The Maze III ใน C++

สมมติว่ามีเขาวงกตที่มีพื้นที่ว่างและกำแพง และมีลูกบอลอยู่ในเขาวงกต ลูกบอลสามารถเคลื่อนที่ผ่านพื้นที่ว่างได้โดยการกลิ้งขึ้น (u) ลง (d) ซ้าย (l) หรือขวา (r) แต่จะกลิ้งต่อไปจนกว่าจะชนกำแพง เมื่อลูกบอลหยุด มันสามารถเลือกทิศทางถัดไปได้ มีรูในเขาวงกตด้วย ลูกบอลจะตกเข้าไปในรูหากมันกลิ้งผ่านรู

ดังนั้น หากเรามีตำแหน่งลูกบอล ตำแหน่งรู และเขาวงกต เราต้องหาว่าลูกบอลจะตกเข้าไปในรูได้อย่างไรด้วยการเคลื่อนที่ระยะทางสั้นที่สุด ระยะทางถูกนิยามโดยจำนวนพื้นที่ว่างที่ลูกบอลเดินทางจากจุดเริ่มต้น (ไม่นับ) ถึงรู (นับรวม)

คืนค่าทิศทางการเคลื่อนที่โดยใช้ 'u', 'd', 'l', 'r' เนื่องจากอาจมีหลายเส้นทางสั้นที่สุด ผลลัพธ์ควรเป็นเส้นทางที่เล็กที่สุดในลำดับเลขอักษร (lexicographically smallest) หากลูกบอลไม่สามารถไปถึงรูได้ ให้แสดง "impossible"

เขาวงกตถูกแทนด้วยเมทริกซ์ไบนารี 1 หมายถึงกำแพง 0 หมายถึงพื้นที่ว่าง ตำแหน่งลูกบอลและรูถูกแทนด้วยดัชนีแถวและคอลัมน์

เช่น ถ้าอินพุตเป็นรูปภาพดังนี้:

ผลลัพธ์จะเป็น 'lul' คือ เคลื่อนที่ซ้าย แล้วขึ้น แล้วซ้าย อีกผลลัพธ์หนึ่งอาจเป็น 'ul' คือ ขึ้นแล้วซ้าย ทั้งคู่มีความยาว 6 แต่ 'ul' ไม่ได้เล็กกว่า 'lul' ในลำดับเลขอักษร

ในการแก้ปัญหานี้ เราจะทำตามขั้นตอนต่อไปนี้:

• กำหนดโครงสร้างข้อมูล Data ที่มี distance, string d, และพิกัด x,y
• กำหนดอาร์เรย์ dir ขนาด 4x2 = {{1,0},{0,-1},{0,1},{-1,0}}
• กำหนดอาร์เรย์ dirst ขนาด 4 = {'d','l','r','u'}
• กำหนดฟังก์ชัน ok() รับ x1,y1,x2,y2 คืนค่า true ถ้า x1==x2 และ y1==y2
• จาก main method: n = จำนวนแถว, m = จำนวนคอลัมน์, สร้าง priority queue pq, ใส่ Data(0, ball[0], ball[1], "")
• สร้างอาร์เรย์ visited 2 มิติ ขนาด n x m
• while pq ไม่ว่าง: ดึงข้อมูลปัจจุบัน ตรวจสอบถึงรูแล้วคืนค่าทิศทาง, mark visited, ลอง 4 ทิศทาง กลิ้งจนชนกำแพงหรือถึงรู อัพเดทระยะทางและทิศทาง ใส่ pq ใหม่ถ้ายังไม่ visited
• คืนค่า "impossible" ถ้าไม่พบทาง

ตัวอย่าง

ลองดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:

#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) {
            d = s;
            dist = a;
            x = b;
            y = c;
        }
    };
    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";
    }
};
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));
}

อินพุต

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

เอาต์พุต

lul