C++-এ বুলিয়ান ম্যাট্রিক্সে সর্ববৃহৎ রিজন (সংযুক্ত ১-র আকার) বের করুন

একটি n x m বুলিয়ান ম্যাট্রিক্স (শুধু ০ এবং ১) দেওয়া আছে। 1 হলে সেটি ফিল্ড সেল। আড়াল, লম্বা, কোণাংক — ৮ দিকেই সংযুক্ত ফিল্ড সেলগুলো একটি রিজন বানায়। সর্ববৃহৎ রিজনের আকার (সেল সংখ্যা) বের করতে হবে।

উদাহরণ

ইনপুট (4x5):

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

আউটপুট: 6

ব্যাখ্যা: সবচেয়ে বড় রিজনে ৬টি সংযুক্ত ১ আছে।

অ্যালগরিদম: DFS + ভিজিটেড ট্র্যাকিং

1. সব সেলের জন্য ভিজিটেড অ্যারে রাখুন।
2. প্রতিটি অনভিজিটেড 1 সেল থেকে DFS শুরু করুন।
3. ৮ দিকের নোবর চেক করুন (dx,dy ∈ {-1,0,1})।
4. বৈধ, অনভিজিটেড, মান ১ হলে রিকার্সিভ কল, কাউন্ট বাড়ান।
5. সব ডিএফএস থেকে ম্যাক্স কাউন্ট রিটার্ন করুন।

C++ প্রোগ্রাম

#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) {
        int nx = row + rowNbr[k], ny = col + colNbr[k];
        if (isNotVisited(M, nx, ny, visited)) {
            count++;
            depthFirstSearch(M, nx, ny, visited, count);
        }
    }
}

int findLargestRegionLength(int M[][COL]) {
    bool visited[ROW][COL];
    memset(visited, 0, sizeof(visited));
    int maxCount = -1;
    for (int i = 0; i < ROW; ++i) {
        for (int j = 0; j < COL; ++j) {
            if (M[i][j] && !visited[i][j]) {
                int count = 1;
                depthFirstSearch(M, i, j, visited, 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

ব্যাখ্যা

• rowNbr/colNbr ৮ দিকের অফসেট।
• isNotVisited বাউন্ড চেক + ভ্যালু ১ + অনভিজিটেড চেক করে।
• count রেফারেন্স দিয়ে পাস করা হয়েছে যাতে সব রিকার্শনে শেয়ার করা যায়।
• টাইম: O(ROW×COL) — প্রতিটি সেল একবার ভিজিট হয়।
• স্পেস: O(ROW×COL) ভিজিটেড অ্যারে + O(ROW×COL) রিকার্শন স্ট্যাক (ওয়ার্স্ট কেস)।

ইটারেটিভ BFS বিকল্প

স্ট্যাক ওভারফ্লো রোধে BFS (queue) ব্যবহার করা ভালো বড় গ্রিডের জন্য।