AI Fantasy
Don't ever underestimate a heart of the champion!
BFS,AC后感觉很爽
#include<iostream>
#include
<memory>
#include
<queue>
using namespace std;

int dir[8][2= {{2,1},{2,-1},{-2,1},{-2,-1},{1,2},{-1,2},{-1,-2},{1,-2}
};    
//八个可能方向

int flag[8][8]; //标记棋盘中一个点是否已经被踏过

struct  node
{
    
int x,y,step; //棋盘点的坐标和几次可达的信息
};

int main()
{
     
char a,b,c,d;
     node N,P;
     queue
<node> Q;
     memset(flag,
0,64);
     cin
>>a>>b>>c>>d;
     
int r1=a-'a';
     
int c1=b-'1';
     
int r2=c-'a';
     
int c2=d-'1';
     N.x
=r1;N.y=c1;N.step=0;
     Q.push(N);     
//初始节点入队
     flag[r1][c1]=1;  
     
while(!Q.empty())
     {
          N
=Q.front();Q.pop();  //出队
          if(N.x==r2&&N.y==c2)  //达到目的,则跳出
             break;
          
for(int i=0;i<8;i++)   //八方向搜索
          {
               
int tx=N.x+dir[i][0];
               
int ty=N.y+dir[i][1];
               
if(tx>=0&&tx<8&&ty>=0&&ty<8&&flag[tx][ty]==0//看是否在棋盘内和是否已经被踏过
               {
                    P.x
=tx;P.y=ty;P.step=N.step+1;
                    Q.push(P);
                    flag[tx][ty]
=1;  //标记为被踏过
               }
          }
    }
    cout
<<"To get from "<<a<<b<<" to "<<c<<d<<' ';
    cout
<<"takes "<<N.step<<" knight moves."<<endl;
}


posted on 2007-06-02 23:55 AIFantasy 阅读(281) 评论(0)  编辑 收藏 引用 所属分类: ACM
只有注册用户登录后才能发表评论。