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