एक भूलभुलैया को एक पंक्ति X कॉलम मैट्रिक्स के रूप में दर्शाया गया है जिसमें बाधा को -1 के रूप में दर्शाया गया है और एक स्पष्ट सेल का मान -1 के अलावा है। लक्ष्य पहली सेल एआर [0] [0] से शुरू करना है और आखिरी सेल एआर [पंक्ति] [कॉल] तक पहुंचना है, जैसे कि केवल दो चालों की अनुमति है:
- गिरफ्तारी[i][j] को गिरफ्तार करने के लिए सही कदम[i][j+1] और
- गिरफ्तारी [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)
इनपुट - एआर [पंक्ति] [कॉल] ={{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) में जोड़ें। इस तरह हमें सेल पर योग (पंक्ति-1, कॉलम-1) तक पहुंचने के कुल तरीकों के रूप में मिलेगा।
- इनपुट ऐरे arr[row][col] को भूलभुलैया के रूप में लें।
- Function definition_maze(int arr[row][col]) गिरफ्तारी लेता है और भूलभुलैया में गंतव्य तक पहुंचने के तरीकों की संख्या देता है।
- यदि पहली सेल अवरुद्ध है तो अंत तक पहुंचने के तरीके के रूप में 0 लौटाएं।
- अब सबसे बाएं कॉलम को पार करें और सभी 0s को 1 पर सेट करें। सबसे पहले रुकावट लूप को तोड़ती है क्योंकि इसके नीचे की कोशिकाओं तक नहीं पहुंचा जा सकता है। अनुक्रमणिका i=0 से i<पंक्ति तक प्रारंभ करें और arr[i][0] को 1 पर सेट करें यदि यह 0 है।
- इसी तरह पहली पंक्ति के लिए j=0 से j
- गिरफ्तारी को फिर से सेल (1,1) से पार करें और अगर 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