在矩阵中的源和目标之间建立路径所需的最少翻转
Minimum flips required to make path between source and destination in a matrix
问题的扩展https://www.geeksforgeeks.org/find-whether-path-two-cells-matrix/
这里必须找到路径是否存在于矩阵的 top left 到 bottom right 角中。如问题所述，两者之间会有障碍。现在我的问题是，如果不存在从源到目的地的路径，那么必须在矩阵中翻转才能构建的最小障碍是什么：
- a) 路径。
- b) 最短路径
在源和目标之间。
为了更清楚地说明您的问题，假设我们将获得一个二维网格，其中包含 row 行数和 col 列数的整数，其中包含整数 0 和1.
0 ：空白单元格。
1 : 障碍。
您想知道从矩阵的左上角到右下角构建路径和最短路径时必须翻转的最小障碍？
a) 障碍物最少的路径：
我们可以简单地应用广度优先搜索 (BFS) 或深度优先搜索 (DFS) 并将进入空白 space 的成本设为 0 并将进入障碍物的成本设为 1。而且，我们可以从每个单元格向上、向下、向右和向左遍历所有方向。这样计算出的最短路径的距离，就是矩阵左上角到右下角的最小障碍物翻转路径。
b) 障碍物最少的最短路径：
从矩阵的左上角到右下角的最短路径长度始终相同，等于 row + col - 2 这可以通过从网格中的每个单元格向右或向下遍历来实现。因此，这个问题也可以使用 BFS 或 DFS 来解决，从每个单元格只向右或向下遍历，并将进入空白的成本 space 设为 0，进入障碍物的成本设为 1 .以这种方式计算的最短路径的距离将为我们提供使用最短路径之一从矩阵的左上角到右下角要翻转的最小障碍物数量。由于遍历不会有循环，所以我们也可以用动态规划来解决这个问题。
问题的扩展https://www.geeksforgeeks.org/find-whether-path-two-cells-matrix/
这里必须找到路径是否存在于矩阵的 top left 到 bottom right 角中。如问题所述，两者之间会有障碍。现在我的问题是，如果不存在从源到目的地的路径，那么必须在矩阵中翻转才能构建的最小障碍是什么：
- a) 路径。
- b) 最短路径
在源和目标之间。
为了更清楚地说明您的问题，假设我们将获得一个二维网格，其中包含 row 行数和 col 列数的整数，其中包含整数 0 和1.
0 ：空白单元格。
1 : 障碍。
您想知道从矩阵的左上角到右下角构建路径和最短路径时必须翻转的最小障碍？
a) 障碍物最少的路径：
我们可以简单地应用广度优先搜索 (BFS) 或深度优先搜索 (DFS) 并将进入空白 space 的成本设为 0 并将进入障碍物的成本设为 1。而且，我们可以从每个单元格向上、向下、向右和向左遍历所有方向。这样计算出的最短路径的距离，就是矩阵左上角到右下角的最小障碍物翻转路径。
b) 障碍物最少的最短路径：
从矩阵的左上角到右下角的最短路径长度始终相同，等于 row + col - 2 这可以通过从网格中的每个单元格向右或向下遍历来实现。因此，这个问题也可以使用 BFS 或 DFS 来解决，从每个单元格只向右或向下遍历，并将进入空白的成本 space 设为 0，进入障碍物的成本设为 1 .以这种方式计算的最短路径的距离将为我们提供使用最短路径之一从矩阵的左上角到右下角要翻转的最小障碍物数量。由于遍历不会有循环，所以我们也可以用动态规划来解决这个问题。