AtCoder AGC 033 A - Darker and Darker (緑色, 300 点)

また一つ、教育的 & 典型的な BFS 問が誕生した！！！

問題へのリンク

問題概要

× のグリッドがあって、各マスは「白」「黒」に塗られている。

1 秒ごとに、各黒マスに対し、その上下左右に隣接したマスが存在するならば、そのマスを黒く上塗りしていく。全マスが黒になるのに何秒要するかを求めよ。

制約

• 

考えたこと

つまり

• 各白マスについて、そこから最も近い黒マスまでの距離を求め
• その最大値を求める

ということがしたい。白マス (r, c) に対して、そこから最寄りの黒マスまでの距離とはつまり、「全黒マスをスタート地点として同時にスタートして (r, c) までに至るまでの最短時間」ということになる。

こういうのを多点スタートな最短路問題と呼ぶことがある。1 点スタートであれば普通の BFS で解くことができる。多点スタートでもほとんど変わらず、

• 初期状態でキューに全スタートを突っ込む
• 全スタート地点の距離値を 0 に初期化する

とすれば OK。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int H, W;
vector<string> fi;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main() {
    cin >> H >> W;
    fi.resize(H);
    for (int i = 0; i < H; ++i) cin >> fi[i];

    // 多点をスタートとして扱う
    vector<vector<int> > dist(H, vector<int>(W, -1));
    using pint = pair<int,int>;
    queue<pint> que;
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if (fi[i][j] == '#') {
                dist[i][j] = 0;
                que.push(pint(i, j));
            }
        }
    }

    // BFS
    while (!que.empty()) {
        auto cur = que.front();
        que.pop();
        for (int dir = 0; dir < 4; ++dir) {
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];
            if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
            if (dist[nx][ny] == -1) {
                dist[nx][ny] = dist[cur.first][cur.second] + 1;
                que.push(pint(nx, ny));
            }
        }
    }
    int res = 0;
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            res = max(res, dist[i][j]);
        }
    }
    cout << res << endl;
}