विचार करें कि हमारे पास 2D सरणी है। हमें यह पता लगाना है कि क्या हमें ऊपरी बाएँ कोने से नीचे-दाएँ कोने तक का रास्ता मिल सकता है। मैट्रिक्स 0s और 1s से भरा है। 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 |
एक पथ को हरे रंग से चिह्नित किया गया है, कुछ अन्य पथ भी हैं। तो कार्यक्रम सही होगा, अगर कोई रास्ता है, अन्यथा गलत है।
हम सभी सुलभ नोड को -1 में बदलकर इस समस्या को हल करेंगे, पहले शुरुआती बिंदु के मान को -1 में बदलें, फिर पहली पंक्ति में अगला मान प्राप्त करें, और पिछले मान की तुलना करें, वर्तमान मान को पिछले मान के बराबर सेट करें अगर यह पहुंच योग्य है (0 नहीं)। कॉलम मानों के लिए भी ऐसा ही करें। पिछले कॉलम मानों के साथ वर्तमान की तुलना और सेट करके यदि वह उपलब्ध है। फिर पहली पंक्ति, पहले कॉलम से शुरू करें, और पिछली पंक्ति, पिछले कॉलम के मान लें, उनके बीच न्यूनतम प्राप्त करें। और वर्तमान सूचकांक को न्यूनतम में सेट करें। यदि वर्तमान सूचकांक 1 है, तो कोई परिवर्तन नहीं है। अंत में यदि अंतिम सूचकांक नीचे-दाईं ओर के समान है, तो सही है, अन्यथा गलत है।
उदाहरण
#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