带变体的广度优先搜索（BFS）：二进制矩阵最短路径问题

嘿，这道题我之前在面试准备的时候研究过，正好给你详细拆解下思路！

这是典型的无权图最短路径问题，BFS是最优解——它按层遍历的特性，保证第一次到达终点时的步数就是最短路径长度。

先把你给出的一维矩阵转换成对应3x3的二维结构（毕竟起点(0,0)、终点(2,0)对应3行）：

[
 [1, 1, 0],
 [0, 1, 1],
 [1, 1, 1]
]

BFS核心步骤： #

• 初始化队列，将起点(0,0)入队，记录当前步数为0，同时用二维数组标记已访问的位置（避免重复遍历）。
• 每次从队列取出一个位置：
  • 如果是终点(2,0)，直接返回当前步数。
  • 否则遍历上下左右四个方向的相邻位置，若位置在矩阵范围内、值为1且未被访问，就标记为已访问并入队，步数加1。

对应这个矩阵，最短路径是(0,0) → (0,1) → (1,1) → (1,2) → (2,2) → (2,1) → (2,0)，总共5次移动，也就是答案5。

暴力解法确实能解决问题，但如果矩阵很大、0的数量多，重复跑BFS会导致时间复杂度飙升（O(kmn)，k是0的数量，m、n是矩阵行列数），完全不适合面试里的大数据量场景。这里推荐带状态的BFS（三维访问标记），只需要一次BFS就能搞定，效率拉满。

核心思路 #

把「是否使用过魔法棒」作为状态的一部分，每个位置维护两种状态：

• 未使用魔法棒时到达该点的最短步数
• 已使用魔法棒时到达该点的最短步数

这样我们只需要一次BFS，就能覆盖所有“用/不用魔法棒”的可能路径，不会漏掉最优解。

具体实现步骤 #

1. 定义状态数组：用三维数组visited[m][n][2]，其中visited[i][j][0]表示没使用魔法棒到达(i,j)的最短步数，visited[i][j][1]表示使用过魔法棒的情况，初始值设为无穷大或-1（表示未访问）。
2. 队列元素结构：队列里存(x, y, used, steps)，used是0或1（0=没用到魔法棒，1=已用），steps是当前步数。
3. BFS遍历流程：
   • 起点入队：(0, 0, 0, 0)，同时标记visited[0][0][0] = 0。
   • 每次取出队列元素，遍历四个方向的相邻点(nx, ny)：
     • 如果(nx, ny)是终点，直接返回steps + 1（因为移动到终点需要一步）。
     • 如果matrix[nx][ny] == 1：
       • 若visited[nx][ny][used]未被访问，就更新为steps + 1，并将(nx, ny, used, steps + 1)入队。
     • 如果matrix[nx][ny] == 0且used == 0（还没使用魔法棒）：
       • 若visited[nx][ny][1]未被访问，更新为steps + 1，并将(nx, ny, 1, steps + 1)入队。
4. 终止条件：遍历完队列仍未找到终点，说明路径不可达。

为什么这个方法更优？ #

• 时间复杂度降到了O(m*n)，每个位置最多被访问两次（两种状态），比暴力法的重复BFS高效太多。
• 状态记录完整，确保第一次到达终点的路径就是最短的（BFS的层序遍历特性保证）。

比如题目中翻转(1,0)的场景，BFS会在处理(0,0)时，发现(1,0)是0且未用魔法棒，于是将(1,0, 1, 1)入队；后续处理这个元素时，发现下方就是终点(2,0)，直接返回1 + 1 = 2（如果是按节点数算就是3个节点，对应你说的“3步”表述）。

内容的提问来源于stack exchange，提问作者ZestyZest