题解 | 小红走象步

#include <iostream>
#include <queue>
#include <vector>
#define PII pair<int,int>
#define x first
#define y second
using namespace std;

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    // 0：未访问或者步数为0
    // -1：有兵
    // other：到该坐标的最小步数
    vector<vector<int>> map(n + 1, vector<int>(m + 1, 0));

    while (k--) {
        int x, y;
        cin >> x >> y;
        // 将兵的位置标记为-1
        map[x][y] = -1;
    }
    int x0, y0, xt, yt;
    cin >> x0 >> y0 >> xt >> yt;

    // 目标不在田字格顶点上
    if ((abs(x0 - xt) % 2 != 0 || abs(y0 - yt) % 2 != 0) || (x0 == xt &&
            abs(xt - x0) % 4 != 0) || (y0 == yt && abs(yt - y0) % 4 != 0)) {
        cout << -1 << endl;
        return 0;
    }

    queue<PII> qu;
    qu.push({x0, y0});
    while (!qu.empty()) {
        PII cur = qu.front();
        qu.pop();

        int dx[4] = {+2, -2, +2, -2};
        int dy[4] = {-2, +2, +2, -2};
        int dcx[4] = {+1, -1, +1, -1};
        int dcy[4] = {-1, +1, +1, -1};
        for (int i = 0; i < 4; i++) {
            // 范围检测
            if (cur.x + dx[i] < 1 || cur.y + dy[i] < 1 || cur.x + dx[i] > n ||
                    cur.y + dy[i] > m) {
                continue;
            }
            // 路上没有障碍且目标未访问
            if (map[cur.x + dcx[i]][cur.y + dcy[i]] != -1 &&
                    map[cur.x + dx[i]][cur.y + dy[i]] <= 0) {
                qu.push({cur.x + dx[i], cur.y + dy[i]});
                map[cur.x + dx[i]][cur.y + dy[i]] = map[cur.x][cur.y] + 1;
                // 到达目标点，终止循环
                if (cur.x + dx[i] == xt && cur.y + dy[i] == yt) {
                    while (!qu.empty()) {
                        qu.pop();
                    }
                    break;
                }
            }
        }
    }
    // 如果步数为0，表示无法到达。
    cout << (map[xt][yt] == 0 ? -1 : map[xt][yt]) << endl;
}