leetcode2290 到达角落需要移除障碍物的最小数目

思路：

最短路。

实现：

 1 class Solution {
 2 public:
 3     const int dx[4]={1,0,-1,0};
 4     const int dy[4]={0,1,0,-1};
 5     int minimumObstacles(vectorint>>& a) {
 6         int n=a.size(),m=a[0].size();
 7         using pii=pair<int,int>;
 8         priority_queue,greater>q;
 9         q.push({0,0});
10         vectorint>>dis(n,vector<int>(m,0x3f3f3f3f));
11         dis[0][0]=0;
12         while(!q.empty()){
13             auto tmp=q.top();q.pop();
14             int d=tmp.first,id=tmp.second;
15             int x=id/m,y=id%m;
16             if(d>dis[x][y])continue;
17             if(x==n-1 and y==m-1)break;
18             dis[x][y]=d;
19             for(int i=0;i<4;i++){
20                 int nx=x+dx[i],ny=y+dy[i];
21                 if(nx<0 or nx>=n or ny<0 or ny>=m){
22                     continue;
23                 }
24                 int new_d=dis[x][y]+a[nx][ny];
25                 if(new_d<dis[nx][ny]){
26                     q.push({new_d,nx*m+ny});
27                     dis[nx][ny]=new_d;
28                 }
29             }
30         }
31         cout<<endl;
32         return dis[n-1][m-1];
33     }
34 };