AtCoder Regular Contest 040 D - カクカク塗り
解法
スタート地点から出るときの方向(横 or 縦), ゴール地点に向かうときの方向(横 or 縦) を決定すると, 各列について, 以下のようにして移動方法が決まります。
- 基本的に, 列の 2 つの連続したセルを使って縦方向は移動する
- ただし, 以下のセルは通らない
- '#' がある場所
- スタート地点(スタートから出る方向が横の時)
- ゴール地点(ゴールに向かう方向が横の時)
'#' がある場所は通れないのはアタリマエです。スタート地点, ゴール地点以外のセルは, 「そのセルに入って, 出る」ということをしないといけないので, このようにして移動が決定するわけです。
ゴール地点の位置, 出入りするときの方向を決めることで部分点は取れます。満点解法では, ある程度ゴールの位置を絞り込みます。
上で言ったことにより, 基本的にすべての行, 列は偶数個の空きセルがないとダメです。ただ, スタートセルとゴールセルで 2 つまでは偶奇をごまかせるので, 2 個まではあっても良いです。それ以上あったらすぐさま "IMPOSSIBLE" を返しましょう。
これで奇数のセルがある行, 列が絞り込めたので, あとはゴールセルがある位置が「行, 列ともに空きセルが偶数個ある」状態になるようにします。
struct UnionFind { vector<int> par; int n, cnt; UnionFind(const int& x = 0) {init(x);} void init(const int& x) {par.assign(cnt=n=x, -1);} inline int find(const int& x) {return par[x] < 0 ? x : par[x] = find(par[x]);} inline bool same(const int& x, const int& y) {return find(x) == find(y);} inline bool unite(int x, int y) { if ((x = find(x)) == (y = find(y))) return false; --cnt; if (par[x] > par[y]) swap(x, y); par[x] += par[y]; par[y] = x; return true; } inline int count() const {return cnt;} inline int count(int x) {return -par[find(x)];} }; int cntR[500], cntC[500]; bool ok(int sy, int sx, int sdir, int gy, int gx, int gdir, const vector<string>& board) { if (sy != gy && sx != gx) { if (gdir == 1) { if (cntR[gy]%2==0) return false; } else { if (cntC[gx]%2==0) return false; } } if (sy==gy) { int r = cntR[gy]; if (sdir==1) r++; if (gdir==1) r++; if (r%2) return false; } if (sx==gx) { int c = cntC[gx]; if (sdir==0) c++; if (gdir==0) c++; if (c%2) return false; } int N = board.size(); UnionFind uf(N*N); // 辺を貼ってけ // まず縦 for (int x = 0; x < N; x++) { for (int y = 0; y < N; ) { if (board[y][x] == '#') { y++; continue; } if (y==sy && x==sx && sdir == 0) { y++; continue; } if (y==gy && x==gx && gdir == 0) { y++; continue; } if (y+1 >= N || board[y+1][x] == '#' || (y+1==sy&&x==sx&&sdir==0) || (y+1==gy&&x==gx&&gdir==0)) return false; uf.unite(y*N+x, (y+1)*N+x); y += 2; } } // 横 for (int y = 0; y < N; y++) { for (int x = 0; x < N; ) { if (board[y][x] == '#') { x++; continue; } if (x==sx&&y==sy&&sdir==1) { x++; continue; } if (x==gx&&y==gy&&gdir==1) { x++; continue; } if (x+1 >= N || board[y][x+1]=='#' || (x+1==sx&&y==sy&&sdir==1) || (x+1==gx&&y==gy&&gdir==1)) return false; uf.unite(y*N+x, y*N+x+1); x += 2; } } for (int y = 0; y < N; y++) for (int x = 0; x < N; x++) if (board[y][x] != '#') { if (!uf.same(sy*N+sx, y*N+x)) return false; } return true; } int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; vector<string> board(N); for (int i = 0; i < N; i++) cin >> board[i]; int sy = -1, sx = -1; for (int y = 0; y < N; y++) for (int x = 0; x < N; x++) { if (board[y][x] == 's') sy=y, sx=x; } int ngR = 0, ngC = 0; for (int y = 0; y < N; y++) { for (int x = 0; x < N; x++) cntR[y] += (board[y][x] != '#'); if (cntR[y]%2) ngR++; } for (int x = 0; x < N; x++) { for (int y = 0; y < N; y++) cntC[x] += (board[y][x] != '#'); if (cntC[x]%2) ngC++; } if (max(ngR, ngC) > 2) { cout << "IMPOSSIBLE" << endl; return 0; } for (int gy = 0; gy < N; gy++) for (int gx = 0; gx < N; gx++) { if (board[gy][gx] == '#') continue; if (gy==sy && gx==sx) continue; for (int sdir = 0; sdir < 2; sdir++) for (int gdir = 0; gdir < 2; gdir++) { if (ok(sy, sx, sdir, gy, gx, gdir, board)) { cout << "POSSIBLE" << endl; return 0; } } } cout << "IMPOSSIBLE" << endl; return 0; }