yukicoder 0013 囲みたい！

概要

$H \times W$ のフィールドが与えられる. 各マスには整数 $M _ {i,j}$が書かれている.

四近傍のうち, 同じ整数が書かれた所に辺があるグラフと思った時, 閉路があるか.

制約

$H, W \le 100$, $1 \le M _ {i, j} \le 10^3$

解法

概要に書いたところまで問題を落としてしまえばすぐ見えるけど, こういうのは Union Find に丸投げすると楽.

unite する時に, 既に同じ成分に属していたら, 閉路が出来る. $O(HW * \alpha(HW))$.

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool solve(){
    int w, h; cin >> w >> h;
    UnionFind2D uf(h, w);
    vector<vector<int>> in(h, vector<int>(w));
    rep(i, h) rep(j, w) cin >> in[i][j];
    constexpr int dxy[2] = {0, 1};
    rep(i, h) rep(j, w) rep(dir, 2){
        int x = i + dxy[dir], y = j + dxy[1-dir];
        if(x < 0 or x >= h) continue;
        if(y < 0 or y >= w) continue;
        if(in[i][j] != in[x][y]) continue;
        if(!uf.unite(i, j, x, y)){ cout << "possible" << endl; return true; }
    }
    cout << "impossible" << endl;
    return true;
}