आयाम पंक्ति X कॉलम के साथ 2D मैट्रिक्स को देखते हुए। लक्ष्य सेल 0,0 से सेल पंक्ति तक मैट्रिक्स को पार करने के तरीकों की संख्या की गणना करना है, केवल दाएं और नीचे की चाल का उपयोग करके कॉल करना, यानी पहली चाल 0,0 से 0,1 (नीचे) या 1,0 हो सकती है (दाएं) और 1,1 (विकर्ण) नहीं।
उदाहरण के लिए
इनपुट
col = 2; row = 4
आउटपुट
Count of number of ways to traverse a Matrix are: 4
स्पष्टीकरण
जिस तरीके से हम सेल 0,0 से 2,4 तक पहुंच सकते हैं, वह दिखाया गया है -
इनपुट
col = 4; row = 3
आउटपुट
Count of number of ways to traverse a Matrix are: 10
स्पष्टीकरण
We will reduce the problem into smaller recursions. Count ways for col=3, row=2, then for col=2, row=1 ….. For col=1 or row=1 the answer will be 1. (only right or only down move).
नीचे दिए गए कार्यक्रम में उपयोग किया गया दृष्टिकोण इस प्रकार है
इस दृष्टिकोण में हम एक पुनरावर्तन विधि का उपयोग करेंगे। अंत में या तो पंक्ति या कॉलम के लिए 1 के रूप में। केवल एक ही रास्ता है जो 1 सीधी दाहिनी चाल या 1 सीधी नीचे की चाल है। यह पुनरावर्तन के लिए समाप्ति शर्त होगी।
-
मैट्रिक्स के आयामों के लिए पूर्णांक पंक्ति, कॉलम लें।
-
Functionways_traverse_matrix(int row, int col) आयाम लेता है और मैट्रिक्स को पार करने के तरीकों की संख्या देता है।
-
पंक्ति ==1 के लिए, वापसी 1.
-
col==1 के लिए, वापसी 1.
-
अन्यथा रिकर्सन तरीके_ट्रैवर्स_मैट्रिक्स (temp_1, col) +ways_traverse_matrix (पंक्ति, temp_2) का उपयोग करके तरीकों की गणना करें।
-
यहाँ temp_1=पिछली पंक्ति संख्या और temp_2=पिछला स्तंभ संख्या।
-
अंत में हमें कुल तरीकों की गिनती मिलेगी।
उदाहरण
#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<<"Count the number of ways to traverse a Matrix are: "<<ways_traverse_matrix(row, col);
return 0;
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -
Count the number of ways to traverse a Matrix are: 2