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

একদা আকবর নামে এক সম্রাট ছিলেন। জাহাঙ্গীর নামে তার একটি ছেলে ছিল। একটি ক্ষমার অযোগ্য কারণে, রাজা তাকে রাজ্য ত্যাগ করতে চেয়েছিলেন। যেহেতু তিনি তার ছেলেকে ভালোবাসতেন, তাই তিনি সিদ্ধান্ত নিয়েছিলেন যে তার ছেলেকে একটি নতুন জায়গায় নির্বাসিত করা হবে। রাজপুত্র দুঃখ পেয়েছিলেন, কিন্তু তিনি তার পিতার ইচ্ছা অনুসরণ করেছিলেন। তিনি দেখতে পেলেন যে জায়গাটি স্থল ও জলের সংমিশ্রণ। যেহেতু তিনি সাঁতার জানতেন না, তাই তিনি কেবল জমিতে চলাফেরা করতে পেরেছিলেন। তিনি জানতেন না কত জায়গা তার গন্তব্য হতে পারে। তাই, তিনি আপনার সাহায্য চেয়েছেন.

আপনি স্থানটিকে কিছু ঘর সমন্বিত একটি আয়তক্ষেত্রাকার গ্রিড হিসাবে বিবেচনা করতে পারেন। একটি সেল একটি জমি হতে পারে বা জল থাকতে পারে। প্রতিবার রাজপুত্র তার বর্তমান অবস্থান থেকে একটি নতুন সেল যেতে পারে যদি সেইখানে স্থল থাকে।

এখন তিনি প্রাথমিকভাবে যে সেলে ছিলেন তা সহ তিনি কতগুলি সেলে পৌঁছাতে পারেন তা খুঁজে বের করার জন্য একটি প্রোগ্রাম লিখুন।

এইখানে উপরে চিত্রের ইনপুটটি দেখুন, সেখানে @ হচ্ছে Source । এই source থেকে যেই যেই সেলে যাওয়া সম্ভব সেই সেই সেলে কে গণনা করতে হবে। উপরে blue করে মার্ক করে দেয়া সেলগুলোকে গণনা করলে হয় ১২টি আর source সেলটিকে সহ গণনা করলে হয় ১৩। উপরের ইনপুটির আউটপুট হবে ১৩।

সমাধান

cin >> m >> n;
int si, sj;
for (int i = 0; i < n; i++)
{
    for (int j = 0; j < m; j++)
    {
        cin >> a[i][j];
        if (a[i][j] == '@')
        {
            si = i;
            sj = j;
        }
    }
}
cnt = 0;
memset(vis, false, sizeof(vis));
dfs(si, sj);

2D grid টি কে ইনপুট নিয়া হল। 2D grid এর মধ্যে '@' কে পেলেই সেইটিই হবে source। memset ব্যবহার করে vis array কে false করা হল। এরপর source দিয়ে dfs কে কল করা হল।

void dfs(int si, int sj)
{
    vis[si][sj] = true;
    cnt++;
    for (int i = 0; i < 4; i++)
    {
        int ci = si + d[i].first;
        int cj = sj + d[i].second;
        if (valid(ci, cj) && !vis[ci][cj] && a[ci][cj] == '.')
        {
            dfs(ci, cj);
        }
    }
}

dfs function এ প্রথমে source কে ভিজিটেড করেছি। এরপর count করেছি। এরপর আনভিজিটেড , valid এবং grid এ ডট (.) থাকলে dfs কে আবার recursive কল করতেছি।

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

#include <bits/stdc++.h>
using namespace std;
const int N = 25;
char a[N][N];
bool vis[N][N];
int cnt;
vector<pair<int, int>> d = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
int n, m;
bool valid(int ci, int cj)
{
    if (ci >= 0 && ci < n && cj >= 0 && cj < m)
        return true;
    else
        return false;
}
void dfs(int si, int sj)
{
    vis[si][sj] = true;
    cnt++;
    for (int i = 0; i < 4; i++)
    {
        int ci = si + d[i].first;
        int cj = sj + d[i].second;
        if (valid(ci, cj) && !vis[ci][cj] && a[ci][cj] == '.')
        {
            dfs(ci, cj);
        }
    }
}
int main()
{
    int t;
    cin >> t;
    int cs = 1;
    while (t--)
    {
        cin >> m >> n;
        int si, sj;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                cin >> a[i][j];
                if (a[i][j] == '@')
                {
                    si = i;
                    sj = j;
                }
            }
        }
        cnt = 0;
        memset(vis, false, sizeof(vis));
        dfs(si, sj);
        cout << "Case " << cs++ << ": " << cnt << endl;
    }
    return 0;
}