この問題は自力で答えまでたどり着けず、少し他の人の解法を参考にした。
http://community.topcoder.com/stat?c=problem_statement&pm=11780
問題
NxMの２次元のグリッドがあり、一部のセルは通るべきマスである。
以下の条件を満たし、全ての通るべきマスを１度ずつ通る経路は存在するか。
- 移動中、通るべきでないマスで止まることはできない。
- 最初は任意のマスで開始できる。
- 奇数回目の移動では、同じ行のうち、まだ通っていない通るべきマスにジャンプする。
- 偶数回目の移動では、同じ列のうち、まだ通っていない通るべきマスにジャンプする。
解法
奇数回目の移動では、どこかの行のうち２マスを通る。
同様に偶数回目にはどこかの列のうち２マスを通る。
オイラー閉路の考えを応用すれば、開始位置と終了位置を除き、各行と各列が偶数個ずつ通るべきマスがあれば、全部を１回ずつ通ることができそうである。
この推論より、以下のようにすればよい。
- 開始位置を全通り総当たりし、以下をチェックしていく
- まずはその開始位置から、奇数回目に横方向、偶数回目に縦方向に移動して、全ての通るべきマスに到達できるかBFSでチェックする。その際は一筆書きは考慮する必要はなく、到達可能かどうかだけチェックすればよい。
- 全部の通るべきマスに到達不可なら、その開始位置で始める経路はないのでその開始位置はあきらめる。
- 各行・各列のマスの数の偶奇をカウントし、どれも偶数であることを確認する。
- 開始位置のマスは最初横に移動するため、その列は奇数個のマスで良いので１つ数をずらしていく。
- 通るべきマスが偶数個なら、最後の１手は横移動である。よって、奇数個のマスからなる列が１個だけあり、残りの列・行がすべて偶数個のマスからなるなら、題意を満たす閉路が作れる。
- 通るべきマスが奇数個なら、最後の１手は縦移動である。よって、奇数個のマスからなる行が１個だけあり、残りの列・行がすべて偶数個のマスからなるなら、題意を満たす閉路が作れる。
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"; } }
