ぷよぷよの消去アルゴリズム

元ネタ > 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;
}