C++-এ মেজ সমস্যা: বল দিয়ে পথ খুঁজে বের করা

মনে করুন একটি মেজে একটি বল আছে যেখানে খালি স্থান এবং দেওয়াল রয়েছে। বলটি যেকোনো দিকে (উপর, নিচ, বাম বা ডান) লুড়িয়ে খালি পথে যেতে পারে, কিন্তু এটি দেওয়াল ধাক্কা খাওয়া পর্যন্ত থামবে না। বলটি থামলে পরবর্তী দিকে যেতে পারে।

সমস্যা বিবরণ

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

উদাহরণ

যদি ইনপুট মেজটি নিচের ২D অ্যারেটির মতো হয়:

শুরুর অবস্থান (0, 4) এবং গন্তব্য অবস্থান (4, 4) হলে আউটপুট হবে true। একটি সম্ভাব্য পথ: বামে → নিচে → ডানে।

সমাধানের পদ্ধতি

এই সমস্যাটি সমাধান করার জন্য আমরা BFS (Breadth-First Search) অ্যালগরিদম ব্যবহার করব। ধাপগুলো নিচে দেওয়া হলো:

1. মেজের সাইজ নির্ধারণ করুন (n × m)।
2. একটি কিউ (queue) এবং একটি ভিজিটেড সেট (visited set) আরম্ভ করুন।
3. শুরুর পজিশন কিউতে পুশ করুন এবং ভিজিটেড সেটে যোগ করুন।
4. কিউ খালি না হওয়া পর্যন্ত লুপ চালান:
   • কিউ থেকে বর্তমান পজিশন পপ করুন।
   • যদি বর্তমান পজিশন গন্তব্যের সমান হয়, তবে true রিটার্ন করুন।
   • চার দিকেই (উপর, নিচ, বাম, ডান) বলটি কতদূর যেতে পারে তা খুঁজে বের করুন (দেওয়াল বা সীমানা পাওয়া পর্যন্ত)।
   • প্রতিটি দিকের শেষ পজিশন যদি আগে ভিজিট না করা থাকে, তবে সেটি কিউতে পুশ করুন এবং ভিজিটেড সেটে যোগ করুন।
5. লুপ শেষ হলে false রিটার্ন করুন।

C++ কোড উদাহরণ

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

class Solution {
public:
    bool hasPath(vector<vector<int>>& grid, vector<int>& start, vector<int>& destination) {
        int n = grid.size();
        int m = grid[0].size();
        queue<vector<int>> q;
        q.push(start);
        set<vector<int>> visited;
        visited.insert(start);
        
        while (!q.empty()) {
            vector<int> curr = q.front();
            q.pop();
            int x = curr[0];
            int y = curr[1];
            
            if (destination[0] == x && destination[1] == y)
                return true;
            
            // নিচের দিকে যাওয়া
            int i = x;
            while (i + 1 < n && !grid[i + 1][y])
                i++;
            if (!visited.count({i, y})) {
                visited.insert({i, y});
                q.push({i, y});
            }
            
            // উপরের দিকে যাওয়া
            i = x;
            while (i - 1 >= 0 && !grid[i - 1][y])
                i--;
            if (!visited.count({i, y})) {
                visited.insert({i, y});
                q.push({i, y});
            }
            
            // ডানের দিকে যাওয়া
            i = y;
            while (i + 1 < m && !grid[x][i + 1])
                i++;
            if (!visited.count({x, i})) {
                visited.insert({x, i});
                q.push({x, i});
            }
            
            // বামের দিকে যাওয়া
            i = y;
            while (i - 1 >= 0 && !grid[x][i - 1])
                i--;
            if (!visited.count({x, i})) {
                visited.insert({x, i});
                q.push({x, i});
            }
        }
        return false;
    }
};

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.hasPath(v, v1, v2));
    return 0;
}

ইনপুট

{{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}

আউটপুট

1