Kiểm tra đường đi giữa hai ô trong ma trận C++

Cho ma trận vuông giá trị 0,1,2,3:

• 0: Tường chặn
• 1: Điểm xuất phát (Source)
• 2: Đích đến (Destination)
• 3: Ô trống (có thể đi)

Chỉ di chuyển 4 hướng (trên/dưới/trái/phải). Kiểm tra có đường đi từ 1 đến 2 không.

Giải pháp: BFS trên đồ thị

• Chuyển ma trận thành đồ thị: mỗi ô ≠ 0 là một đỉnh.
• Nối cạnh giữa các ô liền kề hợp lệ.
• Chạy BFS từ source đến destination.

Chương trình C++

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

class Graph {
    int V;
    vector<vector<int>> adj;
public:
    Graph(int v) : V(v), adj(v) {}
    void addEdge(int u, int v) { adj[u].push_back(v); }
    bool bfs(int src, int dest) {
        if (src == dest) return true;
        vector<bool> vis(V, false);
        queue<int> q;
        q.push(src); vis[src] = true;
        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 isValid(int i, int j, int n, vector<vector<int>>& mat) {
    return i>=0 && i=0 && j
Kết quả
Khong co duong di