本文共 2431 字，大约阅读时间需要 8 分钟。

图片我不会放进来 图片就是马走日 当前位置可以跳到八个新状态 玩没玩过象棋都懂吧。。。。题目和代码如下

现有一200*200大小的国际象棋棋盘，棋盘中仅有一个马，给定马的当前位置（S）和目标位置（T），求出马最少需要多少跳才能从当前位置到达目标位置。

输入：

本题包含多个测例。输入数据的第一行有一个整数N（1<=N<=1000），表示测例的个数，接下来的每一行有四个以空格分隔的整数，分别表示马当前位置及目标位置的横、纵坐标C（x,y）和G（x,y）。坐标由1开始。

输出：

对于每个测例，在单独的一行内输出一个整数，即马从当前位置跳到目标位置最少的跳数。

输入样例：

21 1 2 11 5 5 1

输出样例：

34

#include<iostream>

#include<queue>

using namespace std ;

queue<int>x ;//横坐标队列

queue<int>y ;//纵坐标队列   int step[201][201] = {0} ;//计算步数 本身带有标记的作用 int n ;//n个测例 int c[1000] = {0} ;//存一下n个测例的答案 int x1 , y1 , x2 , y2 ;//起点和终点的坐标

void input() ;//输入起点和终点

int bfs() ;//广搜找答案 int canmoveto(int a , int b) ;//判断是否可以跳步 1.不越界 2.不重复 void clean() ; //多个测例每次使用前上一次需要清空

int main()

{   int i ;   cin >> n ;   for(i = 1 ; i <= n ; i++)   {    input() ;     c[i] = bfs() ;     clean();//多组数据 需要清空上一次的数据   }   for(i = 1 ; i <= n ; i++)   {    cout << c[i] << endl ;   }   return 0 ; } void input() {  cin >> x1 >> y1 >> x2 >> y2 ; } int bfs() {  x.push(x1) ;//起点入队  y.push(y1) ;//终点入队  step[x1][y1] = 0 ;//起点的步数为0  while(1) //肯定有答案 无限循环找答案 找到就break  {   if(step[x2][y2] != 0)   {    return step[x2][y2] ;    break ;    }   x1 = x.front() ; //访问队首横坐标   x.pop() ; //队首横坐标出队   y1 = y.front() ; //访问队首纵坐标   y.pop() ; //队首纵坐标出队      if(canmoveto (x1 - 1,y1 - 2))//八个状态   {    x.push(x1 - 1) ;    y.push(y1 - 2) ;    step[x1 - 1][y1 - 2] = step[x1][y1] + 1 ;   }   if(canmoveto (x1 - 1,y1 + 2))   {    x.push(x1 - 1) ;    y.push(y1 + 2) ;    step[x1 - 1][y1 + 2] = step[x1][y1] + 1 ;   }   if(canmoveto (x1 + 1,y1 - 2))   {    x.push(x1 + 1) ;    y.push(y1 - 2) ;    step[x1 + 1][y1 - 2] = step[x1][y1] + 1 ;   }   if(canmoveto (x1 + 1,y1 + 2))   {    x.push(x1 + 1) ;    y.push(y1 + 2) ;    step[x1 + 1][y1 + 2] = step[x1][y1] + 1 ;   }   if(canmoveto (x1 - 2,y1 - 1))   {    x.push(x1 - 2) ;    y.push(y1 - 1) ;    step[x1 - 2][y1 - 1] = step[x1][y1] + 1 ;   }   if(canmoveto (x1 - 2,y1 + 1))   {    x.push(x1 - 2) ;    y.push(y1 + 1) ;    step[x1 - 2][y1 + 1] = step[x1][y1] + 1 ;   }   if(canmoveto (x1 + 2,y1 - 1))   {    x.push(x1 + 2) ;    y.push(y1 - 1) ;    step[x1 + 2][y1 - 1] = step[x1][y1] + 1 ;   }   if(canmoveto (x1 + 2,y1 + 1))   {    x.push(x1 + 2) ;    y.push(y1 + 1) ;    step[x1 + 2][y1 + 1] = step[x1][y1] + 1 ;   }   } } int canmoveto(int a , int b) {  if(a >= 1 && a <= 200 && b >= 1 && b <= 200 && step[a][b] == 0 )  {   return 1 ;  }  else //这个else让我找了三个多小时的bug 我为了省事没写else 然后就呵呵了 老铁们别偷懒  {   return 0 ;  } } void clean() //把步数和队列清零 {  int i , j ;  for(i = 1 ; i <= 200 ; i++)//步数清零  {   for(j = 1 ; j <= 200 ; j++)   {    step[i][j] = 0 ;  }  }     while(!x.empty()) // 队首一直出队直到队列为空      {          x.pop();      }      while(!y.empty())      {       y.pop();   } }