আমাদের একটি 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
