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 阅读(294)
评论(0) 编辑 收藏 引用 所属分类:
ＡＣＭ