hdu 1372 Knight Moves 解题报告

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1372

        题目的意思是，在一个棋盘里，给出两点a和b，计算a到b的最小步数。玩过象棋的人应该都知道，“马”是走“日”的，这里的走法就是按“马”的走法来走。假设给出的点是（0，0），它下一步只能有8个选择，也就是（1， 2），（1，-2），（-1，2），（-1，-2），（2，1），（2，-1），（-2，1），（-2，-1）。

       这里还有两点要注意：1、输入的字符a-h要化成整型，以便在棋盘里构图。2、最终，每一个knight[i][j]保存的都是最少的步数，否则会递归地找到最少的move数

#include <iostream>
using namespace std;

int knight[8][8];
int x[] = {1, 1, -1, -1, 2, 2, -2, -2};   //存储8个方向的点，每次用的时候x，y要同步，因为坐标点是由x、y组成的。                                         
int y[] = {2, -2, 2, -2, 1, -1, 1, -1};

void dfs(int i, int j, int move)
{
    if (i < 0 || j < 0 || i > 7 || j > 7 || move >= knight[i][j]) //越界或统计的步数不小于knight[i][j]存储的步数则返回，说明knight[i][j]存储的步数不是最少的，继续递归找
        return;
    int k;
    knight[i][j] = move;        //保存当前的move，但有可能不是最优的move 
    for (k = 0; k < 8; k++)
    {
        dfs(i+x[k], j+y[k], move+1); //递归直到每一个knight[i][j]存储的步数最少，move作为计数器每次调用要+1
    }
}

int main()
{
    char a[5], b[5];
    while (scanf("%s%s", a, b) != EOF)
    {
        memset(knight, 100, sizeof(knight));  //对knight的每个点赋予足够大的步数
        dfs(a[1]-'1', a[0]-'a', 0);       //字母代表列，数字代表行，都要化成整型（dfs的形参是整型）
        printf("To get from %s to %s takes %d knight moves.\n", a, b, knight[b[1]-'1'][b[0]-'a']); //输出的是到b点的最少步数
    }
    return 0;
}