समस्या विवरण
एक 2D मैट्रिक्स दिया गया है जिसके आयाम row X col हैं। लक्ष्य मैट्रिक्स को सेल 0,0 से सेल row, col तक केवल दाएं और नीचे की चालों का उपयोग करके पार करने के तरीकों की संख्या गिनना है। यानी पहली चाल 0,0 से 0,1 (नीचे) या 1,0 (दाएं) हो सकती है न कि 1,1 (तिरछे)।
उदाहरण
इनपुट
col = 2; row = 4
आउटपुट
मैट्रिक्स को पार करने के तरीकों की संख्या: 4
व्याख्या
सेल 0,0 से 2,4 तक पहुंचने के तरीके नीचे दिखाए गए हैं:
इनपुट
col = 4; row = 3
आउटपुट
मैट्रिक्स को पार करने के तरीकों की संख्या: 10
व्याख्या
हम समस्या को छोटे पुनरावर्तन में कम करेंगे। col=3, row=2 के तरीके गिनें, फिर col=2, row=1... col=1 या row=1 के लिए उत्तर 1 होगा (केवल दाएं या केवल नीचे की चाल)।
दृष्टिकोण
इस दृष्टिकोण में हम पुनरावर्तन विधि का उपयोग करेंगे। अंत में या तो row या col के 1 होने पर केवल एक तरीका होता है जो 1 सीधी दाएं चाल या 1 सीधी नीचे की चाल है। यह पुनरावर्तन के लिए समाप्ति शर्त होगी।
एल्गोरिदम चरण
- मैट्रिक्स के आयामों के लिए पूर्णांक
row,colलें। - फंक्शन
ways_traverse_matrix(int row, int col)आयाम लेता है और मैट्रिक्स को पार करने के तरीकों की संख्या लौटाता है। row==1के लिए, 1 लौटाएं।col==1के लिए, 1 लौटाएं।- अन्यथा पुनरावर्तन का उपयोग करके तरीकों की गणना करें:
ways_traverse_matrix(temp_1, col) + ways_traverse_matrix(row, temp_2)। - यहां
temp_1= पिछली पंक्ति संख्या औरtemp_2= पिछला कॉलम संख्या। - अंत में हमें कुल तरीकों की गिनती मिल जाएगी।
C++ कोड उदाहरण
#include <bits/stdc++.h>
using namespace std;
int ways_traverse_matrix(int row, int col) {
if (row == 1) {
return 1;
} else if(col == 1) {
return 1;
} else {
int temp_1 = row - 1;
int temp_2 = col - 1;
return ways_traverse_matrix(temp_1, col) + ways_traverse_matrix(row, temp_2);
}
}
int main() {
int col = 2;
int row = 2;
cout << "मैट्रिक्स को पार करने के तरीकों की संख्या: " << ways_traverse_matrix(row, col);
return 0;
}
आउटपुट
मैट्रिक्स को पार करने के तरीकों की संख्या: 2
