leetcode:1091. 二进制矩阵中的最短路径(广搜)
程序员文章站
2023-12-23 15:35:40
...
题目:
分析:
典型广搜,
vector 可作为队列的内容。
代码:
int main()
{
vector<int> t1;
t1.push_back(0);t1.push_back(0);t1.push_back(0);
vector<int> t2;
t2.push_back(1);t2.push_back(1);t2.push_back(0);
vector<int> t3;
t3.push_back(1);t3.push_back(1);t3.push_back(0);
vector<vector<int> > g;
g.push_back(t1);g.push_back(t2);g.push_back(t3);
if(g.size()==0||g[0].size()==0) return -1;
if(g.size()==1&&g[0].size()==1&&g[0][0]==0) return 1;
if(g[0][0]==1) return -1;
vector<vector<int> > n=g;
for(int i=0;i<g.size();i++)
{
for(int j=0;j<g[0].size();j++)
{
g[i][j]=0;
}
}
vector<int> v(2,0);
int k=1;
queue<vector<int> > q;
q.push(v);
g[0][0]=1;
int ok=0;
cout<<" ---";
while(!q.empty())
{
queue<vector<int> > qq;
while(!q.empty())
{
v=q.front();
q.pop();
//+1 +1
if(v[0]+1<g.size()&&v[1]+1<g[0].size()&&n[v[0]+1][v[1]+1]==0&&g[v[0]+1][v[1]+1]==0)
{
n[v[0]+1][v[1]+1]=1;
if(v[0]+1==g.size()-1&&v[1]+1==g[0].size()-1){
ok=1;
break;
}
vector<int> vv(2,0);
vv[0]=v[0]+1;
vv[1]=v[1]+1;
qq.push(vv);
}
//+1 0
if(v[0]<g.size()&&v[1]+1<g[0].size()&&n[v[0]][v[1]+1]==0&&g[v[0]][v[1]+1]==0)
{
n[v[0]][v[1]+1]=1;
if(v[0]==g.size()-1&&v[1]+1==g[0].size()-1){
ok=1;
break;
}
vector<int> vv(2,0);
vv[0]=v[0];
vv[1]=v[1]+1;
qq.push(vv);
}
if(v[0]+1<g.size()&&v[1]<g[0].size()&&n[v[0]+1][v[1]]==0&&g[v[0]+1][v[1]]==0)
{
n[v[0]+1][v[1]]=1;
if(v[0]+1==g.size()-1&&v[1]==g[0].size()-1){
ok=1;
break;
}
vector<int> vv(2,0);
vv[0]=v[0]+1;
vv[1]=v[1];
qq.push(vv);
}
//-1 -1
if(v[0]-1>-1&&v[1]-1>-1&&n[v[0]-1][v[1]-1]==0&&g[v[0]-1][v[1]-1]==0)
{
n[v[0]-1][v[1]-1]=1;
vector<int> vv(2,0);
vv[0]=v[0]-1;
vv[1]=v[1]-1;
qq.push(vv);
}
//-1
if(v[0]-1>-1&&n[v[0]-1][v[1]]==0&&g[v[0]-1][v[1]]==0)
{
n[v[0]-1][v[1]]=1;
vector<int> vv(2,0);
vv[0]=v[0]-1;
vv[1]=v[1];
qq.push(vv);
}
if(v[1]-1>-1&&n[v[0]][v[1]-1]==0&&g[v[0]][v[1]-1]==0)
{
n[v[0]][v[1]-1]=1;
vector<int> vv(2,0);
vv[0]=v[0];
vv[1]=v[1]-1;
qq.push(vv);
}
if(v[0]-1>-1&&v[1]+1<g[0].size()&&n[v[0]-1][v[1]+1]==0&&g[v[0]-1][v[1]+1]==0)
{
n[v[0]-1][v[1]+1]=1;
vector<int> vv(2,0);
vv[0]=v[0]-1;
vv[1]=v[1]+1;
qq.push(vv);
}
if(v[0]+1<g.size()&&v[1]-1>-1&&n[v[0]+1][v[1]-1]==0&&g[v[0]+1][v[1]-1]==0)
{
n[v[0]+1][v[1]-1]=1;
vector<int> vv(2,0);
vv[0]=v[0]+1;
vv[1]=v[1]-1;
qq.push(vv);
}
}
q=qq;
k++;
if(ok) break;
}
if(ok) return k;
return -1;
}