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

問題

arc040.contest.atcoder.jp

解法

スタート地点から出るときの方向(横 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;
}