广度优先搜索

广度优先搜索（Breadth First Search)：英文缩写为（BFS），是一种用于搜索树或图的算法。从起始节点开始逐层扩展搜索，直到达到目标节点。它以广度的方式探索图中的节点，即先访问离起始节点最近的节点，然后逐渐扩展到距离更远的节点。

广度优先搜索的实现：

1. 将起始节点放入队列中，并将其标记为已访问。
2. 从队首取出一个节点作为当前节点。
3. 遍历当前节点的所有邻居节点：如果邻居节点没有被访问过，则将其放入队列中并标记为已访问。
4. 重复步骤2和3，直到队列为空或找到目标节点。

char mp[N][N];  // 地图
step step[N][N];  // 记录到达某点的最短步数
queue<pair<int, int> > q;  // 辅助广搜的队列
int dir[4][2] = {  // 方向数组  根据需求确定搜索方向
    0, 1,
    0, -1,
    1, 0,
    -1, 0
}

// 步数初始化为-1，在记录步数的同时也可以记录哪些点走过
fill(step[0], step[0] + N * N, -1)

void bfs(int sx, int sy) {
    q.push({sx, sy});  // 起始节点入队
    step[sx][sy] = 0;  // 起点设为0步，也可能是1步，并且达到了标记已访问的作用
    while(!q.empty()) {  // 队列不为空，就要继续搜
        int x = q.front().first;  // 当前节点的x坐标        
        int y = q.front().second;  // 当前节点的y坐标
        q.pop();  // 取出当前节点

        if (x, y) 是终点 {  // 遇到结束条件，如果没有结束条件就把能搜的点都搜完
            // 遇到终点做一些事情，比如最短步数、判断能否到达终点
            break;  // 结束
        }

        for(int i = 0; i < 4; i++) {
            int nx = x + dir[i][0];  // 下一个点的x坐标
            int ny = y + dir[i][1];  // 下一个点的y坐标
            // 如果下一个点越界了 不能走
            // 注意下面两个if要先判断是否越界，才可以访问 
            if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            // 如果下一个点是障碍 或者 下一个点访问过 不能走
            if(mp[nx][ny] 是障碍 || step[nx][ny] != -1) continue; 
            q.push({nx, ny});  // 能走的点就入队
            // 走到下一个点的步数等于这个点的步数+1
            step[nx][ny] = step[x][y] + 1;  
        }
    }
}

特别注意：要在入队时就对节点进行标记，如果在出队时标记，两个点都指向某个未访问的节点时，它会被重复入队。