मान लीजिए हमारे पास एक 2D सरणी है। हमें जांचना है कि क्या हम ऊपरी-बाएं कोने से नीचे-दाएं कोने तक पथ प्राप्त कर सकते हैं। मैट्रिक्स 0 और 1 से भरा है। 0 खुले क्षेत्र को इंगित करता है, 1 रुकावट को इंगित करता है। ध्यान दें कि ऊपरी-बाएं कोना हमेशा 1 होगा।
मान लीजिए एक मैट्रिक्स नीचे जैसी है -
| 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 |
एक पथ हरे रंग से चिह्नित है, कुछ अन्य पथ भी हैं। तो प्रोग्राम true लौटाएगा यदि पथ है, अन्यथा false।
हम इस समस्या को हल करेंगे, सभी पहुंच योग्य नोड्स को -1 में बदलकर। पहले शुरुआती बिंदु का मान -1 में बदलें, फिर पहली पंक्ति में अगला मान प्राप्त करें, और पिछले मान से तुलना करें, वर्तमान मान को पिछले मान के बराबर सेट करें यदि यह पहुंच योग्य है (0 नहीं)। स्तंभ मानों के लिए भी वही करें। पिछले स्तंभ मानों के साथ तुलना करके और यदि वह पहुंच योग्य है तो वर्तमान को सेट करके। फिर पहली पंक्ति, पहले स्तंभ से शुरू करके, पिछली पंक्ति, पिछले स्तंभ के मान लें, उनके बीच न्यूनतम प्राप्त करें। और वर्तमान इंडेक्स को न्यूनतम में सेट करें। यदि वर्तमान इंडेक्स 1 है, तो कोई परिवर्तन नहीं। अंत में यदि अंतिम इंडेक्स नीचे-दाएं के समान है, तो true लौटाएं, अन्यथा false।
उदाहरण
#include <iostream> #define row 5 #define col 5 using namespace std; bool isPathPresent(int arr[row][col]) { arr[0][0] = -1; for (int i = 1; i < row; i++) if (arr[i][0] != 1) arr[i][0] = arr[i - 1][0]; for (int j = 1; j < col; j++) if (arr[0][j] != 1) arr[0][j] = arr[0][j - 1]; for (int i = 1; i < row; i++) for (int j = 1; j < col; j++) if (arr[i][j] != 1) arr[i][j] = min(arr[i][j - 1], arr[i - 1][j]); return (arr[row - 1][col - 1] == -1); } int main() { int arr[row][col] = {{ 0, 0, 0, 1, 0}, {1, 0, 0, 1, 1}, { 0, 0, 0, 1, 0}, {1, 0, 0, 0, 0}, { 0, 0, 1, 0, 0}}; if (isPathPresent(arr)) cout << "Path is present"; else cout << "No path has found"; }आउटपुट
Path is present
