C++-এ The Maze II সমস্যা: গোলাপταν গেঁদের ন্যূনতম দূরত্ব

ধরি একটি মেইজ (maze) আছে যাতে খালি স্থান (empty space) এবং দেওয়াল (wall) রয়েছে। একটি গোলাপتان গেঁদ (ball) খালি পথ দিয়ে যেকোনো দিকে (উপর, নিচ, বাম, ডান) রোল করতে পারে, কিন্তু এটি থামবে না যতক্ষণ না একটি দেওয়ালে ধাক্কা খায়। গেঁদ থামলে সেটি পরবর্তী দিক বেছে নিতে পারে।

আমাদের গেঁদের শুরুর পজিশন (start), গন্তব্য (destination) এবং মেইজ দেওয়া আছে। লক্ষ্য হলো গেঁদ গন্তব্যে থামানোর জন্য ন্যূনতম দূরত্ব বের করা। দূরত্ব বলতে খালি সেল (empty cells) সংখ্যা বোঝানো হয়েছে যা গেঁদ কভার করেছে (শুরু পজিশন বাদ, শেষ পজিশন সহ)। যদি গন্তব্যে গেঁদ থামানো অসম্ভব হয়, তবে -১ রিটার্ন করুন।

মেইজটি ২D অ্যারে দিয়ে উপস্থাপিত: ১ = দেওয়াল, ০ = খালি স্থান। মেইজের বর্ডারগুলো সব দেওয়াল। শুরুর এবং গন্তব্যের কোঅর্ডিনেট রো এবং কলাম ইনডেক্স দিয়ে দেওয়া হয়।

উদাহরণ: মেইজ =

0	0	1	0	0
0	0	0	0	0
0	0	0	1	0
1	1	0	1	1
0	0	0	0	0

start = (0, 4), destination = (4, 4) হলে আউটপুট = ১২। এক সম্ভাব্য পথ: বাম → নিচ → বাম → নিচ → ডান → নিচ → ডান। দূরত্ব = (১+১+৩+১+২+২+২) = ১২।

C++-এ The Maze II সমস্যা: গোলাপταν গেঁদের ন্যূনতম দূরত্ব

সমাধানের ধাপসমূহ:

n := row count, m := column count
ret := infinity
dist[n][m] ২D অ্যারে ডিফাইন করুন
কিউ q ডিফাইন করুন
start কিউতে পুশ করুন
dist[start[0]][start[1]] := 0
while (!q.empty()):
- curr := q.front(), q.pop()
- x := curr[0], y := curr[1]
- যদি x == destination[0] && y == destination[1]: ret = min(ret, dist[x][y])
- currDist := dist[x][y]
- চার দিকেই (উপর, নিচ, বাম, ডান) গেঁদ রোল করান:
  - দিকভাগে যতক্ষণ খালি সেল পাওয়া যায়, tempDist বাড়ান
  - যদি currDist + tempDist < dist[newX][newY] হয়: dist[newX][newY] = currDist + tempDist, নতুন পজিশন কিউতে পুশ করুন
return (ret == INF ? -1 : ret)

উদাহরণ

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int shortestDistance(vector<vector<int>>& grid, vector<int>& start, vector<int>& destination) {
        int n = grid.size();
        int m = n ? grid[0].size() : 0;
        int ret = INT_MAX;
        vector<vector<int>> dist(n, vector<int>(m, INT_MAX));
        queue<vector<int>> q;
        q.push(start);
        dist[start[0]][start[1]] = 0;
        while (!q.empty()) {
            vector<int> curr = q.front();
            q.pop();
            int x = curr[0];
            int y = curr[1];
            if (x == destination[0] && y == destination[1]) {
                ret = min(ret, dist[x][y]);
            }
            int currDist = dist[x][y];
            int tempDist = 0;
            int i = x;
            // নিচে
            while (i + 1 < n && !grid[i + 1][y]) {
                i++; tempDist++;
            }
            if (currDist + tempDist < dist[i][y]) {
                dist[i][y] = currDist + tempDist;
                q.push({i, y});
            }
            // উপরে
            i = x; tempDist = 0;
            while (i - 1 >= 0 && !grid[i - 1][y]) {
                tempDist++; i--;
            }
            if (currDist + tempDist < dist[i][y]) {
                dist[i][y] = currDist + tempDist;
                q.push({i, y});
            }
            // বামে
            i = y; tempDist = 0;
            while (i - 1 >= 0 && !grid[x][i - 1]) {
                i--; tempDist++;
            }
            if (currDist + tempDist < dist[x][i]) {
                dist[x][i] = currDist + tempDist;
                q.push({x, i});
            }
            // ডানে
            i = y; tempDist = 0;
            while (i + 1 < m && !grid[x][i + 1]) {
                i++; tempDist++;
            }
            if (currDist + tempDist < dist[x][i]) {
                dist[x][i] = currDist + tempDist;
                q.push({x, i});
            }
        }
        return ret == INT_MAX ? -1 : ret;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{0,0,1,0,0},{0,0,0,0,0},{0,0,0,1,0},{1,1,0,1,1},{0,0,0,0,0}};
    vector<int> v1 = {0,4}, v2 = {4,4};
    cout << (ob.shortestDistance(v, v1, v2));
}

ইনপুট

{{0,0,1,0,0},{0,0,0,0,0},{0,0,0,1,0},{1,1,0,1,1},{0,0,0,0,0}}, {0,4}, {4,4}