कार्य को देखते हुए अधिकतम पूर्णांक मान ज्ञात करना है जो किसी दिए गए वर्ग बाइनरी सरणी के शीर्ष बाएं तत्व से नीचे दाएं तत्व तक पथ में यात्रा करते समय प्राप्त किया जा सकता है, जो कि इंडेक्स [0] [0] से इंडेक्स तक शुरू होता है। [एन -1] [एन -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 का उपयोग करके शीर्ष पर वर्गाकार आव्यूह की भुजा के आकार को परिभाषित करें।
-
मुख्य () फ़ंक्शन में मैट्रिक्स को स्टोर करने के लिए एक 2D सरणी int m[][4] बनाएं और Max(m, 0, 0, 0)
को कॉल करें। -
मैक्स () फंक्शन में पहले चेक करें कि क्या (i>=साइड || j>=साइड)। अगर ऐसा है, तो इसका मतलब है कि हम मैट्रिक्स सीमा से बाहर हैं और 0.
-
एक नया वेरिएबल int ans बनाएं और ans =max(Max(m, i, j+1, pw+1), Max(m, i+1, j, pw+1)) डालें।
-
फिर जांचें कि क्या (एम [i] [जे] ==1)। अगर ऐसा है, तो पाउ (2, पीडब्ल्यू) + उत्तर दें।
-
अन्यथा बस उत्तर दें।
उदाहरण
#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