Skiing [CodeChef November Cook-Off 2017 C]

https://www.codechef.com/COOK88/problems/SKIING

H(=N)行W(=M)列の行列Aがある。
「A[y][x] := 座標(x,y)の高さ」である。
現在(x,y)にいる時、移動できるのは高さが同じか低い隣り合った座標である。
ここで、座標集合Sを定義する。
全ての座標に座標集合のいずれかの座標から遷移可能となるようにするとき、座標集合Sのサイズの最小値は？

前提知識

• UnionFind

解法

https://www.codechef.com/viewsolution/16322478

隣り合う同じ高さの座標は好きに移動できるため、UnionFindで1つにまとめておく。
座標集合Sに入れるべき座標について考えてみる。
そのため、A[x][y] > A[xx][yy]であるとき、(x,y)から(xx,yy)へ遷移可能と考え、有向辺を引いた有向グラフを考える。
すると、入ってくる辺が無い頂点はどこからも遷移されないため、頂点Sに入れる必要がある。
そのような頂点を数え上げれば答え。

int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };
int H, W, A[1010][1010];
int in[1010101];
//---------------------------------------------------------------------------------------------------
void solve() {
    cin >> H >> W;
    rep(y, 0, H) rep(x, 0, W) cin >> A[y][x];
 
    UnionFind uf(H*W);
    rep(y, 0, H) rep(x, 0, W) rep(d, 0, 4) {
        int xx = x + dx[d];
        int yy = y + dy[d];
        if (0 <= xx and xx < W and 0 <= yy and yy < H) {
            if (A[y][x] == A[yy][xx]) uf(y * W + x, yy * W + xx);
        }
    }
 
    rep(i, 0, H*W) in[i] = 0;
    rep(y, 0, H) rep(x, 0, W) rep(d, 0, 4) {
        int xx = x + dx[d];
        int yy = y + dy[d];
        if (0 <= xx and xx < W and 0 <= yy and yy < H) {
            if (A[y][x] < A[yy][xx]) {
                int a = uf[y * W + x], b = uf[yy * W + xx];
                // b -> a
                in[a]++;
            }
        }
    }
 
    int ans = 0;
    rep(i, 0, H*W) if (uf[i] == i and in[i] == 0) ans++;
    cout << ans << endl;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    rep(t, 0, T) solve();
}