C++-এ বাইনারি ম্যাট্রিক্সে ম্যাক্সিমাম ডেসিমেল ভ্যালু পাথ

দেওয়া কাজ হচ্ছে একটি বর্গাকার বাইনারি অ্যারেতে উপরের বাম এলিমেন্ট থেকে নিচের ডান এলিমেন্ট পর্যন্ত পাথে যেতে সময় প্রাপ্ত হয় এমন সর্বোচ্চ পূর্ণসংখ্যা মান বের করা, অর্থাৎ ইনডেক্স [0][0] থেকে ইনডেক্স [n - 1][n - 1] পর্যন্ত।

পথ কভার করার সময় আমরা শুধু ডানে ([i][j + 1]) বা নিচে ([i + 1][j]) যেতে পারি।

পূর্ণসংখ্যা মান হবে ট্রাভার্স করা পথের বিটগুলো ব্যবহার করে ক্যালকুলেট করা।

উদাহরণ দিয়ে বুঝি −

ইনপুট

m = { 
    {1, 1, 1, 1}, 
    {0, 0, 1, 0}, 
    {1, 0, 1, 1}, 
    {0, 1, 1, 1} }

আউটপুট

ব্যাখ্যা

যে পথটি আমরা নিয়েছি: [0, 0] →[0, 1] → [0, 2] → [1, 2] → [2, 2] → [3, 2] →[3, 3]

তাহলে ডেসিমেল ভ্যালু হয় = 1*(2⁰) + 1*(2¹) + 1*(2²) + 1*(2³) + 1*(2⁴) + 1*(2⁵) + 1*(2⁶)

= 1 + 2 + 4 + 8 + 16 + 32 + 64

= 127

ইনপুট

m = { 
    {1, 0, 1, 1}, 
    {0, 0, 1, 0}, 
    {1, 0, 0, 1}, 
    {0, 1, 1, 1} }

আউটপুট

নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতি নিম্নরূপ

প্রথমে বর্গাকার ম্যাট্রিক্সের সাইডের আকার #define দিয়ে টপে ডিক্লেয়ার।
main() ফাংশনে একটি ২D অ্যারে int m[][4] তৈরি করা হয় ম্যাট্রিক্স সংরক্ষণের জন্য এবং Max(m, 0, 0, 0) কল করা হয়।
max() ফাংশনে প্রথমে চেক করা হয় if (i >= side || j >= side )। যদি সত্য হয় তবে ম্যাট্রিক্স বাউন্ডেরি বাইরে এবং ০ রিটার্ন।
একটি নতুন ভেরিয়েবল int ans এবং ans = max(Max(m, i, j+1, pw+1), Max(m, i+1, j, pw+1))।
তারপর চেক করা হয় if (m[i][j] == 1)। যদি সত্য হয় তবে রিটার্ন pow(2, pw) + ans।
অন্যথায় সিম্পলি ans রিটার্ন।

উদাহরণ

#include<bits/stdc++.h> 
using namespace std; 
#define side 4 // pw is power of 2 

int Max(int m[][side], int i, int j, int pw){ 
    // Out of boundary 
    if (i >= side || j >= side ) 
        return 0; 
    int ans = max(Max(m, i, j+1, pw+1), Max(m, i+1, j, pw+1)); 
    if (m[i][j] == 1) 
        return pow(2, pw) + ans; 
    else 
        return ans; 
} 
//main function 
int main(){ 
    int m[][4] = {{1, 1, 1, 1},{0, 0, 1, 0},{1, 0, 1, 1},{0, 1, 1, 1}}; 
    cout << Max(m, 0, 0, 0); 
    return 0; 
}