题目

思路

• 经典的BFS，因为题目需要求搜索最短路径，所以下意识想到BFS
• 将一个坐标作为一个节点去建立树，重复的节点就不放到树当中了，最少的次数能跳到某坐标，那么该次数就是坐标的层数。
• 通过map<pair, int>的结构去记录每个坐标的次序，同时防止重复遍历。
• printf如何保证左对齐，需要留心一下。

  代码

  ```cpp

  include

  include

  include

using namespace std;

int main() { map, int> recordSteps; int n, m, x, y; cin >> n >> m >> x >> y;

// 题目从1开始计数的
x--;
y--;
queue<pair<int, int>> q;
q.push(make_pair(x, y));
recordSteps[make_pair(x, y)] = 0;
int dx[8] = {1, 2, -1, -2, 1, 2, -1, -2};
int dy[8] = {2, 1, -2, -1, -2, -1, 2, 1};
while (!q.empty()) {
    for (int i = 0, q_size = q.size(); i < q_size; i++) {
        pair<int, int> cur = q.front();
        q.pop();
        for (int j = 0; j < 8; j++) {
            int x = cur.first, y = cur.second;
            int nx = cur.first + dx[j];
            int ny = cur.second + dy[j];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && !recordSteps.count(make_pair(nx, ny))) {
                q.push(make_pair(nx, ny));
                recordSteps[make_pair(nx, ny)] = recordSteps[make_pair(x, y)] + 1;
            }
        }
    }
}
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        if (recordSteps.count(make_pair(i, j)) == 0) {
            printf("%-5d", -1);
        } else {
            printf("%-5d", recordSteps[make_pair(i, j)]);
        }
    }
    cout << endl;
}
return 0;

} ```