[AtCoder] ABC 151 D – Maze Master

2020年12月15日

問題

方針

良くある迷路の探索のアルゴリズムを使って、全探索を行います。ここでは、全ての道となっているマスから幅優先探索を行い、到達可能なマスの最短距離を求めます。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int H, W;
    cin >> H >> W;
    char c[H][W];
    for (int i = 0; i < H; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < W; j++) {
            c[i][j] = s[j];
        }
    }
    int ans = 0;
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            int d[H][W]{};
            for (int k = 0; k < H; k++) {
                for (int l = 0; l < W; l++) {
                    d[k][l] = -1;
                }
            }
            if (c[i][j] == '#') continue;
            deque<pair<int, int>> q;
            d[i][j] = 0;
            q.push_back(make_pair(i, j));
            while (!q.empty()) {
                pair<int, int> p = q.front();
                q.pop_front();
                int y = p.first;
                int x = p.second;
                for (int k = 0; k < 4; k++) {
                    int ny = y + dy[k];
                    int nx = x + dx[k];
                    if (ny >= H || ny < 0 || nx >= W || nx < 0) continue;
                    if (c[ny][nx] == '.' && d[ny][nx] == -1) {
                        d[ny][nx] = d[y][x] + 1;
                        ans = max(ans, d[ny][nx]);
                        q.push_back(make_pair(ny, nx));
                    }
                }
            }
        }
    }
    cout << ans << "\n";
    return 0;
}