[POJ 1915] Knight Moves

题目链接：http://poj.org/problem?id=1915

题目理解：

T组测试案例，棋盘是n*n的，给你起点和终点的坐标，有八种走法；

求最少走的步数。

注意：

1.别把方向数组写错了

2.如果bfs的函数类型是int型，别忘了写return 0，原因：int型函数的返回值类型是int型，如果没有指明返回值，默认的返回值会因不同的编译器而不同，所以，在存在不可达的情况时，返回的值会因编译器的不同而不同，所以，应该指明这种情况应该返回0；

我的代码：

bfs函数类型是void型

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<queue>
 5 using namespace std;
 6 
 7 int T,sx,sy,ex,ey,n;
 8 bool vis[301][301];
 9 int go[8][2] ={{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};
10 struct node
11 {
12     int x,y,step;
13 };
14 
15 void bfs()
16 {
17     queue<node> Q;
18     node now,nex;
19     now.x = sx;now.y = sy;
20     now.step = 0;
21     Q.push(now);
22     while(!Q.empty()) {
23         now = Q.front();
24         Q.pop();
25         if(now.x == ex && now.y == ey)
26         {
27             printf("%d
", now.step);
28             return;
29         }
30         for(int i = 0; i < 8; i++)
31         {
32             nex.x = now.x + go[i][0];
33             nex.y = now.y + go[i][1];
34             if (nex.x >= 0 && nex.x < n && nex.y >= 0 && nex.y < n && !vis[nex.x][nex.y]) {
35                 nex.step = now.step + 1;
36                 vis[nex.x][nex.y] = 1;
37                 Q.push(nex);
38             }
39         }
40     }
41 }
42 
43 int main()
44 {
45     for(scanf("%d",&T);T;T--)
46     {
47         scanf("%d",&n);
48         scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
49         memset(vis,0,sizeof(vis));
50         bfs();
51     }
52     return 0;
53 }

来自博客(https://blog.csdn.net/hurmishine/article/details/50939508)的代码:

 1 #include<iostream>
 2 #include<cstring>
 3 #include<queue>
 4 using namespace std;
 5 #define maxn 305
 6 bool vis[maxn][maxn];
 7 int a[maxn][maxn];
 8 int n,sx,sy,ex,ey;
 9 int dir[8][2]={-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2,-2,-1};
10 struct node
11 {
12     int x,y,step;
13 };
14 bool OK(int x,int y)
15 {
16     if(x>=0&&x<n&&y>=0&&y<n)
17         return true;
18     else
19         return false;
20 }
21 int BFS()
22 {
23     queue<node>q;
24     node start,mid,next;
25     start.x=sx;
26     start.y=sy;
27     start.step=0;
28     q.push(start);
29     while(!q.empty())
30     {
31         mid = q.front();
32         q.pop();
33         if(mid.x == ex && mid.y == ey)
34             return mid.step;
35         for(int i = 0; i<8; i++)
36         {
37             next.x = mid.x+dir[i][0];
38             next.y = mid.y+dir[i][1];
39             if(next.x == ex && next.y == ey)
40                 return mid.step+1;
41             if (OK(next.x,next.y)&&!vis[next.x][next.y])
42             {
43                 next.step=mid.step+1;
44                 vis[next.x][next.y]=true;
45                 q.push(next);
46             }
47         }
48     }
49     return 0;//少了这句你试试!!!!!!!（回顾上面的注意第二点）
50 }
51 int main()
52 {
53     int t;
54     cin>>t;
55     while(t--)
56     {
57         cin>>n;
58         cin>>sx>>sy;
59         cin>>ex>>ey;
60         memset(vis,false,sizeof(vis));
61         vis[sx][sy]=true;
62         cout<<BFS()<<endl;
63     }
64     return 0;
65 }