广度优先搜索
Breadth first search with a twist
给定一个二进制矩阵，其中 0 代表障碍物，1 代表路径，求从给定源到目的地的最小步数（只允许在 4 个方向上遍历）。这是一道典型的 BFS 题。
来源：(0,0) 目的地：(2,0)
1 1 0
0 1 1
1 1 1
答案：5
但是这个问题的下一部分很棘手，你可以用魔杖把一个零变成一个。现在你将如何找到这种情况下的最短路径。
如果我们翻转 (1,0)，我们可以通过 3 步到达目的地。
典型的蛮力解决方案是通过将零变为一来对每个矩阵执行 BFS。我们怎样才能做得更好？
这是在一家受欢迎的公司中被问到的。任何帮助都将不胜感激。
这是我想到的解决方案：
为简单起见，我将矩阵视为图形。
因此，将起始位置表示为 s（顶点），将目的地表示为 d
(顶点).
现在，我们将 运行 BFS 一次使用源 s 一次，一次使用源 d。
所以我们有每个顶点 v 从 s 到 v 的最小距离和从 v 到 d 的最小距离（距离可以为无穷大，例如矩阵中所有值为 0 的顶点的距离为无穷大）。
现在，对于矩阵中每个值为 0 的顶点 v，执行以下操作：
对于 v 的每对邻居（在矩阵中，最多 4 个），其中顺序很重要，这意味着顶点对 a 和 b 不同于b 和 a.
最多有 4!/2! = 12 对。
表示一对顶点a和b并计算以下距离：
s->a + 1 + 1 + b->d（给定s->a,b->d，这是路径s->a->v->b->的距离d).
从这些距离中选择最小值（其中最多 12 个），这是从 s 到 d 且 v 翻转后的最小距离。
现在，你可以知道要翻转哪一个，以及最小距离了。
复杂度 = O(V + E)
编辑：
如果矩阵的大小为 n x n，则 V = n ^ 2 并且每个顶点最多有 4 条边，因此 E = O(n^2) => O(n ^ 2).
给定一个二进制矩阵，其中 0 代表障碍物，1 代表路径，求从给定源到目的地的最小步数（只允许在 4 个方向上遍历）。这是一道典型的 BFS 题。
来源：(0,0) 目的地：(2,0)
1 1 0
0 1 1
1 1 1
答案：5
但是这个问题的下一部分很棘手，你可以用魔杖把一个零变成一个。现在你将如何找到这种情况下的最短路径。
如果我们翻转 (1,0)，我们可以通过 3 步到达目的地。
典型的蛮力解决方案是通过将零变为一来对每个矩阵执行 BFS。我们怎样才能做得更好？
这是在一家受欢迎的公司中被问到的。任何帮助都将不胜感激。
这是我想到的解决方案：
为简单起见，我将矩阵视为图形。
因此，将起始位置表示为 s（顶点），将目的地表示为 d
(顶点).
现在，我们将 运行 BFS 一次使用源 s 一次，一次使用源 d。
所以我们有每个顶点 v 从 s 到 v 的最小距离和从 v 到 d 的最小距离（距离可以为无穷大，例如矩阵中所有值为 0 的顶点的距离为无穷大）。
现在，对于矩阵中每个值为 0 的顶点 v，执行以下操作：
对于 v 的每对邻居（在矩阵中，最多 4 个），其中顺序很重要，这意味着顶点对 a 和 b 不同于b 和 a.
最多有 4!/2! = 12 对。
表示一对顶点a和b并计算以下距离：
s->a + 1 + 1 + b->d（给定s->a,b->d，这是路径s->a->v->b->的距离d).
从这些距离中选择最小值（其中最多 12 个），这是从 s 到 d 且 v 翻转后的最小距离。
现在，你可以知道要翻转哪一个，以及最小距离了。
复杂度 = O(V + E)
编辑：
如果矩阵的大小为 n x n，则 V = n ^ 2 并且每个顶点最多有 4 条边，因此 E = O(n^2) => O(n ^ 2).