โปรแกรม C++ ตรวจสอบว่ามีเส้นทางระหว่างสองเซลล์ในเมทริกซ์หรือไม่

โปรแกรมตรวจสอบว่ามีเส้นทางจาก Source ไป Destination ในเมทริกซ์สี่เหลี่ยมจัตุรัสที่มีค่า 0,1,2,3:

• 0 = ผนังว่าง (Blank Wall)
• 1 = จุดเริ่มต้น (Source)
• 2 = จุดหมาย (Destination)
• 3 = เซลล์ว่าง (Blank Cell)

มี Source และ Destination เพียงจุดเดียว เดินได้ 4 ทิศทาง (ไม่ใช่ทแยง) ใช้ BFS บนกราฟที่สร้างจากเมทริกซ์

ตัวอย่างโค้ด

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

class use_graph {
    int W;
    list <int> *adj;
    public:
    use_graph(int W) { this->W = W; adj = new list<int>[W]; }
    void add_side(int source, int dest);
    bool search(int source, int dest);
};

void use_graph::add_side(int source, int dest) {
    adj[source].push_back(dest);
    adj[dest].push_back(source);
}

bool use_graph::search(int source, int dest) {
    if (source == dest) return true;
    bool *visited = new bool[W];
    for (int i = 0; i < W; i++) visited[i] = false;
    list<int> queue;
    visited[source] = true;
    queue.push_back(source);
    while (!queue.empty()) {
        source = queue.front(); queue.pop_front();
        for (auto i = adj[source].begin(); i != adj[source].end(); ++i) {
            if (*i == dest) return true;
            if (!visited[*i]) { visited[*i] = true; queue.push_back(*i); }
        }
    }
    return false;
}

bool is_okay(int i, int j, int M[][4]) {
    if ((i < 0 || i >= 4) || (j < 0 || j >= 4) || M[i][j] == 0) return false;
    return true;
}

bool find(int M[][4]) {
    int source, dest;
    int W = 4*4+2;
    use_graph g(W);
    int k = 1;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (M[i][j] != 0) {
                if (is_okay(i, j+1, M)) g.add_side(k, k+1);
                if (is_okay(i, j-1, M)) g.add_side(k, k-1);
                if (j < 3 && is_okay(i+1, j, M)) g.add_side(k, k+4);
                if (i > 0 && is_okay(i-1, j, M)) g.add_side(k, k-4);
            }
            if (M[i][j] == 1) source = k;
            if (M[i][j] == 2) dest = k;
            k++;
        }
    }
    return g.search(source, dest);
}

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

ผลลัพธ์

Not Possible