Leetcode:2290
两题均可用bfs算法做出,但很难做到最优。
而如果将queue替换成deque将可以将速度提升一倍
主要是将优先级较高的放在队列前面,提前出队,优先级低的放在队列尾处。
如何判断优先级将是至关重要的
int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; typedef pair<int,int> pii; class Solution { public: int minimumObstacles(vector<vector<int>>& grid) { auto & g = grid; int m = g.size(); int n= g[0].size(); vector<vector<int> > st(m+10,vector<int>(n+10,0x3f3f3f3f)); queue<pii> heap; heap.push({0,0}); int cnt=0; if(g[0][0])cnt++;st[0][0]=0; while(heap.size()){ auto top = heap.front(); heap.pop(); for(int i=0;i<4;i++){ int x= top.first+dx[i],y=top.second+dy[i]; if(x<0||x>=m||y<0||y>=n||st[x][y]<=(st[top.first][top.second]+g[x][y]))continue; st[x][y]=st[top.first][top.second]+g[x][y]; heap.push({x,y}); } } // for(int i=0;i<m;i++){ // for(int j=0;j<n;j++){ // cout<<st[i][j]<<" "; // }cout<<endl; // } return cnt+st[m-1][n-1]; } };
int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; typedef pair<int,int> pii; class Solution { public: int minimumObstacles(vector<vector<int>>& grid) { auto & g = grid; int m = g.size(); int n= g[0].size(); vector<vector<int> > st(m+10,vector<int>(n+10,0x3f3f3f3f)); deque<pii> heap; heap.push_front({0,0}); int cnt=0; if(g[0][0])cnt++;st[0][0]=0; while(heap.size()){ auto top = heap.front(); heap.pop_front(); for(int i=0;i<4;i++){ int x= top.first+dx[i],y=top.second+dy[i]; if(x<0||x>=m||y<0||y>=n||st[x][y]<=(st[top.first][top.second]+g[x][y]))continue; st[x][y]=st[top.first][top.second]+g[x][y]; if(g[x][y]) heap.push_back({x,y}); else heap.push_front({x,y}); } } // for(int i=0;i<m;i++){ // for(int j=0;j<n;j++){ // cout<<st[i][j]<<" "; // }cout<<endl; // } return cnt+st[m-1][n-1]; } };