解説 ARC 005C 器物損壊！高橋君
February 7, 2023ダイクストラ法を使えば、スタート地点から各区画への最短距離を求められる。 塀に移動にかかる時間を十分に大きい値、かりに\(HM+1\)として、ダイクストラ法適用すると、 ゴール地点が\(3(HM+1)\)以下未満であり、そのときに限り、塀を壊す回数が2回以下でゴール地点に到達できる。
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main() {
int h, w;
cin >> h >> w;
vector<string> grid(h);
rep(i, h) cin >> grid[i];
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>,
greater<pair<int, pair<int, int>>>>
que;
vector<vector<int>> d(h, vector<int>(w, 1 << 28));
int goal_r, goal_c;
rep(i, h) {
rep(j, w) {
if (grid[i][j] == 's') {
d[i][j] = 0;
que.push({0, {i, j}});
}
if (grid[i][j] == 'g') {
goal_r = i;
goal_c = j;
}
}
}
int mx = 500 * 500 + 1;
while (que.size()) {
auto [cost, pos] = que.top();
que.pop();
auto [row, col] = pos;
if (d[row][col] < cost)
continue;
vector<pair<int, int>> neighbors = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
for (auto [d_row, d_col] : neighbors) {
int next_row = row + d_row, next_col = col + d_col;
if (0 <= next_row && next_row < h && 0 <= next_col && next_col < w) {
int d_cost;
if (grid[next_row][next_col] != '#')
d_cost = 1;
else
d_cost = mx;
if (cost + d_cost < d[next_row][next_col]) {
d[next_row][next_col] = cost + d_cost;
que.push({cost + d_cost, {next_row, next_col}});
}
}
}
}
if (d[goal_r][goal_c] < mx * 3)
cout << "YES";
else
cout << "NO";
cout << endl;
return 0;
}