The Maze II (Ngõ lối II) - Tìm đường đi ngắn nhất trong C++

Cho mê cung (ma trận 2D: 0 = đường trống, 1 = tường), vị trí bắt đầu và đích. Quả bóng lăn theo 4 hướng (lên/xuống/trái/phải) và chỉ dừng khi đâm vào tường. Tìm khoảng cách ngắn nhất (số ô trống đi qua, không tính ô bắt đầu, tính ô dừng) để bóng dừng tại đích. Trả về -1 nếu không thể.

Ví dụ

Mê cung 5x5, bắt đầu (0,4), đích (4,4) → kết quả 12.

Giải thuật (BFS + Đi thẳng đến tường)

• Dùng hàng đợi queue lưu vị trí dừng.
• Mảng dist lưu khoảng cách ngắn nhất đến mỗi ô.
• Từ ô hiện tại, thử lăn 4 hướng: đi thẳng cho đến khi gặp tường hoặc biên, tính khoảng cách lăn được.
• Nếu khoảng cách mới < dist[vị trí dừng] → cập nhật và đẩy vào hàng đợi.
• Khi đến đích, cập nhật kết quả tối thiểu.

Ví dụ triển khai

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

class Solution {
public:
    int shortestDistance(vector<vector<int>>& grid, vector<int>& start, vector<int>& destination) {
        int n = grid.size();
        int m = n ? grid[0].size() : 0;
        int ret = INT_MAX;
        vector<vector<int>> dist(n, vector<int>(m, INT_MAX));
        queue<vector<int>> q;
        q.push(start);
        dist[start[0]][start[1]] = 0;
        while (!q.empty()) {
            auto curr = q.front(); q.pop();
            int x = curr[0], y = curr[1];
            if (x == destination[0] && y == destination[1]) {
                ret = min(ret, dist[x][y]);
            }
            int currDist = dist[x][y];
            // 4 hướng: xuống, lên, trái, phải
            int dirs[4][2] = {{1,0},{-1,0},{0,-1},{0,1}};
            for (auto& d : dirs) {
                int nx = x, ny = y, steps = 0;
                while (nx + d[0] >= 0 && nx + d[0] < n && ny + d[1] >= 0 && ny + d[1] < m && grid[nx + d[0]][ny + d[1]] == 0) {
                    nx += d[0];
                    ny += d[1];
                    steps++;
                }
                if (currDist + steps < dist[nx][ny]) {
                    dist[nx][ny] = currDist + steps;
                    q.push({nx, ny});
                }
            }
        }
        return ret == INT_MAX ? -1 : ret;
    }
};

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.shortestDistance(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

12