Đường đi ngắn nhất trong ma trận nhị phân (Shortest Path in Binary Matrix) trong C++

Cho ma trận vuông N x N, mỗi ô là 0 (trống) hoặc 1 (chặn). Đường đi rõ ràng từ góc trên trái đến góc dưới phải có độ dài k nếu: các ô liền kề liên thông 8 hướng, bắt đầu (0,0), kết thúc (N-1,N-1), tất cả ô trên đường là 0. Tìm độ dài đường đi ngắn nhất, trả về -1 nếu không có.

Ví dụ ma trận 3x3, đường đi độ dài 4.

Giải pháp BFS:

• Mảng 8 hướng di chuyển.

• Queue lưu điểm (x,y,độ dài).

• Nếu ô (0,0) là 0, đẩy vào queue, đánh dấu visited (gán 1).

• BFS: lấy điểm, nếu đến đích trả về độ dài. Duyệt 8 hướng, nếu hợp lệ và là 0 thì đánh dấu và đẩy vào queue.

• Hết queue trả về -1.

Ví dụ hoàn chỉnh

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