代码收集0014——找到从起点到终点的路
程序员文章站
2024-03-02 19:53:10
...
int Path(vector<vector<int>>& point)
{
int row=point.size(),col=point[0].size(),ans=0;
const vector<vector<int>> direction{{-1,0},{1,0},{0,-1},{0,1}};
int left=0,right=max_possible_ans+1;//we try to use binary search to find the ans.
while(left<=right)
{
int mid=(left+right)/2;
queue<pair<int,int>> q;
q.emplace(0,0);
vector<vector<bool>> visit(row,vector<bool>(col));
while(!q.empty())
{
auto [x,y]=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int nx=x+direction[i][0],ny=y+direction[i][1];//next position
if(nx<row&&nx>=0&&ny<col&&ny>=0&&!visit[nx][ny]&&/*
the condition that needed to be satisfied*/)
{
q.emplace(nx,ny);
visit[nx][ny]=true;
}
}
}
if(visit[row-1][col-1])
{
ans=mid;
right=mid-1;
}
else
left=mid+1;
}
return ans;
}
推荐阅读