ぷよぷよの消去アルゴリズム
元ネタ > http://okajima.air-nifty.com/b/2011/01/2011-ffac.html
#include<iostream> #include<vector> #include<cstdio> #include<string> #include<valarray> typedef std::vector<std::vector<int> > Field; const int width=6; const std::string data = " GYRR" "RYYGYG" "GYGYRR" "RYGYRG" "YGYRYG" "GYRYRG" "YGYRYR" "YGYRYR" "YRRGRG" "RYGYGG" "GRYGYR" "GRYGYR" "GRYGYR" ; // 表示 void disp(const Field& field) { const int height = field[0].size(); for(int i=0;i<height;++i) { for(int j=0;j<width;++j) { std::cout<<static_cast<char>(field[j][i]); } std::cout<<std::endl; } } // 転置 template<class T> std::valarray<T> transpose( const std::valarray<T>& A, const int column) { const int row=A.size()/column; std::valarray<size_t> n(2),s(2); n[0]=column;n[1]=row;s[0]=1;s[1]=column; return A[std::gslice(0,n,s)]; } // 配置データ(width*height)からField型(height*width)に変換 Field convert(std::string str) { const int height = str.size()/width; std::valarray<std::string::value_type> tmp(str.c_str(),str.size()); std::valarray<std::string::value_type> trans = transpose(tmp,width); Field field; for(int i=0;i<width;++i) { field.push_back(std::vector<int>(&trans[i*height],&trans[(i+1)*height])); } return field; } // paint(flagで同じ色を塗りつぶす。塗った箇所もついでに数える) int paint(Field& field,const int x,const int y,int flag) { const int height = field[0].size(); const int now = field[x][y]; if(now==flag||now==' ')return 0; field[x][y]=flag; const int nx[] = {x ,x ,x-1,x+1}; const int ny[] = {y-1,y+1,y, y }; int count=1; for(int i=0;i<4;++i) { if(nx[i]>=0&&nx[i]<width&&ny[i]>=0&&ny[i]<height &&field[nx[i]][ny[i]]==now&&field[nx[i]][ny[i]]==now){ count+=paint(field,nx[i],ny[i],flag); } } return count; } // ぷよを消す // 消す場所がなくなったらfalseを返す bool Clear(Field& field) { const int height = field[0].size(); const int mflag= 'x', rflag = 'N'; Field mask(field); for(int i=0;i<width;++i) { for(int j=0;j<height;++j) { // 一回目のpaintで数えて、二回目で消すフラグを立てる if(paint(mask,i,j,mflag)>=4) paint(field,i,j,rflag); } } bool check=false; for(int i=0;i<width;++i) { std::vector<int>::reverse_iterator itr =std::remove_if(field[i].rbegin(),field[i].rend(), std::bind1st(std::equal_to<int>(),rflag)); std::fill(itr,field[i].rend(),' '); check |= itr!=field[i].rend(); } return check; } int main() { Field field=convert(data); for(int i=0;Clear(field);++i) { std::cout<<"["<<i<<"]"<<std::endl; disp(field); } return 0; }