読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

TopCoder SRM 533 Div1 Medium MagicBoard

この問題は自力で答えまでたどり着けず、少し他の人の解法を参考にした。
http://community.topcoder.com/stat?c=problem_statement&pm=11780

問題

NxMの2次元のグリッドがあり、一部のセルは通るべきマスである。
以下の条件を満たし、全ての通るべきマスを1度ずつ通る経路は存在するか。

  • 移動中、通るべきでないマスで止まることはできない。
  • 最初は任意のマスで開始できる。
  • 奇数回目の移動では、同じ行のうち、まだ通っていない通るべきマスにジャンプする。
  • 偶数回目の移動では、同じ列のうち、まだ通っていない通るべきマスにジャンプする。

解法

奇数回目の移動では、どこかの行のうち2マスを通る。
同様に偶数回目にはどこかの列のうち2マスを通る。

オイラー閉路の考えを応用すれば、開始位置と終了位置を除き、各行と各列が偶数個ずつ通るべきマスがあれば、全部を1回ずつ通ることができそうである。
この推論より、以下のようにすればよい。

  • 開始位置を全通り総当たりし、以下をチェックしていく
  • まずはその開始位置から、奇数回目に横方向、偶数回目に縦方向に移動して、全ての通るべきマスに到達できるかBFSでチェックする。その際は一筆書きは考慮する必要はなく、到達可能かどうかだけチェックすればよい。
    • 全部の通るべきマスに到達不可なら、その開始位置で始める経路はないのでその開始位置はあきらめる。
  • 各行・各列のマスの数の偶奇をカウントし、どれも偶数であることを確認する。
    • 開始位置のマスは最初横に移動するため、その列は奇数個のマスで良いので1つ数をずらしていく。
    • 通るべきマスが偶数個なら、最後の1手は横移動である。よって、奇数個のマスからなる列が1個だけあり、残りの列・行がすべて偶数個のマスからなるなら、題意を満たす閉路が作れる。
    • 通るべきマスが奇数個なら、最後の1手は縦移動である。よって、奇数個のマスからなる行が1個だけあり、残りの列・行がすべて偶数個のマスからなるなら、題意を満たす閉路が作れる。
class MagicBoard {
	public:
	int H,W;
	vector <string> B;
	
	int reachable(int y,int x) {
		int vis[51][51],tx,ty;
		
		ZERO(vis);
		queue<int> Q;
		Q.push(y*100+x);
		vis[y][x]=1;
		while(!Q.empty()) {
			int k=Q.front();
			Q.pop();
			int cy=k/100,cx=k%100;
			int ty,tx;
			if(vis[cy][cx]&1) {FOR(tx,W) if(tx!=cx && B[cy][tx] && (vis[cy][tx]&2)==0) vis[cy][tx]|=2,Q.push(cy*100+tx);}
			if(vis[cy][cx]&2) {FOR(ty,H) if(ty!=cy && B[ty][cx] && (vis[ty][cx]&1)==0) vis[ty][cx]|=1,Q.push(ty*100+cx);}
		}
		int ng=0;
		FOR(y,H) FOR(x,W) if(B[y][x] && vis[y][x]==0) ng++;
		return ng==0;
		
	}
	
	string ableToUnlock(vector <string> board) {
		B=board;
		H=board.size();
		W=board[0].size();
		
		int R[51],C[51],N=0;
		int x,y,tx,ty;
		ZERO(R);
		ZERO(C);
		FOR(y,H) FOR(x,W) B[y][x]=(B[y][x]=='#');
		FOR(y,H) FOR(x,W) R[y]^=B[y][x], C[x]^=B[y][x], N^=B[y][x];
		
		FOR(y,H) FOR(x,W) if(B[y][x]) {
			
			int R2[51],C2[51];
			memmove(R2,R,sizeof(R2));
			memmove(C2,C,sizeof(C2));
			C2[x]^=1;
			int ro=0,co=0;
			FOR(ty,H) ro+=R2[ty];
			FOR(tx,W) co+=C2[tx];
			if(N==1 && ro==1 && co==0 && reachable(y,x)) return "YES";
			if(N==0 && co==1 && ro==0 && reachable(y,x)) return "YES";
		}
		
		return "NO";
	}
}

まとめ

オイラー閉路風のアイデアを使った面白い問題。

広告を非表示にする