algorithm - 在矩阵中的源和目标之间建立路径所需的最小翻转

Question

问题的扩展https://www.geeksforgeeks.org/find-whether-path-two-cells-matrix/

在这里，必须查找路径是否存在于矩阵的角中top left。bottom right如问题中所述，两者之间会有障碍。现在我的问题是，如果不存在从源到目标的路径，那么必须在矩阵中翻转才能构建的最小障碍是什么：

• a) 一条路径。
• b) 最短路径

源和目的地之间。

标签： algorithmdata-structuresdynamic-programminggraph-algorithmbreadth-first-search

Answer 1

为了更清楚地说明您的问题，假设我们将获得一个二维网格，其中包含整数和row的行数和列数。col01

0：空白单元格。
1：障碍物。

您想知道必须在矩阵中翻转以构建路径的最小障碍物和从矩阵的左上角到右下角的最短路径吗？

a) 障碍物最少的
路径：我们可以简单地应用广度优先搜索（BFS）或深度优先搜索（DFS），并以进入空白空间的0成本为 ，进入障碍物的成本为 ，找到障碍物数量最少的路径1。而且，我们可以从每个单元格向上、向下、向右和向左遍历所有方向。以这种方式计算的最短路径距离将给我们从矩阵的左上角到右下角的最小障碍物翻转路径。

b) 障碍物最少的最短路径：
从矩阵的左上角到右下角的最短路径长度总是相同的，等于 row + col - 2，这可以通过从右或向下遍历来实现网格中的每个单元格。因此，也可以使用 BFS 或 DFS 来解决这个问题，并且从每个单元格仅向右或向下遍历，并将进入空白空间的0成本作为 ，并将进入障碍物的成本作为1。以这种方式计算的最短路径距离将为我们提供使用最短路径之一从矩阵的左上角到右下角翻转的最少障碍物数量。由于遍历时不会有循环，我们也可以使用动态规划来解决这个问题。