yukicoder ★★★ No.307 最近色塗る問題多くない?

問題

No.307 最近色塗る問題多くない? - yukicoder

考察

同じ色で塗った時、塗りつぶしは行われずすぐ終わります。
違う色で塗った時、少なくとも1つはマスの色が変わります。

違う色で塗る処理はその色を全て辿ればいいので、最悪でも O(H * W)で終わります。
また、色を塗るのは上記の条件より最悪でも O(H * W)回……ですが、市松模様の場合が一番多いのでそれより少ないです。

ということで、計算量的には間に合いそうなので、通常のDFSで書くとACがもらえます。

コード

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

const int MAX_H = 205;
const int MAX_W = 205;
vvi A(MAX_H, vi(MAX_W));

int H, W;

void dfs(int r, int c, int x) {
    if(A[r][c] != x) {
        A[r][c] = x;

        rep(i, 4) {
            int nr = r + dr[i];
            int nc = c + dc[i];

            if(0<=nr && nr<H && 0<=nc && nc<W && A[nr][nc] != x) {
                dfs(nr, nc, x);
            }
        }
    }
}

int main() {
    cin >> H >> W;

    rep(i, H) {
        rep(j, W) {
            cin >> A[i][j];
        }
    }

    int Q;
    cin >> Q;

    bool s_ok = false;
    int last_col = -1;

    while(Q--) {
        int r, c ,x;
        cin >> r >> c >> x;
        --r, --c;

        if(s_ok) {
            last_col = x;
            continue;
        }

        dfs(r, c, x);

        int col = A[0][0];
        bool ok = true;
        rep(i, H) {
            rep(j, W) {
                if(col != A[i][j])
                    ok = false;
            }
        }
        if(ok) {
            s_ok = true;
            last_col = x;
        }
    }

    if(s_ok) {
        rep(i, H) {
            rep(j, W) {
                A[i][j] = last_col;
            }
        }
    }

    rep(i, H) {
        rep(j, W) {
            if(j > 0)
                cout << " ";
            cout << A[i][j];
        }
        cout << endl;
    }

    return 0;
}