C++-এ গ্রিডে রোবটের জাম্প সংখ্যা বের করুন

h x w সাইজের একটি গ্রিড দেওয়া আছে যেখানে '#' = বাধা, '.' = পথ। রোবট কোঅর্ডিনেট c = (x,y) থেকে d = (p,q) যেতে চায়। রোবটের মুভমেন্ট নিয়ম:

1. উপর/নিচে/ডানে/বামে সন্নিকট সেলে যেতে পারে (কোস্ট ০ জাম্প)।
2. বর্তমান সেলকে কেন্দ্র করে ৫x৫ এরিয়ার যেকোনো সেলে জাম্প দিয়ে যেতে পারে (কোস্ট ১ জাম্প)।
3. বাধায় যাওয়া যায় না, গ্রিডের বাইরে যাওয়া যায় না।

গন্তব্যে পৌঁছাতে ন্যূনতম জাম্প সংখ্যা বের করুন।

উদাহরণ

ইনপুট: h=4, w=4, c={2,1}, d={4,4}, grid = {"#...",".##.", "...#", "..#."}

আউটপুট: 1 (শুধু ১ জাম্পে গিয়ে পৌঁছানো যায়)

অ্যালগরিদম (০-১ BFS / Deque BFS)

1. dst[i][j] = নোড (i,j)-এ পৌঁছাতে লাগা ন্যূনতম জাম্প।
2. শুরুতে সব INF, শুধু সোর্সে ০।
3. deque ব্যবহার: কোস্ট ০ वाले নোড push_front, কোস্ট ১ वाले push_back।
4. প্রতিটি নোড থেকে ৫x৫ এরিয়ার চেক করুন: |dx| + |dy| > 1 হলে জাম্প (কোস্ট ১), নয় তবে ওক (কোস্ট ০)।
5. যখন গন্তব্যে পৌঁছায়, dst প্রিন্ট করুন।

C++ প্রোগ্রাম

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
#define N 100
int h, w;
pair<int,int> s, t;
string grid[N];
int dst[N][N];

struct node { int a, b, e; };

bool check(int a, int b) {
    return a >= 0 && a < h && b >= 0 && b < w;
}

void bfs(int a, int b) {
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++)
            dst[i][j] = INF;
    dst[a][b] = 0;
    deque<node> dq;
    dq.push_back({a, b, 0});
    while (!dq.empty()) {
        node nd = dq.front(); dq.pop_front();
        if (nd.e > dst[nd.a][nd.b]) continue;
        for (int dx = -2; dx <= 2; dx++) {
            for (int dy = -2; dy <= 2; dy++) {
                int tm = abs(dx) + abs(dy);
                int nx = nd.a + dx, ny = nd.b + dy;
                if (check(nx, ny) && grid[nx][ny] == '.') {
                    int w = (tm > 1) ? 1 : 0;
                    if (dst[nd.a][nd.b] + w < dst[nx][ny]) {
                        dst[nx][ny] = dst[nd.a][nd.b] + w;
                        if (w == 0) dq.push_front({nx, ny, dst[nx][ny]});
                        else dq.push_back({nx, ny, dst[nx][ny]});
                    }
                }
            }
        }
    }
}

void solve(pair<int,int> c, pair<int,int> d, string initGrid[]) {
    s = c; t = d;
    s.first--; s.second--; t.first--; t.second--;
    for (int i = 0; i < h; i++) grid[i] = initGrid[i];
    bfs(s.first, s.second);
    cout << (dst[t.first][t.second] == INF ? -1 : dst[t.first][t.second]) << '\n';
}

int main() {
    h = 4; w = 4;
    pair<int,int> c = {2,1}, d = {4,4};
    string initGrid[] = {"#...", ".##.", "...#", "..#."};
    solve(c, d, initGrid);
    return 0;
}

আউটপুট

1

মূল পয়েন্ট

• ০-১ BFS ডিক utiliza করে স্ট্রেটএজ এবং জাম্প আলাদা হ্যান্ডেল করা হয়।
• সাধারণ BFS (কিউ) দিয়ে ও করা যায় কিন্তু ০-১ BFS দ্রুত।
• গ্রিড সাইজ ১০০x১০০ পর্যন্ত এই কোড কাজ করবে।