C++-এ ম্যাট্রিক্স-এ ৪টি আডজেসেন্ট এলিমেন্টের সর্বোচ্চ গুণফল বের করার প্রোগ্রাম

সমস্যা বিবরণ

একটি স্কোয়ার ম্যাট্রিক্স দেওয়া থাকলে, ৪টি আডজেসেন্ট এলিমেন্ট (হরিজন্টাল, ভার্টিকেল, ডায়াগোনাল উভয় দিক) যেন তাদের গুণফল সর্বোচ্চ হয়।

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

1. প্রতিটি সেল (i,j) থেকে ৪ দিক চেক করুন:
   • বাম: (i,j), (i,j-1), (i,j-2), (i,j-3)
   • উপর: (i,j), (i-1,j), (i-2,j), (i-3,j)
   • মেন ডায়াগোনাল: (i,j), (i-1,j-1), (i-2,j-2), (i-3,j-3)
   • অন्टी-ডায়াগোনাল: (i,j), (i-1,j+1), (i-2,j+2), (i-3,j+3)
2. বাউন্ডারি চেক করে গুণফল বের করুন এবং সর্বোচ্চ আপডেট করুন।

C++ কোড উদাহরণ

#include <bits/stdc++.h>
using namespace std;

const int n = 5;

int FindMaxProduct(int arr[][n], int n) {
    int max = 0, result;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            // Horizontal (left)
            if ((j - 3) >= 0) {
                result = arr[i][j] * arr[i][j-1] * arr[i][j-2] * arr[i][j-3];
                if (max < result) max = result;
            }
            // Vertical (up)
            if ((i - 3) >= 0) {
                result = arr[i][j] * arr[i-1][j] * arr[i-2][j] * arr[i-3][j];
                if (max < result) max = result;
            }
            // Diagonal (main)
            if ((i - 3) >= 0 && (j - 3) >= 0) {
                result = arr[i][j] * arr[i-1][j-1] * arr[i-2][j-2] * arr[i-3][j-3];
                if (max < result) max = result;
            }
            // Anti-diagonal
            if ((i - 3) >= 0 && (j + 3) < n) {
                result = arr[i][j] * arr[i-1][j+1] * arr[i-2][j+2] * arr[i-3][j+3];
                if (max < result) max = result;
            }
        }
    }
    return max;
}

int main() {
    int arr[][5] = {
        {1, 2, 3, 4, 5},
        {6, 7, 8, 9, 1},
        {2, 3, 4, 5, 6},
        {7, 8, 9, 1, 0},
        {9, 6, 4, 2, 3}
    };
    cout << FindMaxProduct(arr, n);
    return 0;
}

আউটপুট

3024

ব্যাখ্যা

সর্বোচ্চ গুণফল: 9×8×7×6 = 3024 (লাস্ট রো, ডায়াগোনাল বা অন্য कहीं)

জটিলতা

• সময়: O(n²)
• স্থান: O(1)