BFS广度优先搜索，在处理问题时，优先考虑更多的机会，而不是像DFS那样优先走一条路，再回溯

BFS基于队列实现，目的是把可能的解放在同一层处理，即BFS队列中至多只有两层的解

考虑完前一层可能的解后，再考虑下一层的解。把当前解的后续解再放到队列尾部。

img

如上图中，BCDE处在同一层考虑，那么考虑到 B 的后续解时，把FGH 放在 CDE 后面，即CDEFGH ，基于队列实现。

BFS每一层只往下走一步，当这一步的所有情况考虑完后，再考虑下一步的解

这里以洛谷P1443为例：

通过BFS解决问题，首先要引入队列这一数据结构

#include <queue>

处理坐标，这里使用构造结构体的方法，得到横纵坐标

struct pos {
    int x, y;
};

定义队列，存储我们当前考虑的点（坐标位置）

queue<pos> p;

存储地图，一般分为已访问路径的图和存路径的图

int map[405][405], ans[405][405];

向量变量，本题中，马可走 “日” 字，则向量如下

int dx[] = { 1,2,2,1,-1,-2,-2,-1 };
int dy[] = { 2,1,-1,-2,-2,-1,1,2 };

BFS函数的写法：

void bfs(int sx, int sy) {
    memset(ans, -1, sizeof(ans));
    p.push({ sx,sy });
    ans[sx][sy] = 0;
    map[sx][sy] = 1;
    while (!p.empty()) {
        pos t = p.front();
        p.pop();
        for (int i = 0; i < 8; i++) {
            int tx = t.x + dx[i], ty = t.y + dy[i];
            if (check(tx, ty)) {
                p.push({ tx,ty });
                map[tx][ty] = 1;
                ans[tx][ty] = ans[t.x][t.y] + 1;
            }
        }
    }
}

其中，我们先使 ans 数组的值全部初始化为 -1 即一开始所有的点走还没考虑（都走不到）。

将出发点 sx,sy 放进队列，从这个点开始考虑存在的解。

赋值 ans[sx][sy],map[sx][sy] ，初始时，出发点能够走到（走 $0$ 步），且已经被走过。

当队列不空时，使用向量变量，计算下一步的位置。

check 函数检查下一步的位置是否合法

int check(int x, int y) {
    if (x<1 || x>n || y<1 || y>m) return 0;//越界非法
    if (map[y]) return 0;//走到已走过的位置上非法
    return 1;
}

判断合法后，标记这个位置已经走到过 map[tx][ty] = 1 ，且走到这个位置的步数为走到上一个点的步数加 $1$ 步，ans[tx][ty] = ans[t.x][t.y] + 1 。

最后根据题意，输出我们的所有路径的地图即可

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        printf("%d ", ans[i][j]);
    }
    printf("\n");
}

完整代码：

#define _CRT_SECURE_NO_WARNINGS 
#include <stdio.h>
#include <queue>
#include <cstring>
#include <stdlib.h>
using namespace std;

struct pos {
    int x, y;
};

int n, m, sx, sy;
queue<pos> p;
int map[405][405], ans[405][405];
int dx[] = { 1,2,2,1,-1,-2,-2,-1 };
int dy[] = { 2,1,-1,-2,-2,-1,1,2 };

int check(int x, int y) {
    if (x<1 || x>n || y<1 || y>m) return 0;
    if (map[y]) return 0;
    return 1;
}

void bfs(int sx, int sy) {
    memset(ans, -1, sizeof(ans));
    p.push({ sx,sy });
    ans[sx][sy] = 0;
    map[sx][sy] = 1;
    while (!p.empty()) {
        pos t = p.front();
        p.pop();
        for (int i = 0; i < 8; i++) {
            int tx = t.x + dx[i], ty = t.y + dy[i];
            if (check(tx, ty)) {
                p.push({ tx,ty });
                map[tx][ty] = 1;
                ans[tx][ty] = ans[t.x][t.y] + 1;
            }
        }
    }
}



int main()
{
    scanf("%d %d %d %d", &n, &m, &sx, &sy);
    bfs(sx, sy);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            printf("%d ", ans[i][j]);
        }
        printf("\n");
    }
    return 0;
}