在C ++中找到布尔矩阵中最大区域的长度

在这个问题中，我们得到一个大小为nXm的二维矩阵，仅由0和1组成。我们的任务是在布尔矩阵中找到最大区域的长度。 

问题描述： 如果一个单元格包含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<<"最大区域的长度是 "<<findLargestRegionLength(M);

   return 0;
}

最大区域的长度是 6