找到阻止 A 到达 B 所需的最小阻塞数
Find minimum number of blockage needed to prevent A from reaching B
You are given a 2D array representing a map e.g.:
A . X .
. . . .
X X . B
Note: '.' represents traversable positions 'X' represents
non-traversable positions
THE QUESTION:
Find the minimum number of blockage you can add to prevent A from reaching B.
For the above example, the answer is 1 from a positioning like this:
A . X .
. . % .
X X . B
Note: '%' represents the inserted blockage
我的尝试:
我试图用一个简单的 DFS 来解决这个问题，该 DFS 被抛向 4 个不同的方向，并且只在该特定路径通向 B 时增加总阻塞数。然而，这会在标记已经遍历的路径时产生问题，因为任意标记次优路径可能会阻塞搜索其他方向的努力。
关于如何最佳解决这个问题的任何指示？或者在Leetcode/Codeforces/etc.?
是否有与上述问题一脉相承的编码问题
编辑 1：
根据Jacob Steinebronn的回答，这个问题可以用一个最大流算法来解决。所以在尝试理解算法一段时间后，这是我的新尝试：
- 根据提供的二维地图构建有向图。我假设每个顶点都将相互连接，单向边指向远离起始节点的方向。我假设生成的图形应该是非循环的？
- 用 1 (?) 初始化每条边的容量，因为我不希望算法多次通过相同的路径。
- 运行 该图上的最大流算法（Ford-Fulkerson、Dinic 或 Karp-Edmond），最大流是防止 A 到达 B 所需的最小切割。
我走的路对吗？
这个问题是恒等式Min Cut = Max Flow的经典例子。让我们分解一下：
这个问题可以概括为：给定一个图，以及起点和终点，要 Cut 的 Min 边数是多少，这样就有没有从头到尾的路径。这可以通过称为 Max Flow 的算法来解决。因此，为了解决这个问题，构建一个图表，其中每个节点都连接到与其相邻的所有 non-blocked 单元格（注意定向或 non-directed 边）和 运行 最大流量以获得您的结果。
You are given a 2D array representing a map e.g.:
A . X .
. . . .
X X . B
Note: '.' represents traversable positions 'X' represents non-traversable positions
THE QUESTION:
Find the minimum number of blockage you can add to prevent A from reaching B.
For the above example, the answer is 1 from a positioning like this:
A . X .
. . % .
X X . B
Note: '%' represents the inserted blockage
我的尝试:
我试图用一个简单的 DFS 来解决这个问题，该 DFS 被抛向 4 个不同的方向，并且只在该特定路径通向 B 时增加总阻塞数。然而，这会在标记已经遍历的路径时产生问题，因为任意标记次优路径可能会阻塞搜索其他方向的努力。
关于如何最佳解决这个问题的任何指示？或者在Leetcode/Codeforces/etc.?
是否有与上述问题一脉相承的编码问题编辑 1： 根据Jacob Steinebronn的回答，这个问题可以用一个最大流算法来解决。所以在尝试理解算法一段时间后，这是我的新尝试：
- 根据提供的二维地图构建有向图。我假设每个顶点都将相互连接，单向边指向远离起始节点的方向。我假设生成的图形应该是非循环的？
- 用 1 (?) 初始化每条边的容量，因为我不希望算法多次通过相同的路径。
- 运行 该图上的最大流算法（Ford-Fulkerson、Dinic 或 Karp-Edmond），最大流是防止 A 到达 B 所需的最小切割。
我走的路对吗？
这个问题是恒等式Min Cut = Max Flow的经典例子。让我们分解一下： 这个问题可以概括为：给定一个图，以及起点和终点，要 Cut 的 Min 边数是多少，这样就有没有从头到尾的路径。这可以通过称为 Max Flow 的算法来解决。因此，为了解决这个问题，构建一个图表，其中每个节点都连接到与其相邻的所有 non-blocked 单元格（注意定向或 non-directed 边）和 运行 最大流量以获得您的结果。