C++-এ The Maze III সমস্যা সমাধান

ধরি একটি মেজ (maze) আছে যেখানে খালি জায়গা এবং দেওয়াল আছে। মেজে একটি বলও আছে। বলটি খালি জায়গা দিয়ে উপরে (u), নিচে (d), বামে (l) বা ডানে (r) দিয়ে লুতে পারে, কিন্তু এটি দেওয়াল ধাক্কা খাওয়া পর্যন্ত লুতে থাকে। বলটি থামলে এরপর এর দিক পরিবর্তন করতে পারে। মেজে একটি গর্ত (hole)ও আছে। বলটি যদি গর্তের ওপর লুড়ে যায় তবে সেটি গর্তে পড়ে যাবে।

বলটির অবস্থান, গর্তের অবস্থান এবং মেজ দেওয়া থাকলে, বলটি কীভাবে সবচেয়ে ছোট দুরত্বে গর্তে পড়তে পারে তা বের করতে হবে। দূরত্ব বলтся বলটি শুরুর পজিশন (এটি বাদ দিয়ে) থেকে গর্ত (এটি অন্তর্ভুক্ত করে) পর্যন্ত কতগুলো খালি জায়গা পার করেছে।

চালানোর দিক 'u', 'd', 'l', 'r' দিয়ে দেখাতে হবে। একাধিক সবচেয়ে ছোট পথ থাকতে পারে, এবং আউটপুট হবে লেক্সিকোগ্রাফিক্যালি (lexicographically) সবচেয়ে ছোট পথ। যদি বলটি গর্তে পৌঁছাতে না পারলে "impossible" দেখাতে হবে।

মেজটি বাইনারি ম্যাট্রিক্স দিয়ে প্রতিনিধিত্ব করা হয়। 1 মানে দেওয়াল এবং 0 মানে খালি জায়গা। বল এবং গর্তের কোঅর্ডিনেট সারি এবং কলাম ইনডেক্স দিয়ে দেওয়া হয়।

উদাহরণস্বরূপ, যদি ইনপুট হয় নিচের মেজটি, তবে আউটপুট হবে 'lul' (বামে, তারপর উপরে, তারপর আবার বামে)। অন্য একটি পথ হতে পারে 'ul' (উপরে, তারপর বামে), দুটোর দৈর্ঘ্য 6, কিন্তু 'lul' লেক্সিকোগ্রাফিক্যালি 'ul'-এর চেয়ে ছোট।

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

• Data নামক একটি ডাটা টাইপ সংজ্ঞায়িত করা: এটি distance, একটি স্ট্রিং d, এবং কোঅর্ডিনেট x, y ধারণ করবে।
• dir অ্যারে আকার 4 x 2 := {{1, 0}, {0, -1}, {0, 1}, {-1, 0}}
• dirst অ্যারে আকার 4 := {'d', 'l', 'r', 'u'}
• ok() ফাংশন সংজ্ঞায়িত করা: এটি x1, y1, x2, y2 নিবে এবং x1==x2 এবং y1==y2 হলে true ফেরত দেবে।
• মেইন মেথড থেকে:
  • n := মেজের সারি সংখ্যা
  • m := (n নন-জিরো হলে মেজের কলাম সংখ্যা, অন্যথায় 0)
  • একটি প্রায়োরিটি কিউ pq সংজ্ঞায়িত করা।
  • pq-তে (0, ball[0], ball[1], "") ইনসার্ট করা।
  • আকার n x m এর একটি 2D visited অ্যারে সংজ্ঞায়িত করা।
  • pq খালি না হওয়া পর্যন্ত:
    • curr := pq-এর শীর্ষ উপাদান
    • x := curr.x, y := curr.y, dist := curr.dist, d := curr.d
    • যদি ok(x, y, hole[0], hole[1]) হয়, তবে d ফেরত দেবে।
    • visited[x][y] := true
    • pq থেকে উপাদানটি ডিলিট করা।
    • k = 0 থেকে 3 পর্যন্ত লুপ:
      • nx := x, ny := y
      • tempDist := 0
      • যখন nx+dir[k][0] এবং ny+dir[k][1] মেজের পরিসীমার মধ্যে থাকে এবং maze[nx+dir[k][0]][ny+dir[k][1]] == 0:
        • nx += dir[k][0], ny += dir[k][1]
        • tempDist++
        • যদি ok(nx, ny, hole[0], hole[1]) হয়, তবে লুপ থেকে বের হওয়া।
      • যদি visited[nx][ny] == 0 হয়, তবে নতুন Data(dist + tempDist, nx, ny, d + dirst[k]) pq-তে ইনসার্ট করা।
  • "impossible" ফেরত দেবে।

প্রোগ্রাম উদাহরণ

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

int dir[4][2] = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};
char dirst[4] = {'d', 'l', 'r', 'u'};

class Solution {
public:
    struct Data {
        int dist;
        string d;
        int x, y;
        Data(int a, int b, int c, string s) {
            d = s;
            dist = a;
            x = b;
            y = c;
        }
    };
    struct Comparator {
        bool operator()(Data a, Data b) {
            return a.dist != b.dist ? !(a.dist < b.dist) : !(a.d < b.d);
        }
    };
    bool ok(int x1, int y1, int x2, int y2) { return x1 == x2 && y1 == y2; }
    string findShortestWay(vector>& maze, vector& ball, vector& hole) {
        int n = maze.size();
        int m = n ? maze[0].size() : 0;
        priority_queue, Comparator> pq;
        pq.push(Data(0, ball[0], ball[1], ""));
        vector> visited(n, vector(m));
        while (!pq.empty()) {
            Data curr = pq.top();
            int x = curr.x;
            int y = curr.y;
            int dist = curr.dist;
            string d = curr.d;
            if (ok(x, y, hole[0], hole[1])) {
                return d;
            }
            visited[x][y] = true;
            pq.pop();
            for (int k = 0; k < 4; k++) {
                int nx = x;
                int ny = y;
                int tempDist = 0;
                while (nx + dir[k][0] < n && nx + dir[k][0] >= 0 && ny + dir[k][1] < m && ny + dir[k][1] >= 0 && !maze[nx + dir[k][0]][ny + dir[k][1]]) {
                    nx += dir[k][0];
                    ny += dir[k][1];
                    tempDist++;
                    if (ok(nx, ny, hole[0], hole[1]))
                        break;
                }
                if (!visited[nx][ny]) {
                    pq.push(Data(dist + tempDist, nx, ny, d + dirst[k]));
                }
            }
        }
        return "impossible";
    }
};

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

ইনপুট

vector> v = {{0, 0, 0, 0, 0}, {1, 1, 0, 0, 1}, {0, 0, 0, 0, 0}, {0, 1, 0, 0, 1}, {0, 1, 0, 0, 0}}; vector v1 = {4, 3}, v2 = {0, 1};

আউটপুট

lul