মডিউল ৩_৫ঃ 2D গ্রীডে BFS ইমপ্লিমেন্টশন

2D গ্রীডে BFS ইমপ্লিমেন্টশন

আমরা এখন 2D গ্রীডে DFS ইমপ্লিমেন্টশন স্টেপ বাই স্টেপ কোড এ দেখার চেষ্টা করব।

প্রথমে n ( number of rows ) এবং m ( number of columns ) ইনপুট নিয়া হল। এরপর একটি নেস্টেড লুপ চালিয়ে 2D গ্রীডটি ইনপুট নেয়া হল।

cin >> n >> m;
for (int i = 0; i < n; i++)
{
    for (int j = 0; j < m; j++)
    {
        cin >> a[i][j];
    }
}

এরপর source হিসেবে si, sj ইনপুট নেয়া হল। memset দিয়ে ভিজিটেড এ্যারেটি ইনিশিয়ালাইজ করে নিচ্ছি false হিসেবে এবং dis এ্যারেটি ইনিশিয়ালাইজ করে নিচ্ছি -1 হিসেবে। এরপর bfs function কে কল করেছি এবং সেইখানে argument হিসেবে source এর si, sj কে পাঠিয়েছি।

int si, sj;
cin >> si >> sj;
memset(vis, false, sizeof(vis));
memset(dis, -1, sizeof(dis));
bfs(si, sj);

valid function টি দিয়ে i এবং j কোন invalid index এ চলে গিয়েছে কিনা সেইটি চেক করা হয়।

bool valid(int i, int j)
{
    if (i < 0 || i >= n || j < 0 || j >= m)
        return false;
    return true;
}

bfs function টি source এর si , sj কে parameter হিসেবে নিবে। এরপর source কে queue এর মধ্যে পুশ করে দেয়া হয়েছে এবং source নোডটি dis কে 0 ধরা হয়েছে।

এরপর একটি লুপ চালানো হচ্ছে ততক্ষন যতক্ষন না queue টি খালি হচ্ছে নাহ। লুপের ভিতর queue থেকে সেলটির ইনডেক্সকে সংগ্রহ করা হয়েছে এবং এরপর একটি লুপ চালানো হয়েছে ৪ বার। সেই লুপের মাধ্যমে ইনডেক্স সংগ্রহ করা সেল ( অর্থাৎ নোড) এর উপরে , নিচে, বামে এবং ডানে আনভিজিটেড সেল আছে কিনা চেক করা হচ্ছে, যদি আনভিজিটেড সেল পাওয়া যায় তাহলে সেই সেল এর ইনডেক্স কে queue টিতে পুশ করে দেয়া হচ্ছে এবং সেই সেলটিকে ভিজিটেড করা হচ্ছে। এর সাথে সেই সেলটির distance আগের সেলটির distance থেকে 1 বেশি, সেইটিকে dis এ্যারেটিতে সংরক্ষণ করা হচ্ছে।

void bfs(int si, int sj)
{
    queue<pair<int, int>> q;
    q.push({si, sj});
    vis[si][sj] = true;
    dis[si][sj] = 0;
    while (!q.empty())
    {
        pair<int, int> par = q.front();
        int a = par.first, b = par.second;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int ci = a + d[i].first;
            int cj = b + d[i].second;
            if (valid(ci, cj) == true && vis[ci][cj] == false)
            {
                q.push({ci, cj});
                vis[ci][cj] = true;
                dis[ci][cj] = dis[a][b] + 1;
            }
        }
    }
}

এইভাবে 2D গ্রীডে BFS দিয়ে ট্রাভাসাল করা হয়।

---

সম্পূর্ণ কোড 2D গ্রীডে BFS ইমপ্লিমেন্টশনের

#include <bits/stdc++.h>
using namespace std;
bool vis[20][20];
int dis[20][20];
vector<pair<int, int>> d = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
int n, m;
char a[20][20];
bool valid(int i, int j)
{
    if (i < 0 || i >= n || j < 0 || j >= m)
        return false;
    return true;
}

void bfs(int si, int sj)
{
    queue<pair<int, int>> q;
    q.push({si, sj});
    vis[si][sj] = true;
    dis[si][sj] = 0;
    while (!q.empty())
    {
        pair<int, int> par = q.front();
        int a = par.first, b = par.second;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int ci = a + d[i].first;
            int cj = b + d[i].second;
            if (valid(ci, cj) == true && vis[ci][cj] == false)
            {
                q.push({ci, cj});
                vis[ci][cj] = true;
                dis[ci][cj] = dis[a][b] + 1;
            }
        }
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> a[i][j];
        }
    }
    int si, sj;
    cin >> si >> sj;
    memset(vis, false, sizeof(vis));
    memset(dis, -1, sizeof(dis));
    bfs(si, sj);
    cout << dis[2][3];
    return 0;
}