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

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

আমরা এখন 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 হিসেবে। dfs function কে কল করেছি এবং সেইখানে argument হিসেবে source এর si, sj কে পাঠিয়েছি।

int si, sj;
cin >> si >> sj;
memset(vis, false, sizeof(vis));
dfs(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;
}

dfs function টি source এর si , sj কে parameter হিসেবে নিবে। এরপর source কে প্রিন্ট করা হয়েছে এবং সেই source টিকে ভিজিটেড করা হয়েছে।

এরপর একটি লুপ চালানো হয়েছে ৪ বার। সেই লুপের মাধ্যমে সেল ( অর্থাৎ নোড) এর উপরে , নিচে, বামে এবং ডানে আনভিজিটেড সেল আছে কিনা চেক করা হচ্ছে, যদি আনভিজিটেড সেল পাওয়া যায় তাহলে সেই সেল এর ইনডেক্স দিয়ে dfs function কে recursive কল করা হচ্ছে।

void dfs(int si, int sj)
{
    cout << si << " " << sj << endl;
    vis[si][sj] = true;
    for (int i = 0; i < 4; i++)
    {
        int ci = si + d[i].first;
        int cj = sj + d[i].second;
        if (valid(ci, cj) == true && vis[ci][cj] == false)
        {
            dfs(ci, cj);
        }
    }
}

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

---

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

#include <bits/stdc++.h>
using namespace std;
char a[20][20];
bool vis[20][20];
vector<pair<int, int>> d = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
int n, m;
bool valid(int i, int j)
{
    if (i < 0 || i >= n || j < 0 || j >= m)
        return false;
    return true;
}
void dfs(int si, int sj)
{
    cout << si << " " << sj << endl;
    vis[si][sj] = true;
    for (int i = 0; i < 4; i++)
    {
        int ci = si + d[i].first;
        int cj = sj + d[i].second;
        if (valid(ci, cj) == true && vis[ci][cj] == false)
        {
            dfs(ci, cj);
        }
    }
}
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));
    dfs(si, sj);
    return 0;
}