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

Cho ma trận 2D kích thước n x m chứa 0 và 1. Nhiệm vụ: tìm độ dài vùng lớn nhất trong ma trận Boolean.

Mô tả: Ô giá trị 1 gọi là ô đã điền. Cần tìm số ô đã điền liên thông (ngang, dọc, chéo).

Ví dụ:

Đầu vào: matrix[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ố ô đã điền liên thông là 1, 2, 6.

Phương pháp giải

Dùng DFS đếm ô liên thông. Với mỗi ô chưa thăm, thực hiện DFS kiểm tra 8 hướng lân cận. Dùng mảng đánh dấu visited. Trả về số lượng ô lớn nhất.

Chương trình minh họa

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

Kết quả

The length of largest region is 6