C++의 부울 행렬에서 가장 큰 영역의 길이 찾기

이 문제에서는 0과 1로만 구성된 nXm 크기의 2차원 행렬이 제공됩니다. 우리의 임무는 부울 행렬에서 가장 큰 영역의 길이를 찾는 것입니다.

문제 설명: 셀에 1이 포함되어 있으면 채워진 셀입니다. 가로 또는 세로 또는 대각선으로 서로 인접하게 연결된 연결된 셀의 길이를 찾아야 합니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

입력: 매트릭스[4][5]

{ {0, 1, 1, 0, 1},
{0, 0, 1, 1, 1},

{1, 0, 0, 0, 0},
{1, 0, 1, 0, 1} }

출력: 6

설명:

연결된 채워진 셀의 수는 1, 2, 6입니다.

해결 방법 -

문제를 해결하려면 행렬의 연결된 총 셀 수를 계산하기만 하면 됩니다.

이를 위해 현재 셀의 모든 인접 셀을 검사할 셀에 대해 DFS를 수행합니다(셀의 경우 8개의 인접 셀이 있을 수 있음). 각 셀에 대해 해시 맵을 사용하여 추적하여 방문했는지 확인해야 합니다. 그리고 완료되면 방문한 셀의 최대 개수를 반환해야 합니다.

우리 솔루션의 작동을 설명하는 프로그램,

예시

#include <bits/stdc++.h>
using namespace std;
#define ROW 4
#define COL 5

int isNotVisited(int M[][COL], int row, int col, bool visited[][COL]) {
   
   return (row >= 0) && (row < ROW) && (col >= 0 ) && (col < COL) && (M[row][col] && !visited[row][col]);
}

void depthFirstSearch(int M[][COL], int row, int col, bool visited[][COL], int& count){
   
   static int rowNbr[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
   static int colNbr[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
   visited[row][col] = true;

   for (int k = 0; k < 8; ++k) {
      if (isNotVisited(M, row + rowNbr[k], col + colNbr[k], visited)) {
         count++;
         depthFirstSearch(M, row + rowNbr[k], col + colNbr[k], visited, count);
      }
   }
}

int findLargestRegionLength(int M[][COL]) {
   
   bool isvisited[ROW][COL];
   memset(isvisited, 0, sizeof(isvisited));
   int maxCount = -1;
   for (int i = 0; i < ROW; ++i) {
      for (int j = 0; j < COL; ++j) {
         if (M[i][j] && !isvisited[i][j]) {

            int count = 1;
            depthFirstSearch(M, i, j, isvisited, count);
            maxCount = max(maxCount, count);
         }
      }
   }
   return maxCount;
}

int main(){
   int M[][COL] = { {0, 1, 1, 0, 1},
                {0, 0, 1, 1, 1},
                {1, 0, 0, 0, 0},
                {1, 0, 1, 0, 1} };

   cout<<"The length of largest region is "<<findLargestRegionLength(M);

   return 0;
}

출력

The length of largest region is 6