[ABC213] E - Stronger Takahashi
[Q] https://atcoder.jp/contests/abc213/tasks/abc213_e
priority_queueでBFSをする場合の戒め
(正) top()を取得したあと、すぐにpop()する。
(誤) top()を参照取得し、pushが終わったあとpop()する。
途中のpushで最小要素の更新があった場合、新しい要素をpop()してしまう
考察
1. 道と隣接してるなら、コスト0で進む
2. 自分の周囲20マスなら、コスト1で壊せる
Q. 隣接する、破壊できる範囲は？
#####
#####
##0##
#####
#####
A. この20マス
#111#
11111
11011
11111
#111#
自分を中心とした隣接20マスが、1ターンで破壊して移動できるマス。実装
vector<ll> dx, dy;
ll dx4[] = {0, 1, 0, -1};
ll dy4[] = {-1, 0, 1, 0};
bool isn_field(ll y, ll x, ll H, ll W) {
return (y < 0 || y >= H || x < 0 || x >= W);
}
ll H, W;
ll DP[510][510];
char C[510][510];
int main() {
cincout();
cin >> H >> W;
rep(i, H) { cin >> C[i]; }
rep(i, H) rep(j, W) DP[i][j] = oo;
dy.reserve(25);
dx.reserve(25);
for (ll i = -2; i <= 2; ++i) {
for (ll j = -2; j <= 2; ++j) {
ll d = abs(i) + abs(j);
if (d == 0 || d == 4) continue;
dy.push_back(i);
dx.push_back(j);
}
}
priority_queue<pll, vector<pll>, greater<pll>> Q; // turn, pos
Q.push({0, 0});
DP[0][0] = 0;
while (!Q.empty()) {
auto [turn, pos] = Q.top();
Q.pop(); // すぐにpopする
ll y = pos / 1000;
ll x = pos % 1000;
if (turn != DP[y][x]) continue;
// まず4方向みて、道を進む
rep(i, 4) {
ll ny = y + dy4[i];
ll nx = x + dx4[i];
if (isn_field(ny, nx, H, W)) continue;
if (C[ny][nx] == '#') continue;
if (chmin(DP[ny][nx], turn)) {
Q.push({turn, ny * 1000 + nx});
}
}
// 20マス見て、壁爆破する
rep(i, (ll)dy.size()) {
ll ny = y + dy[i];
ll nx = x + dx[i];
if (isn_field(ny, nx, H, W)) continue;
if (chmin(DP[ny][nx], turn + 1)) {
Q.push({turn + 1, ny * 1000 + nx});
}
}
// Q.pop()しない
// ここでpopすると、途中でpushしたものを含めた最小値がpopされてしまう
}
cout << DP[H - 1][W - 1] << endl;
}