Yukicoder013 囲みたい！

問題概要

$H*W$の二次元グリッド上で、それぞれのマスに数字が割り当てられている。 同じ数字のみをたどって上下左右のみに移動できるとき、囲みを作ることができるか。

$H,W\leqq10^2$

yukicoder013

解法

つまるところ四方向に移動できるグリッドグラフで閉路検出をすればよい。
これは今まで訪れたことのある頂点を発見できればよくて、bfsでもdfsでも書くことができる。
よくある感じで実装すれば良い。

計算量:$O(HW)$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using VI = vector<int>;       using VVI = vector<VI>;
    using PII = pair<int, int>;   using PLL = pair<LL, LL>;
    
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };
    
    LL W, H;
    
    LL ans = 0LL;
    
    void bfs(int y, int x, int num, VVI& a, VVI& visit) {
    
        using tp = tuple<PII, PII>;
        queue<tp>q;
        q.push(tp(PII(y, x), PII(-1, -1)));
        while (!q.empty()) {
            PII pos, pre;
            tie(pos, pre) = q.front(); q.pop();
    
            FOR(k, 0, 4) {
                int ny = pos.first + DY[k], nx = pos.second + DX[k];
                if (0 <= ny && ny < H && 0 <= nx && nx < W) {
                    if (ny == pre.first && nx == pre.second)continue;
                    if (a[ny][nx] == num) {
                        if (visit[ny][nx])ans = 1;
                        else {
                            q.push(tp(PII(ny, nx), pos));
                            visit[ny][nx] = 1;
                        }
                    }
                }
            }
        }
    }
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        cin >> W >> H;
        VVI a(H, VI(W, 0));
        FOR(i, 0, H) {
            FOR(j, 0, W) {
                cin >> a[i][j];
            }
        }
        VVI visit(H, VI(W, 0));
        FOR(i, 0, H) {
            FOR(j, 0, W) {
                if (!visit[i][j])bfs(i, j, a[i][j], a, visit);
            }
        }
        cout << (!ans ? "impossible" : "possible") << "\n";
    
        return 0;
    }