C++——跳馬問題（廣搜）

跳馬

時限：1000ms 記憶體限制：10000K 總時限：3000ms

描述：

在國際象棋中，馬的走法與中車象棋類似，即俗話說的“馬走日”，下圖所示即國際象棋中馬（K）在一步能到達的格子（其中黑色的格子是能到達的位置）。

現有一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;

int cx,cy,gx,gy;
int a[201][201]={0};
int step[201][201];
//馬走的方向所對應的行列變化 
int b[8]={-2,-2,-1,-1,1,1,2,2};
int c[8]={-1,1,-2,2,-2,2,-1,1};

//結構體内定義隊列 
struct add
{
 queue<int>q1;
 queue<int>q2;
}add;

int search(int x,int y);

int main()
{
 int n,i,j,k=0;
 cin>>n;
 int ans[n];
 while(k<n)
 {
  cin>>cx>>cy>>gx>>gy;
  //初始化 
  step[cx][cy]=0;
  a[cx][cy]=1;
  add.q1.push(cx);
  add.q2.push(cy);
  ans[k++]=search(cx,cy);
  //清空棋盤和隊列，防止下一組測試受到影響 
  for(i=0;i<201;i++)
     {
      for(j=0;j<201;j++)
      {
       a[i][j]=0;
       step[i][j]=0; 
      }
     }
     while(!add.q1.empty())
     {
      add.q1.pop();
     }
     while(!add.q2.empty())
        {
      add.q2.pop();
     }
 }
 for(i=0;i<n;i++)
 {
  cout<<ans[i]<<endl;
 } 
 return 0;
}

int search(int x,int y)
{
 int xt,yt,e,f,i;
 while(1)
 {
  e=add.q1.front();
  add.q1.pop();
  f=add.q2.front();
     add.q2.pop();
  for(i=0;i<8;i++)
     {
       xt=e+b[i];
      yt=f+c[i];
      if(xt==gx&&yt==gy)
      {
        return(step[e][f]+1);
      }
      if(xt<1||xt>200||yt<1||yt>200) continue;//剪枝數組越界的情況 
      if(a[xt][yt]==0)
      {//處理下一組可能的情況 
       a[xt][yt]=1;
       step[xt][yt]=step[e][f]+1;
       add.q1.push(xt);
       add.q2.push(yt);
      }
     }
 }
}