时间戳

首页 > 解决方案 > 找出阻止 A 到达 B 所需的最小阻塞数

algorithm - 找出阻止 A 到达 B 所需的最小阻塞数

问题描述

您将获得一个表示地图的二维数组，例如：

一种 。X 。

. . . .

二十。乙

笔记： '。' 表示可遍历的位置 'X' 表示不可遍历的位置

问题：

找出可以添加的最小阻塞数，以防止 A 到达 B。

对于上面的例子，答案是 1 来自这样的定位：

一种 。X 。

. . % 。

二十。乙

注：'%'代表插入的阻塞

我的尝试：

我试图用一个简单的 DFS 来解决这个问题，该 DFS 被抛出到 4 个不同的方向，并且只在该特定路径通向 B 时才增加总阻塞数。然而，这会在标记已经遍历的路径时产生问题，因为任意标记次优路径可能会阻塞其他方向的搜索工作。

有关如何以最佳方式解决此问题的任何指示？或者是否有与上述 Leetcode/Codeforces/etc 中的问题相同的编码问题？

编辑 1：根据Jacob Steinebronn的回答，这个问题可以用Max Flow Algorithm来解决。所以在尝试理解算法一段时间后，这是我的新尝试：

  1. 从提供的 2d 地图构造一个有向图。我假设每个顶点都将相互连接，单向边指向远离 Start 节点。我假设结果图应该是非循环的？
  2. 用 1 (?) 初始化每个边的容量，因为我不希望算法多次通过同一路径。
  3. 在该图上运行 Max Flow 算法（Ford-Fulkerson、Dinic 或 Karp-Edmond），Max flow 是防止 A 到达 B 所需的最小切割。

我在正确的轨道上吗？

标签： algorithmsearchpath-finding

解决方案

这个问题是Min Cut = Max Flow恒等式的一个经典例子。让我们分解一下：这个问题可以概括：给定一个图，以及一个起点和终点，切割的最小边数是多少，这样就没有从起点到终点的路径。这可以通过一种称为Max Flow的算法来解决。因此，要解决此问题，请构建一个图，其中每个节点都连接到与其相邻的所有非阻塞单元（注意有向或无向边）并运行 Max Flow 以获得您的结果。

推荐阅读