上海计算机学会 2023年9月月赛 乙组T2 方格路径（二）（最短路）

标签：最短路
题意：给定$n\times m$的方格地图，每个点要么是空地$.$，要么是障碍物$\ast$，求左上角到右下角，最少的移除障碍个数，每次只能水平或者垂直移动。
题解：跑个最短路，如果走的下个点是障碍物，边权为$1$，否则为$0$。直接跑$SPFA$会超时，得用堆优化的$dijkstra$。这边代码为了方便，直接$pair$套$pair$了。
代码：

#include <bits/stdc++.h>
using namespace std;const int INF = 0x3f3f3f3f;
int d[1005][1005], vis[1005][1005];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
char a[1005][1005];
pair<int, int> p;int main() {int n, m;cin >> n >> m;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++) {cin >> a[i][j];d[i][j] = INF;}priority_queue< pair<int, pair<int, int> > > q;d[1][1] = 0;q.push(make_pair(0, make_pair(1, 1)));while (!q.empty()) {p = q.top().second;q.pop();if (vis[p.first][p.second]) continue;vis[p.first][p.second] = 1;for (int i = 0; i < 4; i++) {int nx = p.first + dx[i];int ny = p.second + dy[i];int cost = (a[nx][ny] == '*') ? 1 : 0;if (nx < 1 || nx > n || ny < 1 || ny > m) continue;if (d[nx][ny] > d[p.first][p.second] + cost) {d[nx][ny] = d[p.first][p.second] + cost;q.push(make_pair(-d[nx][ny], make_pair(nx, ny)));}}}cout << d[n][m];return 0;
}