Sicily 1936. Knight Moves

/*
【题目来源】
http://soj.me/show_problem.php?pid=1005&cid=567

【题目分析】 
国际象棋棋盘上，给定起点和终点，求出马(knight --!)起点到终点 所需要走的步数

【思路分析】 
打表：构造一个64*64的表格  行和列都为a1,a2……h7,h8  
(i,j)表示从点i到 点j所需要走的最小步数。注意这里的i,j均抽象为一个点，如(1,13) 表示 i = 1 j = 13 也就是 (a1,b5) 

打表的复杂度较高。但打完表后，以后每输入一个测试数据，输出结果的时间复杂度都是O(1). 

唯一要注意的地方是坐标的转换 0表示a1 8表示b1 …… 
*/ 
#include <iostream>
#include <queue>
#include <cstring>
#include <string>
using namespace std;

int s[64][64];
int chess[8][8];

void bfs(int x, int y)//对每一个点(x,y)在棋盘上广搜 求出(x,y) 到棋盘上每一个点所需要走的最小步数 
{
    memset(chess, -1, sizeof(chess));//-1表示未走过 
    
    chess[x][y] = 0;
    
    queue<pair<int, int> > q;
    
    q.push(make_pair(x, y));
    
    while (!q.empty())
    {
        pair<int, int> p = q.front();
        
        q.pop();
        
        int a = p.first, b = p.second;
        
        int current = chess[a][b];
        
        //位于(a,b)的马最多有八个方向可以走 画个图就清楚了
        //当且仅当目标点未超过棋盘范围以及未被走过 
        if (a+2 >= 0 && a+2 < 8 && b-1 >= 0 && b-1 < 8 && chess[a+2][b-1] == -1)
        {
            chess[a+2][b-1] = current + 1;
            
            q.push(make_pair(a+2, b-1));
        }
        if (a+2 >= 0 && a+2 < 8 && b+1 >= 0 && b+1 < 8 && chess[a+2][b+1] == -1)
        {
            chess[a+2][b+1] = current + 1;
                        
            q.push(make_pair(a+2, b+1));
        }
        if (a+1 >= 0 && a+1 < 8 && b+2 >= 0 && b+2 < 8 && chess[a+1][b+2] == -1)
        {
            chess[a+1][b+2] = current + 1;
                        
            q.push(make_pair(a+1, b+2));
        }
        if (a-1 >= 0 && a-1 < 8 && b+2 >= 0 && b+2 < 8 && chess[a-1][b+2] == -1)
        {
            chess[a-1][b+2] = current + 1;
                        
            q.push(make_pair(a-1, b+2));
        }
        if (a-2 >= 0 && a-2 < 8 && b+1 >= 0 && b+1 < 8 && chess[a-2][b+1] == -1)
        {
            chess[a-2][b+1] = current + 1;
                        
            q.push(make_pair(a-2, b+1));
        }
        if (a-2 >= 0 && a-2 < 8 && b-1 >= 0 && b-1 < 8 && chess[a-2][b-1] == -1)
        {
            chess[a-2][b-1] = current + 1;
                        
            q.push(make_pair(a-2, b-1));
        }
        if (a-1 >= 0 && a-1 < 8 && b-2 >= 0 && b-2 < 8 && chess[a-1][b-2] == -1)
        {
            chess[a-1][b-2] = current + 1;
                        
            q.push(make_pair(a-1, b-2));
        }
        if (a+1 >= 0 && a+1 < 8 && b-2 >= 0 && b-2 < 8 && chess[a+1][b-2] == -1)
        {
            chess[a+1][b-2] = current + 1;
                        
            q.push(make_pair(a+1, b-2));
        }
    }
    
    int index1 = x*8+y;//转换坐标 
    
    int index2 = 0;
    
    for (int i = 0; i < 8; ++i)
        for (int j = 0; j < 8; ++j)
            s[index1][index2++] = chess[i][j];//以行的方式填写s数组 
    
}

void init()
{
    for (int i = 0; i < 8; ++i)
    {
        for (int j = 0; j < 8; ++j)
        {
            bfs(i,j);
        }
    }
}

int main()
{
    init();//打表，初始化 
    
    int m;
    
    cin >> m;
    
    while (m--)
    {
        string a, b;
        
        cin >> a >> b;
        
        int index1 = ((a[0]-'a'))*8 + (a[1]-'0')-1;//转换坐标 
        
        int index2 = ((b[0]-'a'))*8 + (b[1]-'0')-1;//转换坐标 
        
        cout << "To get from " << a << " to " << b << " takes " << s[index1][index2] << " knight moves." << endl;
    }
}