算法
(01BFS) $O(HW)$
当相邻的方格可以通行时,边权为 $0$;当我们需要挥一拳毁掉 $2 \times 2$ 的障碍物时,边权为 $1$
当边权为 $0, 1$ 时,我们可以用 01BFS
来代替 Dijkstra
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::min;
using std::abs;
using std::deque;
using std::vector;
using std::string;
using P = std::pair<int, int>;
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, -1, 0, 1};
int main() {
int h, w;
cin >> h >> w;
vector<string> s(h);
rep(i, h) cin >> s[i];
deque<P> q;
const int INF = 1001001001;
vector dist(h, vector<int>(w, INF));
vector visited(h, vector<bool>(w));
dist[0][0] = 0;
q.emplace_back(0, 0);
while (q.size()) {
auto [i, j] = q.front(); q.pop_front();
if (visited[i][j]) continue;
visited[i][j] = true;
int d = dist[i][j];
rep(v, 4) {
int ni = i + di[v], nj = j + dj[v];
if (ni < 0 or nj < 0 or ni >= h or nj >= w) continue;
if (s[ni][nj] == '#') continue;
if (dist[ni][nj] <= d) continue;
dist[ni][nj] = d;
q.emplace_front(ni, nj);
}
for (int ei = -2; ei <= 2; ++ei) {
for (int ej = -2; ej <= 2; ++ej) {
if (abs(ei) + abs(ej) > 3) continue;
int ni = i + ei, nj = j + ej;
if (ni < 0 or nj < 0 or ni >= h or nj >= w) continue;
if (dist[ni][nj] <= d + 1) continue;
dist[ni][nj] = d + 1;
q.emplace_back(ni, nj);
}
}
}
cout << dist[h - 1][w - 1] << '\n';
return 0;
}