題目:
走到終點的時候要移除最少的障礙物
要移除幾個
思路:
如果直接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];
}
};
```