[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;
}

https://atcoder.jp/contests/abc213/submissions/30603777