বিবেচনা করুন আমাদের একটি ২D অ্যারে আছে। আমাদের টপ-লেফট কর্নার থেকে বটম-রাইট কর্নার পর্যন্ত পাথ আছে কিনা তা বের করতে হবে। ম্যাট্রিক্স ০ এবং ১ দিয়ে ভরা আছে। ০ মানে খালি স্থান, ১ মানে বাধা। নোট করুন টপ-লেফট কর্নার সবসময় ১ হবে।
ধরুন একটি ম্যাট্রিক্স নিচের মত:
| 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 করব, তারপর প্রথম সারির পরবর্তী মান নিব এবং পূর্ববর্তী মানের সাথে তুলনা করব, করেন্ট ভ্যালুকে পূর্ববর্তী ভ্যালুর সমান করব যদি সেটি পৌঁছানো যায় (০ নয়)। কলামের জন্যও একই কাজ করব। তারপর প্রথম সারি, প্রথম কলাম থেকে শুরু করে পূর্ববর্তী সারি, পূর্বvious কলামের মান নিয়ে মিনিমাম বের করব এবং করেন্ট ইনডেক্সে সেট করব। যদি করেন্ট ইনডেক্স ১ হয়, তবে কোনো পরিবর্তন নেই। শেষে যদি ফাইনাল ইনডেক্স বটম-রাইটের সমান হয়, তবে 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
