1. spfa
const int inf = 0x3f3f3f3f;
class Solution {
public:
struct Node{
int x, y, d;
bool operator< (const Node& b){
return d < b.d;
}
};
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
//转化为求最短路问题
int minimumObstacles(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
queue<Node> que;
vector<vector<int>> dist(n + 5, vector<int>(m + 5, inf));
vector<vector<bool>> st(n + 5, vector<bool>(m + 5));//记录que中的元素
que.push({0, 0, 0});
dist[0][0] = 0;
st[0][0] = true;
while(que.size()){
auto tmp = que.front();
que.pop();
st[tmp.x][tmp.y] = false;
for(int i = 0; i < 4; i ++){
int s = tmp.x + dx[i], t = tmp.y + dy[i];
if(s < 0 || t < 0 || s >= n || t >= m) continue;
if(dist[s][t] > dist[tmp.x][tmp.y] + grid[s][t]){
dist[s][t] = dist[tmp.x][tmp.y] + grid[s][t];
if(! st[s][t]){
que.push({s, t, dist[tmp.x][tmp.y] + grid[s][t]});
st[s][t] = true;
}
}
}
}
return dist[n - 1][m - 1];
}
};
2. dijkstra
const int inf = 0x3f3f3f3f;
class Solution {
public:
struct Node{
int x, y, d;
bool operator > (const Node& b) const{
return d > b.d;
}
};
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
//转化为求最短路问题
int minimumObstacles(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
//dijk
priority_queue<Node, vector<Node>, greater<Node>> pque;
vector<vector<int>> dist(n + 5, vector<int>(m + 5, inf));
vector<vector<bool>> st(n + 5, vector<bool>(m + 5));//记录已经计算完毕的元素
pque.push({0, 0, 0});
dist[0][0] = 0;
while(pque.size()){
auto tmp = pque.top();
pque.pop();
if(st[tmp.x][tmp.y]) continue;
st[tmp.x][tmp.y] = true;
for(int i = 0; i < 4; i ++){
int s = tmp.x + dx[i], t = tmp.y + dy[i];
if(s < 0 || t < 0 || s >= n || t >= m) continue;
if(dist[s][t] > dist[tmp.x][tmp.y] + grid[s][t]){
dist[s][t] = min(dist[s][t], dist[tmp.x][tmp.y] + grid[s][t]);
pque.push({s, t, dist[s][t]});
}
}
}
return dist[n - 1][m - 1];
}
};