เส้นทางสั้นที่สุดใน Binary Matrix (Shortest Path in Binary Matrix) ใน C++

โจทย์: กำหนด grid ขนาด N x N แต่ละเซลล์เป็น 0 (ว่าง) หรือ 1 (บล็อก) ต้องหา ความยาวเส้นทางสั้นที่สุด จากมุมซ้ายบน (0,0) ไปมุมขวาล่าง (N-1,N-1) ที่เดินได้เฉพาะเซลล์ 0 และเคลื่อนที่ได้ 8 ทิศทาง (แนวนอน แนวตั้ง ทแยงมุม) หากไม่มีเส้นทาง คืน -1

ตัวอย่าง

เส้นทางสั้นที่สุดมีความยาว 4

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

1. กำหนดอาร์เรย์ทิศทาง 8 ทิศ: d[8][2] = {{1,1},{1,-1},{-1,1},{1,0},{0,1},{-1,-1},{0,-1},{-1,0}}
2. ใช้ queue เก็บ point (x, y, distance)
3. เริ่มจาก (0,0) ถ้าเป็น 0: push เข้า queue, ทำเครื่องหมาย visited (ตั้งค่าเป็น 1)
4. BFS: pop หน้าคิว, ถ้าถึง (n-1,n-1) คืน distance
5. ลอง 8 ทิศทาง: ถ้าในขอบเขตและเป็น 0 -> mark visited, push เข้าคู่คิวพร้อม distance+1
6. จบลูปไม่เจอ: คืน -1

ตัวอย่างโค้ดเต็ม

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

int d[8][2] = {{1,1},{1,-1},{-1,1},{1,0},{0,1},{-1,-1},{0,-1},{-1,0}};

struct point {
    int x, y, c;
    point(int a, int b, int z) { x = a; y = b; c = z; }
};

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        queue<point> q;
        int n = grid.size();
        
        if(!grid[0][0]) {
            q.push(point(0, 0, 1));
            grid[0][0] = 1; // mark visited
        }
        
        while(!q.empty()) {
            point curr = q.front(); q.pop();
            int x = curr.x, y = curr.y, c = curr.c;
            
            if(x == n-1 && y == n-1) return c;
            
            c++;
            for(int i = 0; i < 8; i++) {
                int X = x + d[i][0];
                int Y = y + d[i][1];
                if(X >= 0 && X < n && Y >= 0 && Y < n && !grid[X][Y]) {
                    grid[X][Y] = 1;
                    q.push(point(X, Y, c));
                }
            }
        }
        return -1;
    }
};

int main() {
    vector<vector<int>> v = {{0,0,0},{1,1,0},{1,1,0}};
    Solution ob;
    cout << (ob.shortestPathBinaryMatrix(v));
}

Input

[[0,0,0],[1,1,0],[1,1,0]]

Output

4