একটি প্রদত্ত ম্যাট্রিক্সে, উপাদানের অবস্থান বিশ্লেষণ করার জন্য চারটি বস্তু রয়েছে:বাম, ডান, নীচে এবং উপরে৷
ব্রেডথ ফার্স্ট সার্চ প্রদত্ত 2-ডি ম্যাট্রিক্সের দুটি উপাদানের মধ্যে সবচেয়ে কম দূরত্ব খুঁজে পাওয়া ছাড়া আর কিছুই নয়। এইভাবে প্রতিটি কক্ষে, চারটি ক্রিয়াকলাপ আমরা সম্পাদন করতে পারি যা চারটি সংখ্যায় প্রকাশ করা যেতে পারে যেমন,
- '2' বর্ণনা করে যে ম্যাট্রিক্সের সেলটি উৎস।
- '3' বর্ণনা করে যে ম্যাট্রিক্সের ঘরটি গন্তব্য।
- '1' বর্ণনা করে যে সেলটিকে আরও একটি দিকে সরানো যেতে পারে।
- '0' বর্ণনা করে যে ম্যাট্রিক্সের ঘরটি কোনো দিকে সরানো যাবে না।
অ্যাডোব ন্যায্যতার ভিত্তিতে, আমরা একটি প্রদত্ত ম্যাট্রিক্সে একটি ব্রেডথ ফার্স্ট সার্চ অপারেশন করতে পারি৷
এই সমস্যা সমাধানের পদ্ধতি
সম্পূর্ণ ম্যাট্রিক্স অতিক্রম করার এবং BFS ব্যবহার করে যেকোন কক্ষের মধ্যে সর্বনিম্ন বা সর্বনিম্ন দূরত্ব খুঁজে বের করার অ্যালগরিদম নিম্নরূপ:
- প্রথমে ইনপুট সারি এবং কলাম নিন।
- প্রদত্ত সারি এবং কলাম দিয়ে একটি ম্যাট্রিক্স শুরু করুন।
- একটি পূর্ণসংখ্যা ফাংশন shortestDist(int row, int col, int mat[][col]) সারি, কলাম এবং ম্যাট্রিক্সকে ইনপুট হিসাবে নেয় এবং ম্যাট্রিক্সের উপাদানগুলির মধ্যে সবচেয়ে কম দূরত্ব প্রদান করে।
- উৎস এবং গন্তব্য উপাদান খুঁজে বের করতে পরিবর্তনশীল উৎস এবং গন্তব্য শুরু করুন।
- উপাদানটি '3' হলে সেটিকে গন্তব্য হিসেবে চিহ্নিত করুন এবং যদি উপাদানটি '2' হয়, তাহলে সেটিকে উৎস উপাদান হিসেবে চিহ্নিত করুন।
- প্রদত্ত ম্যাট্রিক্সে ব্রেডথ ফার্স্ট সার্চ বাস্তবায়ন করতে এখন কিউ ডেটা স্ট্রাকচার শুরু করুন।
- ম্যাট্রিক্সের সারি এবং কলাম জোড়া হিসেবে সারিতে ঢোকান। এখন কক্ষে যান এবং এটি একটি গন্তব্য সেল কিনা তা খুঁজে বের করুন। যদি গন্তব্য সেলের দূরত্ব বর্তমান সেলের থেকে ন্যূনতম বা কম থাকে, তাহলে দূরত্ব আপডেট করুন৷
- বর্তমান সেল থেকে সেলের ন্যূনতম দূরত্ব জানতে আবার অন্য দিকে যান।
- আউটপুট হিসাবে সর্বনিম্ন দূরত্ব ফেরত দিন।
উদাহরণ
#include<bits/stdc++.h>
using namespace std;
int findDistance(int row, int col, int mat[][5]) {
int source_i, source_j, destination_i, destination_j;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (mat[i][j] == 2) {
source_i = i;
source_j = j;
}
if (mat[i][j] == 3) {
destination_i = i;
destination_j = j;
}
}
}
int dist[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++)
dist[i][j] = INT_MAX;
}
// initialise queue to start BFS on matrix
queue < pair < int, int >> q;
q.push(make_pair(source_i, source_j));
dist[source_i][source_j] = 0;
// modified BFS by add constraint checks
while (!q.empty()) {
// storing the x co-ordinate or row information of cell
int x = q.front().first;
// storing the y co-ordinate or column information of cell
int y = q.front().second;
// Remove the cell from queue
q.pop();
// If move towards left is allowed or it is the destnation cell
if (y - 1 >= 0 && (mat[x][y - 1] == 1 || mat[x][y - 1] == 3)) {
// if distance to reach the cell to the left is less than the computed previous path distance, update it
if (dist[x][y] + 1 < dist[x][y - 1]) {
dist[x][y - 1] = dist[x][y] + 1;
q.push(mkp(x, y - 1));
}
}
// If move towards right is allowed or it is the destination cell
if (y + 1 < col && (mat[x][y + 1] == 1 || mat[x][y + 1] == 3)) {
// if distance to reach the cell to the right is less than the computed previous path distance, update it
if (dist[x][y] + 1 < dist[x][y + 1]) {
dist[x][y + 1] = dist[x][y] + 1;
q.push(mkp(x, y + 1));
}
}
// If upward direction is allowed
if (x - 1 >= 0 && (mat[x - 1][y] == 1 || mat[x - 1][y] == 3)) {
if (dist[x][y] + 1 < dist[x - 1][y]) {
dist[x - 1][y] = dist[x][y] + 1;
q.push(mkp(x - 1, y));
}
}
// If downward direction allowed
if (x + 1 < row && (mat[x + 1][y] == 1 || mat[x + 1][y] == 3)) {
// if distance to reach the cell to the down is less than the computed previous path distance, update it
if (dist[x][y] + 1 < dist[x + 1][y]) {
dist[x + 1][y] = dist[x][y] + 1;
q.push(mkp(x + 1, y));
}
}
}
return dist[destination_i][destination_j];
}
int main() {
// initialising number of rows and columns
int row = 5;
int col = 5;
// initialising matrix
int mat[][5] = {
{1, 0, 0, 2, 1},
{1, 0, 1, 1, 1},
{0, 1, 1, 2, 0},
{3, 1, 0, 0, 1},
{1, 1, 0, 0, 1}
};
int answer = findDistance(row, col, mat);
// When source and destination are unreachable
if (answer == INT_MAX)
cout << "No Path Found" << endl;
else {
cout << "The Shortest Distance between Source and Destination is:" << endl;
cout << answer << endl;
}
return 0;
} আউটপুট
The Shortest Distance between Source and Destination is:4
