AtCoder Regular Contest 040: D - カクカク塗り

問題記録 AtCoder ARC ARC #040

https://atcoder.jp/contests/arc040/tasks/arc040_d

問題概要

N行N列のグリッドが与えられる。グリッドの各マスは床もしくは障害物である。指定されたマスからスタートして「現在の向きに直進し、90度どちらかに向きを変える」という操作を繰り返してすべての床マスを訪れることが可能かどうかを判定せよ。ただし向きは上下左右のいずれかであり、開始時の向きは自由に決められる。また同じマスを2度以上訪れてはならず、グリッドの外や障害物への移動は不可とする。

N <= 400

解法

最終的な経路を想像すると、スタート・ゴールを除く各床マスからは上下どちらかに1本、左右どちらかに1本、の計2本の辺が生えている（スタート・ゴールからは上下左右どこかに1本）。この数に合うよう辺を張ったうえでグラフが連結であれば題意を満たす経路が存在することになる。

また辺の張り方に関しては自由度がほぼない。たとえば#....#のような行があった場合、全部の床に左右辺を生やすには「2マス目と3マス目」「4マス目と5マス目」というように端から貪欲にペアを組んでいくしかない。

よって「開始時の向き」「ゴールの位置」「ゴールの向き」を決め打つと、あとは自動的に上下・左右のそれぞれの辺の生やし方が決定するため、そのとおりに辺を張ってグラフが連結になるかをチェックすれば問題を解くことができる。ゴールの位置を全探索すると決め打ちにO(N2), グラフの構築・連結チェックにO(N2)のO(N4)かかって、これで部分点は通る。

満点解法ではゴールの位置を枝刈りする。まず前提として、ある行や列に存在する床マスの数は基本的には偶数でなければならない（2つずつペアにして辺を張っていくので）。ただしスタート・ゴールマスのある行/列は例外であり、たとえばスタートマスが左向きの場合上下の辺は出ないので、スタートマスは列に関しては障害物マスと同様の扱いになって、実質的にその列のマス数がマイナス1される。ゴールマスも同様である。つまりすべての行/列の床マス数は偶数でなければならないが、スタートマス・ゴールマスには行もしくは列どちらかひとつの床マス数を1減らす効果がある、ということになる。なのでスタートマスの向きを決め打った時点でゴールマスを置くべきなのは「床マスが奇数の行」「床マスが奇数の列」のどちらかであり、しかもそれら以外の行・列はすべて偶数になっている必要がある。これでゴールの位置が「1行のどこか」もしくは「1列のどこか」に絞れたのでNがひとつ落ちてO(N3)になる。

感想

説明が難しすぎる　公式解説を見たほうが図もわかりやすいし全然早いですすいません、あと実装もなんかこまごましたところがめちゃくちゃつらくてつらかった（gotoまで使ってしまった）

コード (C++)

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
#define REP2(i,m,n) for (int i=m;i<(n);i++)
typedef long long ll;

const int dr[4] = {0, 0, -1, 1}; // LRUD
const int dc[4] = {-1, 1, 0, 0}; // LRUD

int N;
string A[404];
int row_parity[404];
int col_parity[404];
int rp = 0, cp = 0;
int sr, sc;
int empty_count;

class UnionFind {
public:
    vector<int> table;
    UnionFind(int n) {
        table = vector<int> (n, -1);
    }

    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (table[x] >= table[y]) {
            table[y] += table[x];
            table[x] = y;
        } else {
            table[x] += table[y];
            table[y] = x;
        }
    }

    int find(int x) {
        if (table[x] < 0) return x;
        return table[x] = find(table[x]);
    }
};

bool check(int sd, int gr, int gc, int gd) {
    UnionFind uf = UnionFind(N*N);
    REP(i, N) REP(j, N) if (A[i][j] != '#') {
        if (i == sr && j == sc && sd != 1) continue;
        if (i == gr && j == gc && gd != 1) continue;
        if (j == N - 1) return false;
        if (A[i][j+1] == '#') return false;
        if (i == sr && j + 1 == sc && sd != 0) return false;
        if (i == gr && j + 1 == gc && gd != 0) return false;
        uf.unite(i*N+j, i*N+j+1), j += 1;
    }
    REP(j, N) REP(i, N) if (A[i][j] != '#') {
        if (i == sr && j == sc && sd != 3) continue;
        if (i == gr && j == gc && gd != 3) continue;
        if (i == N - 1) return false;
        if (A[i+1][j] == '#') return false;
        if (i + 1 == sr && j == sc && sd != 2) return false;
        if (i + 1 == gr && j == gc && gd != 2) return false;
        uf.unite(i*N+j, (i+1)*N+j), i += 1;
    }

    REP(i, N) REP(j, N) if (A[i][j] != '#') return -uf.table[uf.find(i*N+j)] == empty_count;
    return false;
}

void solve() {
    cin >> N;
    REP(i, N) cin >> A[i];

    REP(i, N) REP(j, N) empty_count += A[i][j] != '#';
    REP(i, N) REP(j, N) if (A[i][j] == 's') sr = i, sc = j;
    REP(i, N) REP(j, N) if (A[i][j] != '#') row_parity[i] ^= 1, col_parity[j] ^= 1;
    REP(i, N) rp += row_parity[i], cp += col_parity[i];

    REP(sd, 4) {
        if (sd < 2) {
            cp += col_parity[sc] ? -1 : 1;
            col_parity[sc] ^= 1;
        } else {
            rp += row_parity[sr] ? -1 : 1;
            row_parity[sr] ^= 1;
        }
        if (rp + cp != 1) goto finally;

        REP(i, N) if (row_parity[i]) REP(j, N) if (A[i][j] == '.') REP2(k, 2, 4) if (check(sd, i, j, k)) {
            cout << "POSSIBLE" << endl;
            return;
        }

        REP(j, N) if (col_parity[j]) REP(i, N) if (A[i][j] == '.') REP(k, 2) if (check(sd, i, j, k)) {
            cout << "POSSIBLE" << endl;
            return;
        }

        finally:
        if (sd < 2) {
            col_parity[sc] ^= 1;
            cp -= col_parity[sc] ? -1 : 1;
        } else {
            row_parity[sr] ^= 1;
            rp -= row_parity[sr] ? -1 : 1;
        }        
    }

    cout << "IMPOSSIBLE" << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    solve(); 
}