嗨嗨嗨,我来啦~~~
好久没看到手写队列的人了,属实是倍感亲切[笑]
OK,闲话不多说,提正事!
你的代码的问题其实出在这里(bfs函数里):
```cpp
if(xx==n&&yy==m)
{
b[xx][yy]=a[tail].k;
return;
}
```
由于我们的马是要走遍全局尝试路径的,所以走到了右下角并不能判断尝试结束。你这段代码导致了探索提前结束,把它删去就可以了。
另外,在主函数这里:
```cpp
memset(b,-1,sizeof(b));
bfs(n,m);
b[x][y]=0;
```
最好换成:
```cpp
memset(b,-1,sizeof(b));
b[x][y]=0;
l[x][y]=1;
bfs(n,m);
```
这里探索前没标记的话,可能会在bfs中导致重复探索。不过其实问题不大~~~
AC代码(从你代码改的)如下:
```cpp
#include<iostream>
#include<cstdio>
#include<string>
#include<cmath>
#include<climits>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m;
int x,y;
struct p
{
int x;
int y;
int k;
};
p a[100086];
bool l[10006][10005];
int b[1086][10010];
int dx[]={-1,-2,-2,-1,1,2,2,1},
dy[]={-2,-1,1,2,2,1,-1,-2};
void bfs(int n,int m)
{
int head=0;
int tail=1;
a[tail].x=x;
a[tail].y=y;
a[tail].k=0;
while(head<tail)
{
head++;
for(int i=0;i<8;i++)
{
int xx=a[head].x+dx[i];
int yy=a[head].y+dy[i];
if(xx>=1 && yy>=1 && xx<=n && yy<=m && !l[xx][yy])
{
tail++;
a[tail].x=xx;
a[tail].y=yy;
a[tail].k=a[head].k+1;
l[xx][yy]=1;
b[xx][yy]=a[tail].k;
}
}
}
}
int main()
{
cin>>n>>m;
cin>>x>>y;
memset(b,-1,sizeof(b));
b[x][y]=0;
l[x][y]=1;
bfs(n,m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{cout<<b[i][j]<<" ";}
cout<<endl;
}
return 0;
}
```
最后再提一点改进建议:
那个判断数组l可以删掉,直接看地图数组是否为-1来判断有没有走过,可以节省一点内存
by AZYDLL @ 2023-07-10 12:27:45