মডিউল ১৫_১ঃ Sundorban ইমপ্লিমেন্টেশন সহ

বঙ্গোপসাগরে গঙ্গা, ব্রহ্মপুত্র এবং মেঘনা নদীর ব-দ্বীপে অবস্থিত সুন্দরবনের ম্যানগ্রোভ বন, বিশ্বের অন্যতম বৃহত্তম বন (১৪০,০০০ হেক্টর)। এটি 1987 সালে খোদিত ভারতের সুন্দরবন বিশ্ব ঐতিহ্যবাহী স্থানের সীমানা সংলগ্ন।

ধরুন আপনি সুন্দরবনের একটি ঘন এলাকায় হারিয়ে গেলেন এবং অন্ধকার হয়ে আসছে। কমপক্ষে একটি পথ রয়েছে যা আপনাকে অন্য দিকে শহরের দিকে নিয়ে যায় তবে আপনি ঠিক তার সামনে না আসা পর্যন্ত আপনি কিছুই দেখতে পারবেন না কারণ গাছ এবং ঝোপগুলি পথটিকে অস্পষ্ট করে।

এখন একটি উপায় খুঁজে বের করুন। আপনার লক্ষ্য হল অন্ধকার হওয়ার আগে যত দ্রুত সম্ভব জঙ্গল থেকে বেরিয়ে যাওয়া।

ইনপুটঃ

একটি সংখ্যা N দিয়ে ইনপুট শুরু করুন এবং তারপর S, E, T, এবং P রয়েছে এমন একটি N x N আকারের ম্যাট্রিক্স আছে। সেইখানে S রয়েছে start point হিসেবে রিপ্রেজেন্ট করে এবং E রয়েছে end point হিসেবে রিপ্রেজেন্ট করে এবং P পথকে রিপ্রেজেন্ট করে এবং T ট্রিকে রিপ্রেজেন্ট করে। ইনপুট EOF দ্বারা terminate হয়।

আউটপুটঃ

আপনার থেকে বের করতে হবে , S থেকে E তে যেতে সর্বনিম্ন কতটি moves করতে হবে।

এইখানে S হচ্ছে source এবং E হচ্ছে Destination. আপনি শুধুমাত্র P কে পেলে movement করতে পারবেন। T কে পেলে movement করতে পারবেন নাহ।

 while (cin >> n)
{
    int si, sj;
    int di, dj;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> a[i][j];
            if (a[i][j] == 'S')
            {
                si = i;
                sj = j;
            }
            if (a[i][j] == 'E')
            {
                di = i;
                dj = j;
            }
        }
    }
    memset(vis, false, sizeof(vis));
    memset(dis, -1, sizeof(dis));
    bfs(si, sj);
    cout << dis[di][dj] << endl;
}

এই প্রব্লেমের প্রশ্নে EOF ব্যবহার করতে বলা হয়েছে। তাই আমরা EOF ব্যবহার করে ইনপুট নিচ্ছি। এরপর matrix টিকে ইনপুট নিয়েছি, সেইখানে Source এবং destination এর ইনডেক্স বের করে রেখেছি। memset ব্যবহার করে vis এবং dis array কে যথাক্রমে false এবং -1 দিয়ে initialize করেছি। Source এর ইনডেক্স দিয়ে bfs কে কল করেছি। bfs function টি complete হওয়ার পর , আমরা dis array এর destination এর ইনডেক্সের মধ্যে Source থেকে Destination এর দূরত্ব আউটপুট দেখিয়েছি।

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

bfs function এ আমরা grid এর মধ্যে 'P' কে পেলে movement করতেছি, এইভাবে যেই যেই নোডে যাওয়া সম্ভব সব নোড ভিজিটেড করছি এবং source থেকে ভিজিটেড সব নোডের দূরত্ব dis array তে store করে রাখছি।

সম্পূর্ণ কোডটি

#include <bits/stdc++.h>
using namespace std;
char a[50][50];
bool vis[50][50];
int dis[50][50];
int n;
vector<pair<int, int>> d;
bool valid(int ci, int cj)
{
    if (ci >= 0 && ci < n && cj >= 0 && cj < n)
        return true;
    else
        return false;
}
void bfs(int si, int sj)
{
    queue<pair<int, int>> q;
    q.push({si, sj});
    dis[si][sj] = 0;
    vis[si][sj] = true;
    while (!q.empty())
    {
        pair<int, int> par = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int ci = par.first + d[i].first;
            int cj = par.second + d[i].second;
            if (valid(ci, cj) && !vis[ci][cj] && a[ci][cj] != 'T')
            {
                q.push({ci, cj});
                vis[ci][cj] = true;
                dis[ci][cj] = dis[par.first][par.second] + 1;
            }
        }
    }
}
int main()
{
    d.push_back({0, 1});
    d.push_back({0, -1});
    d.push_back({-1, 0});
    d.push_back({1, 0});
    while (cin >> n)
    {
        int si, sj;
        int di, dj;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cin >> a[i][j];
                if (a[i][j] == 'S')
                {
                    si = i;
                    sj = j;
                }
                if (a[i][j] == 'E')
                {
                    di = i;
                    dj = j;
                }
            }
        }
        memset(vis, false, sizeof(vis));
        memset(dis, -1, sizeof(dis));
        bfs(si, sj);
        cout << dis[di][dj] << endl;
    }
    return 0;
}