题目描述

有一个 n×m 的棋盘，在某个点 (x,y) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。

输入格式

输入只有一行四个整数，分别为 n,m,x,y。

输出格式

一个 n×m 的矩阵，代表马到达某个点最少要走几步（左对齐，宽 5 格，不能到达则输出 -1）。

输入输出样例

In 1

3 3 1 1

Out 1

0    3    2    
3    -1   1    
2    1    4

---

这道题最开始接触是在学习dfs的时候

最近学了bfs，老师让我们再做一遍

（他应该不会发现我已经把dfs的做法忘了吧……）

就手撸了一个bfs模板

唯一的区别就是要给区域里的每个点附上值表示第几步走到了这里

地图中-1和表示第几步的数字可以直接代替lock了，省空间

#include <bits/stdc++.h>
using namespace std;

int n, m, x, y, ans[401][401];
int mv[8][2] = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2},
                {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};

struct node {
    int x, y, step;
} que[1000001];

int main() {
    cin >> n >> m >> x >> y;
    memset(ans, -1, sizeof(ans));
    int head = 0, tail = 1;
    que[head].x = x;
    que[head].y = y;
    que[head].step = 0;
    ans[x][y] = 0;
    while (head < tail) {
        int x, y;
        for (int i = 0; i < 8; i++) {
            x = que[head].x + mv[i][0];
            y = que[head].y + mv[i][1];
            if (x > 0 && y > 0 && x <= n && y <= m && ans[x][y] == -1) {
                que[tail].x = x;
                que[tail].y = y;
                que[tail].step = que[head].step + 1;
                ans[x][y] = que[tail].step;
                tail++;
            }
        }
        head++;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < m; j++) {
            cout << left << setw(5) << ans[i][j];
        }
        cout << ans[i][m] << endl;
    }
}

正式比赛还是要记得return 0啊哈哈哈哈

版权所有

许可证：署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0)