C++の2Dマトリックスで可能なパスを確認します

2D配列があると考えてください。左上隅から右下隅へのパスを取得できるかどうかを確認する必要があります。マトリックスは0と1で埋められます。 0はオープ​​ンエリアを示し、1は閉塞を示します。左上隅は常に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