1257：Knight Moves

题目链接：http://ybt.ssoier.cn:8088/problem_show.php?pid=1257
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n, l;
 4 int sx, sy;
 5 int ex, ey;
 6 struct node{
 7     int x, y, s;
 8 };
 9 int dir[8][2]={{-1,-2},{-2,-1},{-1,2},{-2,1},{1,2},{2,1},{1,-2},{2,-1}};
10 node que[90005];
11 bool vis[305][305];
12 int f, r;
13 void pr(){//测试使用，观察搜索过程 
14     cout<<f<<":"<<endl;
15     for(int i=0; i<l; i++){
16         for(int j=0; j<l; j++)
17             cout<<vis[i][j];
18         cout<<endl;
19     }
20 }
21 void bfs(){
22     memset(vis, 0, sizeof(vis));//每次初始化为0 
23     f=r=1;//初始化队列 
24     que[r].x=sx; que[r].y=sy; que[r].s=0; vis[sx][sy]=1;
25     while(f<=r){
26         int fx=que[f].x, fy=que[f].y, fs=que[f].s;//获取队首信息 
27         //pr();//测试过程 
28         if(fx==ex && fy==ey){//看是否到达目标 
29             cout<<fs<<endl;
30             break;
31         }
32         for(int i=0; i<8; i++){//8个方向遍历 
33             int nx=fx+dir[i][0], ny=fy+dir[i][1];
34             if(nx>=0 && nx<l && ny>=0 && ny<l && vis[nx][ny]==0){
35                 vis[nx][ny]=1;//更改状态，防止重复访问 
36                 r++;
37                 que[r].x=nx; que[r].y=ny; que[r].s=fs+1; //入队 
38             }
39         }
40         f++;//出队 
41     }
42 }
43 int main()
44 {
45     cin>>n;
46     while(n--){
47         cin>>l;
48         cin>>sx>>sy>>ex>>ey;
49         bfs();
50     }
51     return 0;
52 }