[AtCoder] ABC 151 D – Maze Master
問題
方針
良くある迷路の探索のアルゴリズムを使って、全探索を行います。ここでは、全ての道となっているマスから幅優先探索を行い、到達可能なマスの最短距離を求めます。
コード
#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; }
ディスカッション
コメント一覧
まだ、コメントがありません