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

 

题目理解：

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

求最少走的步数。

 

注意：

1.别把方向数组写错了

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

 

我的代码：

bfs函数类型是void型

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          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 node11 {12     int x,y,step;13 };14 15 void bfs()16 {17     queue
         
           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\n", 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
     
       2 #include
      
        3 #include
       
         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 node11 {12     int x,y,step;13 };14 bool OK(int x,int y)15 {16     if(x>=0&&x
        
         =0&&y
         
          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<
          
           <