Tìm độ dài của vùng lớn nhất trong Ma trận Boolean trong C ++

Trong bài toán này, chúng ta được cung cấp một ma trận 2-D kích thước nXm chỉ bao gồm 0 và 1. Nhiệm vụ của chúng ta là tìm độ dài của vùng lớn nhất trong Ma trận Boolean.

Mô tả sự cố: Nếu một ô chứa 1, nó là một Ô được lấp đầy. Chúng ta cần tìm chiều dài của các ô được kết nối được kết nối liền kề với nhau theo chiều ngang hoặc chiều dọc hoặc đường chéo.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào: ma trận [4] [5]

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

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

Đầu ra: 6

Giải thích:

Số lượng ô đã điền được kết nối là 1, 2, 6.

Phương pháp tiếp cận Giải pháp -

Để giải quyết vấn đề, chúng ta chỉ cần đếm tổng số ô được kết nối của ma trận.

Đối với điều này, chúng tôi sẽ thực hiện DFS cho ô sẽ kiểm tra tất cả các ô lân cận của ô hiện tại (đối với một ô có thể có 8 ô lân cận). Đối với mỗi ô, chúng ta cần kiểm tra xem nó có được truy cập hay không bằng cách theo dõi bằng bản đồ băm. Và khi hoàn thành, chúng ta cần trả về số lượng ô đã truy cập tối đa.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#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;
}

Đầu ra

The length of largest region is 6