kojingharangの日記

AtCoder Regular Contest #012 C. 五目並べチェッカー

22:18 |

• 19x19の盤で五目並べの状態が与えられる。o が先手。x が後手。途中または勝負終了の状態としてあり得るかどうかを返す問題。

• 0≦ oの数 - xの数 ≦1をチェック
• ある色が勝ってるか判定するルーチンを用意して、
• どっちも勝ってるといったことがないかチェック
• どっちかが勝ってたらさらに ox の数に制約が生ずるのでそれもチェック
• 勝負がついていたら、確かに最後の手で勝負がついたかどうかをチェック。
• これには、勝った色のマスのどれかについて、「そのマスを取り消したら勝負がついてない状態である」ようなマスがあるならOK。
• そうでないとき（どう１手戻しても勝ってるとき）はだめ

• 感想→計算量を落とす問題もいいけど、こういう書くのが面倒そうなやつを簡潔に早く書くみたいな問題も面白かった。
• ちょっとした日常のコードを書くための筋トレによさげ。

• accepted

int win(char col, vector<string>& w) {
	int dx[]={1,1,0,-1,-1,-1,0,1};
	int dy[]={0,1,1,1,0,-1,-1,-1};
	REP(y, 19) REP(x, 19) {
		REP(dir, 8) {
			int win=1;
			REP(st, 5) {
				int nx=x+dx[dir]*st;
				int ny=y+dy[dir]*st;
				if(!(0<=nx&&nx<19&&0<=ny&&ny<19)) {win=0;break;}
				if(w[ny][nx]!=col) {win=0;break;}
			}
			if(win) return 1;
		}
	}
	return 0;
}

int solve(vector<string>& w) {
	int Bs=0, Ws=0;
	REP(i, 19) REP(j, 19) Bs+=w[i][j]=='o';
	REP(i, 19) REP(j, 19) Ws+=w[i][j]=='x';
	
	//cout<<"count: "<<Bs<<" "<<Ws<<endl;
	if(!(Bs==Ws || Bs==Ws+1)) return 0;
	
	string col("ox");
	int Bwin = win('o', w);
	int Wwin = win('x', w);
	//cout<<"win: "<<Bwin<<" "<<Wwin<<endl;
	
	if(Bwin && Wwin) return 0;
	if(!(!Bwin || (Bwin && Bs==Ws+1))) return 0;
	if(!(!Wwin || (Wwin && Bs==Ws))) return 0;
	if(Bwin) {
		int ok=0;
		REP(y, 19) REP(x, 19) {
			if(ok) break;
			if(w[y][x]=='o') {
				w[y][x]='.';
				if(!win('o', w)) {ok=1;break;}
				w[y][x]='o';
			}
		}
		if(!ok) return 0;
	}
	if(Wwin) {
		int ok=0;
		REP(y, 19) REP(x, 19) {
			if(ok) break;
			if(w[y][x]=='x') {
				w[y][x]='.';
				if(!win('x', w)) {ok=1;break;}
				w[y][x]='x';
			}
		}
		if(!ok) return 0;
	}
	return 1;
}

int main() {
	//ios::sync_with_stdio(false);
	string s;
	while(getline(cin, s)) {
		vector<string> w(19);
		w[0] = s;
		RANGE(i, 1, 19) getline(cin, w[i]);
		//cout<<w<<endl;
		int ok = solve(w);
		
		
		cout<<(ok?"YES":"NO")<<endl;
		//break;
	}
	
	return 0;
}

ツイートする