AOJ-2232 : Ennichi

Problem A: Ennichi

ぷよぷよっぽいゲームをシュミレートして、１回の操作で全てのマスを消せるかを判定する問題。
操作は、隣り合う２マスを入れ替えるだけ、同じ色がN個以上縦横に並んだら消去。
消えたところには上からマスが落ちてくる。イメージはぷよぷよで考えれば良い。

マスが下に落ちる処理は、右下からループを回していき、１つ上のマスを見るだけで落下はシュミレートできる。今回作成した関数では１つずつしか落ちないので、一気に落ちるところまで、落ちる実装にしたほうがバグは少ないかもしれない。今回は落ちるところがなくなるまで、whileで回すという方法を取っています。

また、問題文の読み間違えでひっかかりそうなのが、隣り合うマスを入れ替えるのは、必ず色付き同士でなくても良いという事。問題文には「 状態 」を入れ替えるなので、空マスと入れ替えるのも処理がないと間違う。

削除は、そのマスを削除していいかの判定を保存してから、あとでまとめて削除したほうがよい。１つずつ見て、削除していくとクロスしているところなどがうまくいきませんでした。

//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2232

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<cmath>
#include<climits>
#include<ctime>
#include<cstring>
#include<numeric>

#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;

using namespace std;
 
int H,W,N;

vector< vector<char> > tmp;

bool win(vector< vector<char> > field)
{
	rep(y,H){
		rep(x,W){
			if(field[y][x] != '.'){ return false; }
		}
	}
	return true;
}

int fall()
{
	int cnt = 0;
	for(int y=H-1; y>0; y--){
		for(int x=W-1; x>=0; x--){
			if(tmp[y][x] == '.' && tmp[y-1][x] != '.'){
				swap(tmp[y][x],tmp[y-1][x]);
				cnt++;
			}
		}
	}
	return cnt;
}

void erase()
{
	vector< vector<bool> > del(H,vector<bool>(W,false));
	rep(y,H)
	{
		rep(x,W)
		{
			char self = tmp[y][x];
			if(self == '.'){ continue; }

			//横の処理
			int cnt=0;
			REP( i, x, W ){
				if( self == tmp[y][i] ){ cnt++; }
				else{ break; }
			}
			if(cnt >= N){
				REP( i, x, W ){					
					if( self == tmp[y][i] ){ del[y][i] = true; }
					else{ break; }
				}
			}
			
			//縦の処理
			cnt = 0;
			REP( i, y, H ){
				if( self == tmp[i][x] ){ cnt++; }
				else{ break; }
			}
			if(cnt >= N){
				REP( i, y, H ){					
					if( self == tmp[i][x] ){ del[i][x] = true; }
					else{ break; }
				}
			}
		}
	}

	rep(y,H){
		rep(x,W){
			if(del[y][x]){ tmp[y][x] = '.'; }
		}
	}
}

void show()
{
	rep(i,H){
		DUMP(tmp[i]);
	}
	cout << "-------------------" << endl;
}

int main()
{
	cin >> H >> W >> N;
	vector< vector<char> > field(H,vector<char>(W,'.'));

	rep(y,H){
		rep(x,W){
			cin >> field[y][x];
		}
	}

	rep(y,H){
		rep(x,W-1)
		{
			tmp = field;
			swap(tmp[y][x],tmp[y][x+1]);
			int cnt=1;
			while(true)
			{
				while(cnt){ cnt = fall(); }
				erase();
				cnt = fall();
				if(!cnt){ break; }
			}

			if(win(tmp)){ //クリアー判定
				cout << "YES" << endl; 
				goto end;
			}
		}
	}
	cout << "NO" << endl;
end:
	return 0;
}