২D ম্যাট্রিক্সে সোর্স (২) থেকে ডেস্টিনেশন (৩) পর্যন্ত শর্টেস্ট পাথ বের করতে BFS ব্যবহার করা হয়। ১ = যাওয়া যায়, ০ = ব্লক।
অ্যালগরিদম
- সোর্স এবং ডেস্টিনেশন কোঅর্ডিনেট খুঁজুন।
- দূরত্ব ম্যাট্রিক্স INT_MAX দিয়ে ইনিশিয়ালাইজ করুন।
- কিউতে (row, col) পেয়ার পুশ করুন। ৪ দিক (আপ, ডাউন, লেফ্ট, রাইট) এক্সপ্লোর করুন।
- যদি নতুন দূরত্ব কম হয়, তবে আপডেট করে কিউতে পুশ করুন।
- ডেস্টিনেশনের দূরত্ব রিটার্ন করুন।
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
int findDistance(int row, int col, int mat[][5]) {
int si, sj, di, dj;
// সোর্স (২) ও ডেস্টিনেশন (৩) খুঁজুন
for (int i=0; i<row; i++)
for (int j=0; j<col; j++) {
if (mat[i][j]==2) { si=i; sj=j; }
if (mat[i][j]==3) { di=i; dj=j; }
}
vector<vector<int>> dist(row, vector<int>(col, INT_MAX));
queue<pair<int,int>> q;
q.push({si, sj});
dist[si][sj] = 0;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
for (int k=0; k<4; k++) {
int nx = x + dx[k], ny = y + dy[k];
if (nx>=0 && nx<row && ny>=0 && ny<col &&
(mat[nx][ny]==1 || mat[nx][ny]==3) &&
dist[x][y] + 1 < dist[nx][ny]) {
dist[nx][ny] = dist[x][y] + 1;
q.push({nx, ny});
}
}
}
return dist[di][dj];
}
int main() {
int mat[5][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 ans = findDistance(5, 5, mat);
if (ans == INT_MAX) cout << "No Path Found";
else cout << "Shortest Distance: " << ans;
return 0;
}
আউটপুট
Shortest Distance: 4
