题目描述

原题来自：POJ 1915

编写一个程序，计算一个骑士从棋盘上的一个格子到另一个格子所需的最小步数。骑士一步可以移动到的位置由下图给出。

输入格式

第一行给出骑士的数量 n。
在接下来的 3n行中，每 3 行描述了一个骑士。其中，

• 第一行一个整数 L 表示棋盘的大小，整个棋盘大小为  L×L；
• 第二行和第三行分别包含一对整数 (x,y)(x,y)，表示骑士的起始点和终点。假设对于每一个骑士，起始点和终点均合理。

输出格式

对每一个骑士，输出一行一个整数表示需要移动的最小步数。如果起始点和终点相同，则输出 0。

样例

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

5
28
0

数据范围与提示

对于 100\%100% 的数据，有 4<= L<=300 4≤L≤300，保证 0≤x,y≤L−1。

这是一道标准的宽搜题，只要套模板即可。

#include<bits/stdc++.h>
using namespace std;
bool flag[301][301];
int a[101][101];
int dy[9]={0,-1,-2,-1,-2,1,2,1,2};
int dx[9]={0,2,1,-2,-1,-2,-1,2,1};
int l;
struct note
{
    int x;
    int y;
    int step;
}que[100010];
void bfs(int sx,int sy,int ex,int ey)
{
    int nx,ny;
    int head=1,tail=1;
    memset(flag,0,sizeof(flag));
    flag[sx][sy]=1;
    que[tail].x=sx;
    que[tail].y=sy;
    que[tail].step=0;
    tail++;
    while(head<tail)
    {
        int x=que[head].x;
        int y=que[head].y;
        int step=que[head].step;
        if (x==ex&&y==ey)
        {
            cout<<step<<endl;
            break;
        }
        for (int i=1;i<=8;i++)
        for (int j=1;j<=8;j++)
        {
            nx=x+dx[i];
            ny=y+dy[i];
            if (nx>=0&&nx<l&&ny>=0&&ny<l&&flag[nx][ny]==0)
            {
                flag[nx][ny]=1;
                que[tail].x=nx;
                que[tail].y=ny;
                que[tail].step=step+1;
                tail++;
            }
        }
        head++;
    }
}
int main()
{
    int n,sx,sy,ex,ey;
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        
        cin>>l;
        cin>>sx>>sy>>ex>>ey;
        bfs(sx,sy,ex,ey);
     }
    return 0;
}

此题还有一种更加简便也出错较少的方法，就是用STL，鉴于本人掌握还不是很熟练，代码可能有很多缺漏（求生欲）

（tip：用万能头文件就不可以用STL）

#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
char s1[5],s2[5];
struct node
{
    int x;
    int y;
    int step;
};
int aa[10][10];
int d[8][2]= {{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};
int ex,ey;
int judge(int x,int y)
{
    if(x>=0&&y>=0&&x<8&&y<8&&!aa[x][y])
        return 1;
    else
        return 0;
}
int bfs()
{
   int i;
   queue<node>q;
   node p,a;
   p.x=s1[0]-'a';
   p.y=s1[1]-'1';
   p.step=0;
   ex=s2[0]-'a';
   ey=s2[1]-'1';
   aa[p.x][p.y]=1;
   q.push(p);
   while(!q.empty())
   {
       a=q.front();
       if(a.x==ex&&a.y==ey)
           return a.step;
       for(i=0;i<8;i++)
       {
           node b;
           b=a;
           b.x+=d[i][0];
           b.y+=d[i][1];
           if(judge(b.x,b.y))
           {
               b.step++;
               aa[b.x][b.y]=1;
               q.push(b);
           }
       }
       q.pop();
   }
}
int main()
{
    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%s%s",s1,s2);
        bfs();
        memset(aa,0,sizeof(aa));
        memset(s1,0,sizeof(s1));
        memset(s2,0,sizeof(s2));
    }
     return 0;
 }