思路
反着跑一遍BFS并标记
正着再跑一遍BFS并输出
#include<bits/stdc++.h>
using namespace std;
int f[1005][1005],t,tx,ty;
int book[1005][1005];
int kx[4]={0,0,1,-1};
int ky[4]={1,-1,0,0};
struct vivo{
int x,y;
}mi;
queue< vivo > v;
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
cin>>t;
if(t)
{
f[i][j]=-1;
book[i][j]=0;
}
else
{
f[i][j]=0;
book[i][j]=1;
}
}
book[n][n]=0;
f[n][n]=1;
mi.x=n;
mi.y=n;
v.push(mi);
while(v.size())
{
for(int i=0;i<4;i++)
{
tx=v.front().x+kx[i];
ty=v.front().y+ky[i];
if(tx>0&&ty>0&&tx<=n&&ty<=n&&book[tx][ty])
{
book[tx][ty]=0;
mi.x=tx;
mi.y=ty;
v.push(mi);
f[tx][ty]=f[v.front().x][v.front().y]+1;
}
}
v.pop();
}
mi.x=1;
mi.y=1;
v.push(mi);
printf("0 0\n");
while(v.size())
{
for(int i=0;i<4;i++)
{
tx=v.front().x+kx[i];
ty=v.front().y+ky[i];
if(tx>0&&ty>0&&tx<=n&&ty<=n&&f[tx][ty]==f[v.front().x][v.front().y]-1)
{
printf("%d %d\n",tx-1,ty-1);
mi.x=tx;
mi.y=ty;
v.push(mi);
break;
}
}
v.pop();
}
return 0;
}
有人试过用dfs回溯的吗??
###bfs+dfs
看错了是0~n-1 所以回溯的时候就减了个1 懒得改了hh
非常滴妙妙种子妙妙屋
为什么这能保证是最短的
bfs就是最短
bfs不往回走的话就是最短的 往回走指的是上一道那种八个方向或者四个方向
非常滴妙
棒啊