# zju 1091

// Traveling Knight Problem
#include "stdafx.h"
#include <string>
#include <string.h>
#include<iostream>
#include <queue>
using  namespace std;
int a[8][8];//棋盘
int MAP[8][2] = { { 2, 1 }, { 2, -1 }, { -2, 1 }, { -2, -1 }, { 1, 2 }, { -1, 2 }, { -1, -2 }, { 1, -2 } };//8个方向
typedef struct
{
int x;
int y;
int moves;
} NodeStru;
NodeStru Start, End,temp;
void bfs(queue<NodeStru>knight)
{
int x, y;
while (!knight.empty())
{
temp = knight.front();
knight.pop();
if (temp.x == End.x&&temp.y == End.y)
break;
for (int i = 0; i < 8; i++)
{
x = temp.x + MAP[i][0];
y = temp.y + MAP[i][1];
if (x >= 0 && x <8 && y >= 0 && y <8 &&!a[x][y])
{
Start.x = x, Start.y = y;
Start.moves = temp.moves + 1;
knight.push(Start);
a[x][y] = 1;//走过了
}
}
}
}
int main()
{
queue<NodeStru>knight;
string s1, s2;
//char s1[2], s2[2];
while (cin>>s1>>s2)
{

if(s1==s2)// (strcmp(s1,s2) == 0)
{
cout << "To get from " << s1 << " to "<<s2 << " takes 0 knight moves." << endl;
}
else
{
memset(a, 0, sizeof(a));
Start.x = s1[0] - 'a';
Start.y = s1[1] - 49;
a[Start.x][Start.y] = 1;
Start.moves = 0;
End.x = s2[0] - 'a';
End.y = s2[1] - 49;
///////////////////////////////////////////////
//入列
knight.push(Start);
bfs(knight);
cout << "To get from " << s1 << " to " << s2 << " takes "<<temp.moves<<" knight moves." << endl;

}

while (!knight.empty())
{
knight.pop();
}//记得清空栈！
}

}

zju 1091