एक भूलभुलैया दी गई है जिसे row X col मैट्रिक्स के रूप में दर्शाया गया है जिसमें बाधा को -1 के रूप में दर्शाया गया है और एक स्पष्ट सेल का मान -1 के अलावा है। लक्ष्य पहले सेल arr[0][0] से शुरू करके अंतिम सेल arr[row][col] तक पहुंचना है जैसे कि केवल दो चालें अनुमत हैं:
- दायां कदम arr[i][j] से arr[i][j+1] तक और
- नीचे का कदम arr[i][j] से arr[i+1][j] तक।
उदाहरणों से समझते हैं।
इनपुट - arr[row][col] = {{0, 0, 0}, {-1, -1, 0}, {0, 0, 0}}
आउटपुट - भूलभुलैया में गंतव्य तक पहुंचने के तरीकों की संख्या: 1
व्याख्या
0 1 2
0 0 0 0
1 -1 -1 0
2 0 0 0
तरीके होंगे :
- सेल (0,0) → सेल (0,1) → सेल (0,2) → सेल(1,2) → सेल(2,0)
इनपुट - arr[row][col] = { {0, 0, 0, 0}, {-1, 0, -1, 0}, {-1, 0, -1, 0}, {0, 0, 0, 0}}
आउटपुट - भूलभुलैया में गंतव्य तक पहुंचने के तरीकों की संख्या: 2
व्याख्या
0 1 2 3
0 0 0 0 0
1 -1 0 -1 0
2 -1 0 -1 0
3 0 0 0 0
तरीके होंगे :
- सेल (0,0) → सेल (0,1) → सेल (1,1) → सेल(2,1) → सेल(3,1) → सेल(3,2) → सेल(3,3)
- सेल (0,0) → सेल (0,1) → सेल (0,2) → सेल(0,3) → सेल(1,3) → सेल(2,3) → सेल(3,3)
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण
इस दृष्टिकोण में हम पहले सभी शून्य को 1 सेट करेंगे। भूलभुलैया मैट्रिक्स को फिर से पार करें और अब प्रत्येक सेल के लिए, यदि यह बाधा (-1) है तो इसे अनदेखा करें। यदि नहीं, तो ऊपरी सेल (i-1,j) और बायां सेल (i,j-1) जांचें। यदि यह शून्य से अधिक है तो इसका मान वर्तमान सेल (i,j) में जोड़ें। इस तरह हमें सेल (row-1,col-1) पर योग मिलेगा जो इसे पहुंचने के कुल तरीके होंगे।
- भूलभुलैया के रूप में इनपुट सरणी arr[row][col] लें।
- फ़ंक्शन destination_maze(int arr[row][col]) arr लेता है और भूलभुलैया में गंतव्य तक पहुंचने के तरीकों की संख्या लौटाता है।
- यदि पहला सेल अवरुद्ध है तो 0 लौटाएं गंतव्य तक पहुंचने के तरीकों के रूप में।
- अब सबसे बाएं कॉलम को पार करें और सभी 0s को 1 सेट करें। पहली बाधा पर लूप तोड़ें क्योंकि इसके नीचे के सेल पहुंचे नहीं जा सकते। इंडेक्स i=0 से i<row से शुरू करें और यदि यह 0 है तो arr[i][0] को 1 सेट करें।
- इसी तरह j=0 से j<col तक पहली पंक्ति के लिए करें और यदि यह 0 है तो arr[j][0] को 1 सेट करें।
- सेल (1,1) से फिर से arr को पार करें और यदि arr[i][j] -1 है तो कुछ न करें।
- यदि arr[i-1][j] या arr[i][j-1] 0 से अधिक है तो arr[i][j] उनसे पहुंच योग्य है। तो उनका मान इसमें जोड़ें।
- अंत में हमारे पास arr[row-1][col-1] होगा इसे पहुंचने के कुल तरीकों के रूप में।
- यदि यह >0 है तो इसे लौटाएं अन्यथा 0 लौटाएं।
उदाहरण
#include<bits/stdc++.h> using namespace std; #define row 3 #define col 3 int destination_maze(int arr[row][col]) { if (arr[0][0] == -1) { return 0; } for (int i = 0; i < row; i++) { if (arr[i][0] == 0) { arr[i][0] = 1; } else { break; } } for (int i = 1; i < col; i++) { if (arr[0][i] == 0) { arr[0][i] = 1; } else { break; } } for (int i = 1; i < row; i++) { for (int j = 1; j < col; j++) { if (arr[i][j] == -1) { continue; } if (arr[i - 1][j] > 0) { arr[i][j] = (arr[i][j] + arr[i - 1][j]); } if (arr[i][j - 1] > 0) { arr[i][j] = (arr[i][j] + arr[i][j - 1]); } } } if (arr[row - 1][col - 1] > 0) { return arr[row - 1][col - 1]; } else { return 0; } } int main() { int arr[row][col] = { { 0, 0, 0 }, { -1, -1, 0 }, { 0, 0, 0 } }; cout << "Count of number of ways to reach destination in a Maze are: " << destination_maze(arr); return 0; } यदि हम उपरोक्त कोड चलाते हैं तो यह निम्नलिखित आउटपुट उत्पन्न करेगा -
आउटपुट
Count of number of ways to reach destination in a Maze are: 1
