AGC033 A Darker and Darker

問題ページ - A - Darker and Darker

概要

行列のマス目が与えられる。各マスは白、または黒のいずれかに塗られている。全てのマスが黒色になるまで、以下の操作を繰り返す。

• 白いマスであって、黒いマスと辺を共有するマスを黒くする。

この操作が何回行われるか求めよ。

制約

• 
• 黒いマスが1つ以上存在する

解法

まず、初めにある黒いマスは1個だけであるという場合を考える。1回の操作で黒いマスと辺を共有するマスが全て黒くなるということは、そのマスが黒くなるのに必要な操作回数は、黒マスを始点としたグリッドグラフの最短路の長さと同じである。よって、全体で行われる操作回数は、黒マスから一番遠い頂点までの最短路の長さと同じと言える。これは幅優先探索で求めることができる。では、黒いマスが2個以上ある場合はどうだろうか。この場合も似たような手順で求めることができる。単一始点の最短経路問題では、初めにキューに始点を入れて探索を始める。同様に、黒いマスが2個以上ある場合は予め全ての黒いマスをキューに入れてから探索を始める。キューの先頭から順にコストを並べたとき、単調非減少であればよいため、この方法で答えを求めることができる。

提出コード

https://atcoder.jp/contests/agc033/submissions/5298324

#include<bits/stdc++.h>
using namespace std;

const int INF = (1 << 30) - 1;

/* マス(y,x)と辺を共有するマスは、(y,x+1), (y+1,x), (y,x-1), (y-1,x)
   の4つであるため、このような配列を用いて効率的に探索できる */
const int dy4[] = {0, 1, 0, -1}, dx4[] = {1, 0, -1, 0};

int main(){
    // 入力
    int h, w;
    cin >> h >> w;

    vector<string> a(h);
    for(int i = 0 ; i < h ; ++i){
        cin >> a[i];
    }

    // 幅優先探索
    queue< pair< pair<int, int>, int> > que;  // {{y座標, x座標}, コスト}
    vector< vector<int> > cost(h, vector<int>(w, INF));  // 最小コスト

    // 黒いマスをキューに入れる
    for(int i = 0 ; i < h ; ++i){
        for(int j = 0 ; j < w ; ++j){
            if(a[i][j] == '#'){
                que.push({{i, j}, 0});
                cost[i][j] = 0;
            }
        }
    }

    // 最小コストの更新が止まるまで探索
    while(!que.empty()){
        auto now = que.front();
        que.pop();
        if(cost[now.first.first][now.first.second] < now.second){
            continue;
        }
        cost[now.first.first][now.first.second] = now.second;
        for(int i = 0 ; i < 4 ; ++i){
            int ny = now.first.first + dy4[i], nx = now.first.second + dx4[i];
            if(0 <= ny && ny < h && 0 <= nx && nx < w && cost[ny][nx] > now.second + 1){
                cost[ny][nx] = now.second + 1;
                que.push({{ny, nx}, now.second + 1});
            }
        }
    }

    // 最小コストの最大値を求める
    int ans = 0;
    for(int i = 0 ; i < h ; ++i){
        for(int j = 0 ; j < w ; ++j){
            ans = max(ans, cost[i][j]);
        }
    }

    cout << ans << endl;

    return 0;
}