分析
采用优先队列对整个路径的寻找进行处理,
优先队列采用手写队列,每次bfs完后对于新的队列进行排序,之后每次取出的队头元素的权值一定是最小的。
每次取出的队头元素的权值就是选择走的路,所以此时要更新ans,取二者最大值。
C++ 代码
class Solution {
public:
int n,m,hh=0,tt=-1,ans=-1;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
struct node{
int x,y,w;
bool operator<(const node& p) //排序函数,按权值
{
return w<p.w;
}
}q[55*55]; //定义优先队列
int bfs(vector<vector<int>>& grid)
{
bool st[n+1][m+1];
memset(st,0,sizeof st);
node t;
t.x=0,t.y=0,t.w=grid[0][0];
q[++tt]=t;
st[0][0]=true;
while(hh<=tt)
{
t=q[hh++]; //取出队头元素,此时该元素权值最小
ans=max(ans,t.w); //取二者最大值,因为此时才能游到这个地方
node cur;
for(int i=0;i<4;i++)
{
cur.x=t.x+dx[i];
cur.y=t.y+dy[i];
if(cur.x==n-1 && cur.y==m-1) //搜到了终点
{
cur.w=grid[cur.x][cur.y];
q[++tt]=cur;
ans=max(ans,cur.w); //答案更新为二者的最大值
return 0;
}
if(cur.x>=0 && cur.x<n && cur.y>=0 && cur.y<m && !st[cur.x][cur.y])
{
cur.w=grid[cur.x][cur.y];
st[cur.x][cur.y]=true;
q[++tt]=cur; //该点加入到队列中
}
}
sort(q+hh,q+tt+1); //对队列进行排序,保证每次队头元素权值是最小的
}
return 0;
}
int swimInWater(vector<vector<int>>& grid) {
if(grid.size()<1) return 0;
n=grid.size(),m=grid[0].size();
bfs(grid);
return ans;
}
};