Khóa học C++ từ cơ bản đến nâng cao

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>

int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

bool isValid(int r, int c, int R, int C, const vector<vector<char>>& banDo, const vector<vector<bool>>& daTham) {
    if (r < 0 || r >= R || c < 0 || c >= C) {
        return false;
    }
    if (banDo[r][c] == '#' || daTham[r][c]) {
        return false;
    }
    return true;
}

vector<pair<int, int>> bfs(const vector<vector<char>>& banDo, pair<int, int> bd, pair<int, int> kt) {
    int R = banDo.size();
    int C = banDo[0].size();

    if (bd.first < 0 || bd.first >= R || bd.second < 0 || bd.second >= C ||
        kt.first < 0 || kt.first >= R || kt.second < 0 || kt.second >= C ||
        banDo[bd.first][bd.second] == '#' || banDo[kt.first][kt.second] == '#') {
        cerr << "Điểm bắt đầu hoặc kết thúc không hợp lệ!" << endl;
        return {};
    }

    vector<vector<bool>> daTham(R, vector<bool>(C, false));
    vector<vector<pair<int, int>>> cha(R, vector<pair<int, int>>(C, {-1, -1}));
    queue<pair<int, int>> hangDoi;

    hangDoi.push(bd);
    daTham[bd.first][bd.second] = true;

    while (!hangDoi.empty()) {
        pair<int, int> hienTai = hangDoi.front();
        hangDoi.pop();

        if (hienTai.first == kt.first && hienTai.second == kt.second) {
            vector<pair<int, int>> duong;
            pair<int, int> b = kt;
            while (b.first != -1 || b.second != -1) {
                duong.push_back(b);
                b = cha[b.first][b.second];
            }
            reverse(duong.begin(), duong.end());
            return duong;
        }

        for (int i = 0; i < 4; ++i) {
            int tR = hienTai.first + dr[i];
            int tC = hienTai.second + dc[i];

            if (isValid(tR, tC, R, C, banDo, daTham)) {
                daTham[tR][tC] = true;
                cha[tR][tC] = hienTai;
                hangDoi.push({tR, tC});
            }
        }
    }
    return {};
}

int main() {
    vector<vector<char>> banDo = {
        {'S', '.', '.', '.', '#', '.'},
        {'.', '#', '.', '#', '.', '.'},
        {'.', '#', '.', '.', '.', '.'},
        {'.', '.', '.', '#', '#', '.'},
        {'#', '.', '.', '.', '.', 'E'}
    };

    pair<int, int> bd = {0, 0};
    pair<int, int> kt = {4, 5};

    cout << "Tim duong di tu (" << bd.first << "," << bd.second << ") den (" << kt.first << "," << kt.second << ")" << endl;

    vector<pair<int, int>> duong = bfs(banDo, bd, kt);

    if (!duong.empty()) {
        cout << "Tim thay duong di ngan nhat:" << endl;
        for (size_t i = 0; i < duong.size(); ++i) {
            cout << "(" << duong[i].first << "," << duong[i].second << ")";
            if (i < duong.size() - 1) {
                cout << " -> ";
            }
        }
        cout << endl;
        cout << "Do dai duong di (so buoc): " << duong.size() - 1 << endl;
    } else {
        cout << "Khong tim thay duong di." << endl;
    }

    return 0;
}