Bài toán mê cung III trong C++

Cho một mê cung có các ô trống và tường, một quả bóng trong mê cung. Bóng lăn theo 4 hướng (lên, xuống, trái, phải) và chỉ dừng khi va vào tường. Có một lỗ trong mê cung, bóng sẽ rơi vào nếu lăn qua lỗ đó.

Cho vị trí bóng, vị trí lỗ và mê cung, hãy tìm đường đi ngắn nhất để bóng rơi vào lỗ. Khoảng cách là số ô trống đi qua (không tính ô bắt đầu, tính ô lỗ). Trả về chuỗi hướng 'u', 'd', 'l', 'r'. Nếu có nhiều đường ngắn nhất, trả về nhỏ nhất theo thứ tự từ điển. Nếu không thể đến, trả về "impossible".

Mê cung: ma trận nhị phân, 1 = tường, 0 = ô trống.

Ví dụ:

Kết quả: 'lul' (trái, lên, trái). Đường 'ul' cũng độ dài 6 nhưng 'lul' nhỏ hơn theo từ điển.

Phương pháp giải

Sử dụng thuật toán Dijkstra với hàng đợi ưu tiên. Trạng thái: (khoảng cách, chuỗi hướng, tọa độ). Mở rộng 4 hướng, lăn cho đến khi chạm tường hoặc lỗ. Theo dõi ô đã thăm.

Ví dụ chương trình

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

int dir[4][2] = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};
char dirst[4] = {'d', 'l', 'r', 'u'};

class Solution {
public:
    struct Data {
        int dist;
        string d;
        int x, y;
        Data(int a, int b, int c, string s) : dist(a), x(b), y(c), d(s) {}
    };
    
    struct Comparator {
        bool operator()(Data a, Data b) {
            return a.dist != b.dist ? !(a.dist < b.dist) : !(a.d < b.d);
        }
    };
    
    bool ok(int x1, int y1, int x2, int y2) {
        return x1 == x2 && y1 == y2;
    }
    
    string findShortestWay(vector>& maze, vector& ball, vector& hole) {
        int n = maze.size();
        int m = n ? maze[0].size() : 0;
        priority_queue, Comparator> pq;
        pq.push(Data(0, ball[0], ball[1], ""));
        vector> visited(n, vector(m));
        
        while (!pq.empty()) {
            Data curr = pq.top();
            int x = curr.x, y = curr.y, dist = curr.dist;
            string d = curr.d;
            
            if (ok(x, y, hole[0], hole[1])) return d;
            visited[x][y] = true;
            pq.pop();
            
            for (int k = 0; k < 4; k++) {
                int nx = x, ny = y, tempDist = 0;
                while (nx + dir[k][0] < n && nx + dir[k][0] >= 0 && 
                       ny + dir[k][1] < m && ny + dir[k][1] >= 0 && 
                       !maze[nx + dir[k][0]][ny + dir[k][1]]) {
                    nx += dir[k][0];
                    ny += dir[k][1];
                    tempDist++;
                    if (ok(nx, ny, hole[0], hole[1])) break;
                }
                if (!visited[nx][ny]) {
                    pq.push(Data(dist + tempDist, nx, ny, d + dirst[k]));
                }
            }
        }
        return "impossible";
    }
};

int main() {
    Solution ob;
    vector> v = {
        {0,0,0,0,0},
        {1,1,0,0,1},
        {0,0,0,0,0},
        {0,1,0,0,1},
        {0,1,0,0,0}
    };
    vector v1 = {4, 3}, v2 = {0, 1};
    cout << ob.findShortestWay(v, v1, v2);
    return 0;
}

Đầu vào

maze 5x5, ball=(4,3), hole=(0,1)

Đầu ra

lul