2.2 数据结构之 队列与BFS (C语言版）
编程总结
在刷题之前需要反复练习的编程技巧，尤其是手写各类数据结构实现，它们好比就是全真教的上乘武功。
本学习来自 leetcode，整理提炼.
https://leetcode-cn.com/leetbook/read/queue-stack/kyozi/
广度优先搜索（BFS）是一种遍历或搜索数据结构（如树或图）的算法。
如前所述，我们可以使用 BFS 在树中执行层序遍历。
我们也可以使用 BFS 遍历图。例如，我们可以使用 BFS 找到从起始结点到目标结点的路径，特别是最短路径。
我们可以在更抽象的情景中使用 BFS 遍历所有可能的状态。在这种情况下，我们可以把状态看作是图中的结点，而以合法的过渡路径作为图中的边。
1. 解释队列和BFS的关系.
广度优先搜索（BFS）的一个常见应用是找出从根结点到目标结点的最短路径。
这里我们提供一个示例来说明如何使用 BFS 来找出根结点 A 和目标结点 G 之间的最短路径。
- 结点的处理顺序是什么？
在第一轮中，我们处理根结点。在第二轮中，我们处理根结点旁边的结点；在第三轮中，我们处理距根结点两步的结点；等等等等。
与树的层序遍历类似，越是接近根结点的结点将越早地遍历。
如果在第 k 轮中将结点 X 添加到队列中，则根结点与 X 之间的最短路径的长度恰好是 k。也就是说，第一次找到目标结点时，你已经处于最短路径中。
- 队列的入队和出队顺序是什么？
如上面的动画所示，我们首先将根结点排入队列。然后在每一轮中，我们逐个处理已经在队列中的结点，并将所有邻居添加到队列中。值得注意的是，新添加的节点不会立即遍历，而是在下一轮中处理。
结点的处理顺序与它们添加到队列的顺序是完全相同的顺序，即先进先出（FIFO）。这就是我们在 BFS 中使用队列的原因。
广度优先搜索 - 模板
之前，我们已经介绍了使用 BFS 的两个主要方案：遍历或找出最短路径。通常，这发生在树或图中。正如我们在章节描述中提到的，BFS 也可以用于更抽象的场景中。在本文中，我们将为你提供一个模板。然后，我们在本文后提供一些习题供你练习。在特定问题中执行 BFS 之前确定结点和边缘非常重要。通常，结点将是实际结点或是状态，而边缘将是实际边缘或可能的转换。
286. 墙与门
待分析。。。。。on 20210418.
// 反向思维，从门开始找
typedef struct {
int x;
int y;
int step;
} WallsStepStr;
void wallsAndGates(int **rooms, int roomsSize, int *roomsColSize) {
if ((roomsSize == 0) || (*roomsColSize == 0)) {
return;
}
int row = roomsSize;
int col = *roomsColSize;
WallsStepStr *wallStep = (WallsStepStr *)malloc(sizeof(WallsStepStr) * row * col);
int stepX[] = { 0, 0, -1, 1 }; // Up Down Left Right of X-Axis
int stepY[] = { 1, -1, 0, 0 }; // Up Down Left Right of Y-Axis
int i, j;
int head = 0;
int tail = 0; // 甚至都不用考虑队列满的情况
// 找门
for (i = 0; i < row; i++) {
for (j = 0; j < col; j++) {
if (rooms[i][j] == 0) { // 0 为门
wallStep[tail].x = i;
wallStep[tail].y = j;
wallStep[tail++].step = 0; // 进队列
}
}
}
// 以门为起点开始BFS
while (head != tail) {
// 先出个门
int xx = wallStep[head].x;
int yy = wallStep[head].y;
int curStep = wallStep[head++].step; // 出队列
for (i = 0; i < 4; i++) {
int xTmp = xx + stepX[i];
int yTmp = yy + stepY[i];
if ((xTmp >= 0) && (xTmp < row) && (yTmp >= 0) && (yTmp < col) && (rooms[xTmp][yTmp] == INT_MAX)) {
rooms[xTmp][yTmp] = curStep + 1; // 这里如果将rooms[xTmp][yTmp]改为curStep+1后，
// 下一次别的门遍历到这个rooms就不会进入这个判断了，所以先到先得，
// 先遍历到这个rooms的门就是这个rooms能到达的最近的门
wallStep[tail].x = xTmp;
wallStep[tail].y = yTmp;
wallStep[tail++].step = curStep + 1; // 将当前出队的元素相邻元素入队
}
}
}
}