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

Question

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

这里必须找到路径是否存在于矩阵的左上角到右下角。如问题所述，两者之间会有障碍。现在我的问题是，如果不存在从源到目的地的路径，那么必须在矩阵中翻转以构建的最小障碍是什么:

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

在源和目标之间。

Answer 1

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

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

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

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

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