一本通-1330：【例8.3】最少步数（经典BFS）

【题目描述】 在各种棋中，棋子的走法总是一定的，如中国象棋中马走“日”。有一位小学生就想如果马能有两种走法将增加其趣味性，因此，他规定马既能按“日”走，也能如象一样走“田”字。他的同桌平时喜欢下围棋，知道这件事后觉得很有趣，就想试一试，在一个（100×100）的围棋盘上任选两点A、B，A点放上黑子，B点放上白子，代表两匹马。棋子可以按“日”字走，也可以按“田”字走，俩人一个走黑马，一个走白马。谁用最少的步数走到左上角坐标为(1,1)的点时，谁获胜。现在他请你帮忙，给你A、B两点的坐标，想知道两个位置到（1,1）点可能的最少步数。

【输入】 A、B两点的坐标。

【输出】 最少步数。

【输入样例】 12 16 18 10

【输出样例】 8 9

---

用grid[i][j]表示从1,1出发到达i,j所需的最小步数，显然grid[1][1] = 0，将其余部分初始化为INT_MAX表示初始不可到达，马走日共8种走法，走田共4种走法，不断更新grid[i][j]的值，如果产生更新，就加入到队列里面。

#include <bits/stdc++.h>

using namespace std;
struct Node
{
    int row, col;
    Node(int x, int y): row(x), col(y) {}
};

int m = 100, n = 100;
vector<vector<int> > grid(101, vector<int>(101, INT_MAX));
int direction[12][2] = {{-1, 2}, {-2, 1}, {-1, -2}, {-2, -1},
                        {1, 2}, {2, 1}, {1, -2}, {2, -1},
                        {2, 2}, {2, -2}, {-2, 2}, {-2, -2}};

void BFS()
{
    queue<Node> q;
    q.push(Node(1, 1));
    while (!q.empty()) {
        Node tmp = q.front(); q.pop();
        for (int i = 0; i < 12; ++i) {
            int nextRow = tmp.row + direction[i][0];
            int nextCol = tmp.col + direction[i][1];
            if (1 <= nextRow && nextRow <= 100 && 1 <= nextCol && nextCol <= 100 
                && grid[nextRow][nextCol] > grid[tmp.row][tmp.col] + 1) {
                grid[nextRow][nextCol] = grid[tmp.row][tmp.col] + 1;
                q.push(Node(nextRow, nextCol));
            }
        }
    }
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    grid[1][1] = 0;
    BFS();
    int x, y;
    while (cin >> x >> y) {
        cout << grid[x][y] << endl;
    }

    return 0;
}