সি++-এ বাইনারি ম্যাট্রিক্সে ১ দিয়ে গঠিত সর্বোচ্চ '+' আকারের আকার বের করা

এই সমস্যাতে, আমাদের একটি NxN বাইনারি ম্যাট্রিক্স bin[][] দেওয়া আছে। আমাদের কাজ হলো বাইনারি ম্যাট্রিক্সে শুধু ১ দিয়ে গঠিত সর্বোচ্চ '+' আকারের আকার (size) বের করা।

উদাহরণ দিয়ে সমস্যা বোঝা যাক,

ইনপুট

0 1 1 1 1 1 0 1 0

আউটপুট

5

সমাধানের পদ্ধতি

এই সমস্যার একটি সহজ সমাধান হলো সর্বোচ্চ '+' বের করার জন্য যেটি হয়েছে একটি পয়েন্টের জন্য চারদিকেই সর্বোচ্চ সংখ্যক ১ থাকা যা সব দিকেই সমান হবে। এর জন্য আমরা পয়েন্টের চারপাশের প্রতিটি দিকের জন্য একটি করে ম্যাট্রিক্স তৈরি করব (মোট ৪টি)। প্রতিটি ম্যাট্রিক্সে প্রদত্ত উপাদানের জন্য সেকোয়েন্সিয়াল ১-গুলোর সংখ্যা সংরক্ষণ করা থাকবে। সব ইনডেক্স মানের জন্য আমরা সর্বোচ্চ মান বের করব যেটি চারদিকের সেকোয়েন্সিয়াল ১-গুলোর মিনিমাম।

সমাধান কোড:

উদাহরণ

#include <iostream>
using namespace std;

#define N 7

int findLargestPlusSize(int mat[N][N]) {
    int conOneLeft[N][N], conOneRight[N][N], conOneTop[N][N], conOneBottom[N][N];
    for (int i = 0; i < N; i++) {
        conOneTop[0][i] = mat[0][i];
        conOneBottom[N - 1][i] = mat[N - 1][i];
        conOneLeft[i][0] = mat[i][0];
        conOneRight[i][N - 1] = mat[i][N - 1];
    }
    for (int i = 0; i < N; i++) {
        for (int j = 1; j < N; j++) {
            if (mat[i][j] == 1)
                conOneLeft[i][j] = conOneLeft[i][j - 1] + 1;
            else
                conOneLeft[i][j] = 0;
            if (mat[j][i] == 1)
                conOneTop[j][i] = conOneTop[j - 1][i] + 1;
            else
                conOneTop[j][i] = 0;
            j = N - 1 - j;
            if (mat[j][i] == 1)
                conOneBottom[j][i] = conOneBottom[j + 1][i] + 1;
            else
                conOneBottom[j][i] = 0;
            if (mat[i][j] == 1)
                conOneRight[i][j] = conOneRight[i][j + 1] + 1;
            else
                conOneRight[i][j] = 0;
            j = N - 1 - j;
        }
    }
    int maxConOne = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++){
            int ConOnes = min(min(conOneTop[i][j], conOneBottom[i][j]), min(conOneLeft[i][j], conOneRight[i][j]));
            if(ConOnes > maxConOne)
                maxConOne = ConOnes;
        }
    }
    if (maxConOne)
        return (4 * (maxConOne - 1) + 1);
    return 0;
}

int main() {
    int mat[N][N] = {
        { 1, 0, 1, 1, 1, 1, 0 },
        { 1, 0, 1, 0, 1, 1, 1 },
        { 1, 1, 1, 0, 1, 1, 0 },
        { 0, 0, 0, 0, 1, 0, 0 },
        { 1, 0, 1, 1, 1, 1, 1 },
        { 1, 1, 1, 0, 1, 1, 1 },
        { 1, 0, 0, 0, 1, 0, 0 },
    };
    cout<<"The size of the largest plus formed by ones is "<<findLargestPlusSize(mat);
    return 0;
}

আউটপুট

The size of the largest plus formed by ones is 9