একটি সারি X কোল ম্যাট্রিক্স হিসাবে উপস্থাপিত একটি গোলকধাঁধা দেওয়া হয়েছে যেখানে বাধাটিকে -1 হিসাবে উপস্থাপন করা হয়েছে এবং একটি পরিষ্কার কক্ষের -1 ছাড়া অন্য মান রয়েছে। লক্ষ্য হল প্রথম সেল arr[0][0] থেকে শুরু করা এবং শেষ সেল arr[row][col] এ পৌঁছানো যাতে শুধুমাত্র দুটি মুভ অনুমোদিত হয়:
- arr[i][j] থেকে arr[i][j+1] এবং ডানদিকে সরান
- Arr[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)
ইনপুট - arr[row][col] ={ {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] কে Maze হিসাবে নিন।
- ফাংশন destination_maze(int arr[row][col]) arr নেয় এবং একটি গোলকধাঁধায় গন্তব্যে পৌঁছানোর উপায়ের সংখ্যা ফেরত দেয়।
- যদি প্রথম সেলটি ব্লক করা হয় তাহলে শেষ পর্যন্ত পৌঁছানোর উপায় হিসেবে 0 ফেরত দিন।
- এখন বামদিকের কলামটি অতিক্রম করুন এবং সমস্ত 0s-এ 1 সেট করুন। প্রথমে ব্লকেজ লুপটি ভেঙে দেয় কারণ নীচের কক্ষগুলিতে পৌঁছানো যায় না। সূচী i=0 থেকে i<রোতে শুরু করুন এবং arr[i][0] 0 হলে 1 এ সেট করুন।
- প্রথম সারির জন্য একইভাবে j=0 থেকে j
- সেল (1,1) থেকে আবার arr অতিক্রম করুন এবং 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
