หาความยาวของภูมิภาคที่ใหญ่ที่สุดใน Boolean Matrix ใน C++

โจทย์

ได้รับเมทริกซ์ 2D ขนาด n x m ประกอบด้วย 0 และ 1 ทางเราต้อง หาความยาวของภูมิภาค (Region) ที่ใหญ่ที่สุดใน Boolean Matrix

โหนดที่มีค่า 1 เรียกว่า Filled Cell ภูมิภาคคือกลุ่มเซลล์ 1 ที่เชื่อมต่อกันใน 8 ทิศทาง (แนวนอน แนวตั้ง แนวทแยง)

ตัวอย่าง

Input: matrix[4][5] = {{0,1,1,0,1}, {0,0,1,1,1}, {1,0,0,0,0}, {1,0,1,0,1}}

Output: 6

แนวทางแก้ปัญหา

ใช้ DFS (Depth First Search) นับจำนวนเซลล์ที่เชื่อมต่อ:

วนลูปทุกเซลล์ ถ้าเป็น 1 และยังไม่ได้เยี่ยม เริ่ม DFS
DFS ตรวจสอบเพื่อนบ้าน 8 ทิศทาง นับจำนวนเซลล์ที่เชื่อมต่อ
เก็บค่าสูงสุดของแต่ละการ DFS

โปรแกรมตัวอย่าง

#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