广度优先搜索
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)
.