题目:
走到终点的时候要移除最少的障碍物
要移除几个
思路:
如果直接bfs+priority queue 的话
当然是可以
不过加上另一个阵列纪录走过的地方跟他的值
来dp的话会更好
其实就是dijk吧
只是是在阵列上面
又水了一题hard
赞赞赞
```cpp
class Solution {
public:
int minimumObstacles(vector<vector<int>>& grid)
{
int n = grid.size();
int m = grid[0].size();
vector<vector<int>> paper(n,vector<int>(m,200000));
// obs i j
priority_queue<pair<int,pair<int,int>> , vector<pair<int,pair<int,int>>>
, greater<pair<int,pair<int,int>>> > pq;
pq.push({0,{0,0}});
while(!pq.empty())
{
int obs = pq.top().first;
int i = pq.top().second.first;
int j = pq.top().second.second;
pq.pop();
if(paper[i][j] > obs)paper[i][j] = obs;
else continue;
if(i == n-1 && j == m-1)return obs;
if(i-1>=0)
{
if(grid[i-1][j] == 1 && (paper[i-1][j] > obs))pq.push({obs+1 , {
i-1,j}});
else if(grid[i-1][j] == 0 && (paper[i-1][j] > obs))pq.push({obs
, {i-1,j}});
}
if(i+1<n)
{
if(grid[i+1][j] == 1 && (paper[i+1][j] > obs)) pq.push({obs+1 ,
{i+1,j}});
else if(grid[i+1][j] == 0 && (paper[i+1][j] > obs)) pq.push({obs
, {i+1,j}});
}
if(j-1>=0)
{
if(grid[i][j-1] == 1 && (paper[i][j-1] > obs)) pq.push({obs+1 ,
{i,j-1}});
else if(grid[i][j-1] == 0 && (paper[i][j-1] > obs)) pq.push({ob
s , {i,j-1}});
}
if(j+1<m)
{
if(grid[i][j+1] == 1 && (paper[i][j+1] > obs)) pq.push({obs+1 ,
{i,j+1}});
else if(grid[i][j+1] == 0 && (paper[i][j+1] > obs)) pq.push({obs
, {i,j+1}});
}
}
return paper[n-1][m-1];
}
};
```