The Maze II - หาระยะทางสั้นที่สุดในเขาวงกตใน C++

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

ระยะทาง = จำนวนช่องว่างที่ลูกบอลผ่าน (ไม่นับตำแหน่งเริ่มต้น นับตำแหน่งสุดท้าย)

ตัวอย่าง

Maze 5×5:

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

Start: (0,4), Destination: (4,4)

Output: 12

เส้นทาง: ซ้าย → ล่าง → ซ้าย → ล่าง → ขวา → ล่าง → ขวา (1+1+3+1+2+2+2 = 12)

แนวทางการแก้ปัญหา (BFS + Sliding)

ใช้ BFS แต่แทนที่จะขยับทีละช่อง ให้ "เลื่อน" จนชนกำแพงในแต่ละทิศทาง
ใช้ array dist[n][m] เก็บระยะทางสั้นที่สุดไปแต่ละช่อง
Queue เก็บตำแหน่งที่ลูกบอลหยุดลง
จากแต่ละตำแหน่ง ลองเลื่อน 4 ทิศทาง อัปเดต dist ถ้าหาได้ระยะทางสั้นกว่า

การนำไปใช้ (Implementation)

#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;
        const int INF = INT_MAX;
        
        vector<vector<int>> dist(n, vector<int>(m, INF));
        queue<vector<int>> q;
        
        q.push(start);
        dist[start[0]][start[1]] = 0;
        
        int dirs[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
        
        while (!q.empty()) {
            auto curr = q.front(); q.pop();
            int x = curr[0], y = curr[1];
            int currDist = dist[x][y];
            
            if (x == destination[0] && y == destination[1]) continue;
            
            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 dist[destination[0]][destination[1]] == INF ? -1 : dist[destination[0]][destination[1]];
    }
};

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

อินพุต

Maze 5x5, Start (0,4), Destination (4,4)

เอาต์พุต

12