在C ++中检查2D矩阵中的可能路径

考虑我们有一个二维数组。我们必须找到是否可以找到从左上角到右下角的路径。矩阵用0和1填充。0表示开放区域，1表示阻塞。请注意，左上角将始终为1。

假设矩阵如下-

一个路径标记为绿色，也有一些其他路径。因此，如果存在路径，程序将返回true，否则返回false。

通过将所有可访问节点更改为-1，我们将解决此问题，首先将起点的值更改为-1，然后在第一行中获取下一个值，然后与上一个值进行比较，将当前值设置为等于上一个值如果可以访问（非0）。对列值也执行相同的操作。通过比较当前值并将其与先前的列值设置（如果可以达到的话）。然后从第一行第一列开始，取上一行，上一列的值，在它们之间取最小值。并将当前索引设置为最小值。如果当前索引为1，则没有变化。最后，如果最终索引与右下角相同，则返回true，否则返回false。

示例

#include <iostream>
#define row 5
#define col 5
using namespace std;
bool isPathPresent(int arr[row][col]) {
   arr[0][0] = -1;
   for (int i = 1; i < row; i++)
      if (arr[i][0] != 1)
         arr[i][0] = arr[i - 1][0];
   for (int j = 1; j < col; j++)
      if (arr[0][j] != 1)
         arr[0][j] = arr[0][j - 1];
   for (int i = 1; i < row; i++)
      for (int j = 1; j < col; j++)
         if (arr[i][j] != 1)
            arr[i][j] = min(arr[i][j - 1], arr[i - 1][j]);
   return (arr[row - 1][col - 1] == -1);
}
int main() {
   int arr[row][col] = {{ 0, 0, 0, 1, 0},
      {1, 0, 0, 1, 1},
      { 0, 0, 0, 1, 0},
      {1, 0, 0, 0, 0},
      { 0, 0, 1, 0, 0}};
   if (isPathPresent(arr))
      cout << "Path is present";
   else
      cout << "No path has found";
}

输出结果

Path is present