# 杭电ACM1372——Knight Moves~BFS

www.MyException.Cn  网友分享于：2015-08-24  浏览：0次

```#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int map[9][9];
int xy[8][2] = {-2, -1, -1, -2, 1, -2, 2, -1, 2, 1, 1, 2, -1, 2, -2, 1};   //八个方向
struct Data            //队列的节点
{
int x, y;
int count;
};

int BFS(int x, int y)
{
if(map[x][y] == 1)    //特殊情况，两个点相同
return 0;
queue<Data>Q;
Data z, temp;
z.x = x; z.y = y; z.count = 0;
Q.push(z);                   //起点入队
map[x][y] = -1;
while(!Q.empty())
{
temp = Q.front();
int tx = temp.x;
int ty = temp.y;
Q.pop();
for(int i = 0; i < 8; i++)        //八个方向各判断一次
{
x = tx + xy[i][0];
y = ty + xy[i][1];
if(x >= 0 && x < 8 && y >= 0 && y < 8 && map[x][y] >= 0)//判断是否符合
{
z.x = x;
z.y = y;
z.count = temp.count + 1;
if(map[x][y] == 1)                           //标记为1 的是终点，返回步数
return z.count;
Q.push(z);
map[x][y] = -1;                              //走过的标记为 -1
}
}
}
}

int main()
{
char str1[4], str2[4];
int x, y;
while(cin >> str1 >> str2)
{
memset(map, 0, sizeof(map));            //初始化为0
x = str1[1] - '1';
y = str1[0] - 'a';
map[str2[1] - '1'][str2[0] - 'a'] = 1;       //终点位置
int ans = BFS(x, y);
cout << "To get from " << str1 << " to " << str2 << " takes " << ans << " knight moves." << endl;
}
return 0;
}```