C++의 2D 행렬에서 가능한 경로 확인

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