问题遇到的现象和发生背景
bfs题,但总是莫名其妙的WA
题目大意:
先输入一个整数q(测试样例的数量)
接下来每个样例包括三行:
第一行,一个整数l(4<=l<=300)表示棋盘大小为l*l;
第二行,两个整数startx,starty,表示棋盘上骑士开始时的坐标;
第三行,两个整数endx,endy,表示棋盘上的目标坐标。
问骑士最少几步走到目标坐标,每个输出占一行。若开始坐标等于结束坐标,输出0。
注:骑士的走法如下图所示:
样例输入:
3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1
样例输出:
5
28
0
问题相关代码,请勿粘贴截图
#include<iostream>
using namespace std;
// flag表示是否搜到,head和tail用于处理队列
int startx,starty,l,endx,endy,tx,ty,flag,head=0,tail=0;
int dir[8][2]={{1,2},{-1,2},{1,-2},{-1,-2},{2,1},{-2,1},{2,-1},{-2,-1}};
int book[501][501]={}; // 标记已搜过的点
struct node{
int x,y,step;
}que[25001];
// 下面是广搜代码
void bfs(){
flag=0;
for(int i=0;i<501;i++){
for(int j=0;j<501;j++){
book[i][j]=0;
}
}
for(int i=0;i<25001;i++){
que[i].x=0;
que[i].y=0;
que[i].step=0;
}
head=0;
tail=0;
que[tail].x=startx;
que[tail].y=starty;
que[tail].step=0;
book[startx][starty]=1;
tail++;
while(head<tail){
for(int i=0;i<8;i++){
tx=que[head].x+dir[i][0];
ty=que[head].y+dir[i][1];
if(tx>=0&&tx<l&&ty>=0&&ty<l&&book[tx][ty]==0){
que[tail].x=tx;
que[tail].y=ty;
que[tail].step=que[head].step+1;
book[tx][ty]=1;
tail++;
if(tx==endx&&ty==endy){
flag=1;
break;
}
}
}
if(flag){
break;
}
head++;
}
}
int main(){
int q;
cin>>q;
while(q--){
cin>>l>>startx>>starty>>endx>>endy;
if(startx==endx&&starty==endy){
cout<<0<<endl;
continue;
}
bfs();
if(!flag){
cout<<0<<endl;
continue;
}
cout<<que[tail-1].step<<endl;
}
return 0;
}
运行结果及报错内容
WA(连续三次都这样)
我的解答思路和尝试过的方法
如上代码,试了几次都不行
我想要达到的结果
得到AC