HDU 1372 Knight Moves 解题报告

        这道题的意思就是在国际象棋的棋盘上，一匹马从一个位置跳到另一个位置最少需要多少步，这里有个常识需要知道，那就是马是可以踏遍棋盘的每一个格子的。所以很自然的用广度搜索。需要注意的是。马在x、y位置上的变化最大为2，所以可以在棋盘周围加上两层不能走的地方，用false标记。
AC代码如下：
（由于我是新手一枚，所以代码很长，而且没用STL，自己写的队列。这道题的Discuss里面有比较短的代码）

#include <iostream>
using namespace std;
const int P = (int)('a' - '1' + '0'); //小写字母和数字的ASCII差值
struct ch{
    bool mark;
    int d;
}ChessBoard[12][12]; //棋盘


struct pos{
    int x;
    int y;
}startPos, destinationPos; //起始点

struct pos QUEUE[64]; //创建队列
void ENQUEUE(int x, int y); //入队
struct pos DEQUEUE(void); //出队
struct pos * head = QUEUE; //队头
struct pos * tail = QUEUE; //队尾

int bfs(void); //BFS

int main()
{
    for(int i = 0; i < 12; ++i)
    {
        ChessBoard[i][0].mark = false;
        ChessBoard[i][1].mark = false;
        ChessBoard[i][10].mark = false;
        ChessBoard[i][11].mark = false;
    }
    for(int i = 0; i < 2; ++i)
    {
        for(int j = 2; j < 10; ++j)
            ChessBoard[i][j].mark = false;
    }
    for(int i = 10; i < 12; ++i)
    {
        for(int j = 2; j < 10; ++j)
            ChessBoard[i][j].mark = false;
    }

    char location1[3];
    char location2[3];
    while(cin >> location1 >> location2)
    {
        for(int i = 2; i < 10; ++i)
        {
            for(int j = 2; j < 10;j++)
            {
                ChessBoard[i][j].mark = true;
                ChessBoard[i][j].d = 0;
            }
        }
        head = QUEUE;
        tail = QUEUE;
        startPos.x = (int)(location1[0] - P) + 1;
        startPos.y = (int)(location1[1] - '0') + 1;
        ChessBoard[startPos.x][startPos.y].mark = false;
        destinationPos.x = (int)(location2[0] - P) + 1;
        destinationPos.y = (int)(location2[1] - '0') + 1;
        //cout << startPos.x << " " << startPos.y << endl;
        //cout << destinationPos.x << " " << destinationPos.y << endl;
        int steps = bfs();
        cout << "To get from " << location1 << " to " << location2 << " takes " << steps << " knight moves.\n";
    }
    return 0;
}

int bfs(void)
{
    ENQUEUE(startPos.x, startPos.y);
    struct pos s;
    while(1)
    {
        s = DEQUEUE();
        if(s.x == destinationPos.x && s.y == destinationPos.y)
            return ChessBoard[s.x][s.y].d;
        if(true == ChessBoard[s.x - 2][s.y - 1].mark)
        {
            ChessBoard[s.x - 2][s.y - 1].mark = false;
            ChessBoard[s.x - 2][s.y - 1].d = ChessBoard[s.x][s.y].d + 1;
            ENQUEUE(s.x - 2, s.y - 1);
        }
        if(true == ChessBoard[s.x - 1][s.y - 2].mark)
        {
            ChessBoard[s.x - 1][s.y - 2].mark = false;
            ChessBoard[s.x - 1][s.y - 2].d = ChessBoard[s.x][s.y].d + 1;
            ENQUEUE(s.x - 1, s.y - 2);
        }
        if(true == ChessBoard[s.x + 1][s.y - 2].mark)
        {
            ChessBoard[s.x + 1][s.y - 2].mark = false;
            ChessBoard[s.x + 1][s.y - 2].d = ChessBoard[s.x][s.y].d + 1;
            ENQUEUE(s.x + 1, s.y - 2);
        }
        if(true == ChessBoard[s.x + 2][s.y - 1].mark)
        {
            ChessBoard[s.x + 2][s.y - 1].mark = false;
            ChessBoard[s.x + 2][s.y - 1].d = ChessBoard[s.x][s.y].d + 1;
            ENQUEUE(s.x + 2, s.y - 1);
        }
        if(true == ChessBoard[s.x + 2][s.y + 1].mark)
        {
            ChessBoard[s.x + 2][s.y + 1].mark = false;
            ChessBoard[s.x + 2][s.y + 1].d = ChessBoard[s.x][s.y].d + 1;
            ENQUEUE(s.x + 2, s.y + 1);
        }
        if(true == ChessBoard[s.x + 1][s.y + 2].mark)
        {
            ChessBoard[s.x + 1][s.y + 2].mark = false;
            ChessBoard[s.x + 1][s.y + 2].d = ChessBoard[s.x][s.y].d + 1;
            ENQUEUE(s.x + 1, s.y + 2);
        }
        if(true == ChessBoard[s.x - 1][s.y + 2].mark)
        {
            ChessBoard[s.x - 1][s.y + 2].mark = false;
            ChessBoard[s.x - 1][s.y + 2].d = ChessBoard[s.x][s.y].d + 1;
            ENQUEUE(s.x - 1, s.y + 2);
        }
        if(true == ChessBoard[s.x - 2][s.y + 1].mark)
        {
            ChessBoard[s.x - 2][s.y + 1].mark = false;
            ChessBoard[s.x - 2][s.y + 1].d = ChessBoard[s.x][s.y].d + 1;
            ENQUEUE(s.x - 2, s.y + 1);
        }
    }
}

void ENQUEUE(int x, int y)
{
    tail->x = x;
    tail->y = y;
    ++tail;
}

struct pos DEQUEUE(void)
{
    struct pos s;
    s.x = head->x;
    s.y = head->y;
    ++head;
    return s;
};