दिया गया कार्य एक दिए गए वर्ग बाइनरी सरणी में ऊपरी बाएं तत्व से निचले दाएं तत्व तक एक पथ में यात्रा करते समय प्राप्त किए जा सकने वाले अधिकतम पूर्णांक मान को ढूंढना है, यानी इंडेक्स [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 >= side || j >= side )। यदि हां, तो इसका मतलब है कि हम मैट्रिक्स सीमा से बाहर हैं और 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 वापस करें।
- अन्यथा बस ans वापस करें।
कार्यक्रम उदाहरण
#include<bits/stdc++.h>
using namespace std;
#define side 4 // pw 2 की घात है
int Max(int m[][side], int i, int j, int pw){
// सीमा से बाहर
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 फ़ंक्शन
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