প্রদত্ত কাজটি হল প্রদত্ত বর্গাকার বাইনারি অ্যারের উপরের বাম উপাদান থেকে নীচের ডানদিকের উপাদানের পথে ভ্রমণ করার সময় সর্বাধিক পূর্ণসংখ্যার মান খুঁজে বের করা, অর্থাৎ, সূচক [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}
} আউটপুট
127
ব্যাখ্যা
আমরা যে পথটি নিয়েছি তা হল:[0, 0] → [0, 1] → [0, 2] → [1, 2] → [2, 2] → [3, 2] → [3, 3]
সুতরাং দশমিক মান =1*(2 0 হয়ে যায় ) + 1*(2 1 ) + 1*(2 2 ) + 1*(2 3 ) + 1*(2 4 ) + 1*(2 5 ) + 1*(2 6 )
=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}
} আউটপুট
109
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
-
প্রথমে #define ব্যবহার করে উপরের বর্গাকার ম্যাট্রিক্সের পাশের আকার নির্ধারণ করুন।
-
main() ফাংশনে ম্যাট্রিক্স সংরক্ষণ করতে একটি 2D অ্যারে int m[][4] তৈরি করুন এবং Max(m, 0, 0, 0)
-
max() ফাংশনে প্রথমে চেক করুন যদি (i>=সাইড || j>=সাইড)। যদি তাই হয়, তাহলে এর মানে হল আমরা ম্যাট্রিক্স সীমানার বাইরে চলে এসেছি এবং 0 রিটার্ন করছি।
-
একটি নতুন পরিবর্তনশীল int ans তৈরি করুন এবং ans =max(Max(m, i, j+1, pw+1), Max(m, i+1, j, pw+1))।
-
তারপর পরীক্ষা করুন যদি (m[i][j] ==1)। যদি তাই হয়, তাহলে pow(2, pw) + 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;
} আউটপুট
127
