Giải bài toán Mê cung (The Maze) trong C++

Giả sử có một quả bóng trong một mê cung bao gồm các ô trống và tường. Quả bóng có thể di chuyển qua các đường trống bằng cách lăn theo bất kỳ hướng nào (lên, xuống, trái, phải), nhưng nó sẽ không dừng lại cho đến khi va vào tường. Khi dừng lại, nó có thể chọn hướng tiếp theo.

Cho vị trí bắt đầu của quả bóng, đích đến và mê cung, ta phải kiểm tra xem quả bóng có thể dừng tại đích hay không. Mê cung được biểu diễn bằng mảng 2D: 1 đại diện cho tường, 0 đại diện cho ô trống. Các đường viền của mê cung đều là tường. Vị trí bắt đầu và đích được biểu diễn bằng chỉ số hàng và cột.

Ví dụ, với mê cung sau (mảng 2D):

Vị trí bắt đầu là (0, 4), đích là (4, 4). Kết quả trả về true. Một đường đi khả thi: trái → xuống → phải.

Giải thuật

Sử dụng BFS (tìm kiếm theo chiều rộng) để mô phỏng việc quả bóng lăn. Từ mỗi vị trí dừng, thử lăn theo 4 hướng cho đến khi gặp tường, đánh dấu vị trí dừng mới và tiếp tục tìm kiếm.

Cài đặt 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;

            // Lăn xuống
            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});
            }

            // Lăn lên
            i = x;
            while (i - 1 >= 0 && !grid[i - 1][y])
                i--;
            if (!visited.count({i, y})) {
                visited.insert({i, y});
                q.push({i, y});
            }

            // Lăn phải
            i = y;
            while (i + 1 < m && !grid[x][i + 1])
                i++;
            if (!visited.count({x, i})) {
                visited.insert({x, i});
                q.push({x, i});
            }

            // Lăn trá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;
}

Đầu vào

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

Đầu ra

1