C++ প্রোগ্রাম: ম্যাট্রিক্সে দুটি সেলের মধ্যকে পথ আছে কিনা চেক করা

একটি স্কোয়ার ম্যাট্রিক্স দেওয়া থাকে যেখানে মানগুলো: 0=দেওয়াল, 1=সোর্স, 2=ডেস্টিনেশন, 3=খালি সেল। শুধু একটি সোর্স ও ডেস্টিনেশন থাকে। আপ-ডাউন-লেফ্ট-রাইট (ডায়াগোনাল নয়) মুভ করে সোর্স থেকে ডেস্টিনেশন যাওয়া যায় কিনা চেক করতে হবে।

অ্যালগরিদম (BFS)

1. ম্যাট্রিক্সকে গ্রাফে কনভার্ট করুন (প্রতিটি সেল = নোড, আডজেসেন্ট সেল = এজ)।
2. সোর্স থেকে BFS চালিয়ে ডেস্টিনেশন পাওয়া যায় কিনা চেক করুন।

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

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

class Graph {
    int V; list<int> *adj;
public:
    Graph(int V) : V(V) { adj = new list<int>[V]; }
    void addEdge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); }
    bool BFS(int src, int dest) {
        if (src == dest) return true;
        vector<bool> vis(V, false);
        queue<int> q;
        vis[src] = true; q.push(src);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                if (v == dest) return true;
                if (!vis[v]) { vis[v] = true; q.push(v); }
            }
        }
        return false;
    }
};

bool isSafe(int i, int j, int M[][4]) {
    return (i>=0 && i<4 && j>=0 && j<4 && M[i][j] != 0);
}

bool findPath(int M[][4]) {
    Graph g(4*4+2);
    int k = 1, src, dest;
    for (int i=0; i<4; i++) for (int j=0; j<4; j++) {
        if (M[i][j] != 0) {
            if (isSafe(i, j+1, M)) g.addEdge(k, k+1);
            if (isSafe(i, j-1, M)) g.addEdge(k, k-1);
            if (j<3 && isSafe(i+1, j, M)) g.addEdge(k, k+4);
            if (i>0 && isSafe(i-1, j, M)) g.addEdge(k, k-4);
        }
        if (M[i][j] == 1) src = k;
        if (M[i][j] == 2) dest = k;
        k++;
    }
    return g.BFS(src, dest);
}

int main() {
    int M[4][4] = {{0,3,0,1}, {3,0,3,3}, {2,3,0,3}, {0,0,3,0}};
    cout << (findPath(M) ? "Possible" : "Not Possible");
    return 0;
}

আউটপুট

Not Possible