Untitled

#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    int minimumObstacles(vector<vector<int>>& grid) {
        int n = grid.size();        // Số hàng
        int m = grid[0].size();     // Số cột

        // Mảng visit lưu số lượng chướng ngại vật tối thiểu để đến (i, j)
        vector<vector<int>> visit(n, vector<int>(m, INT_MAX));
        visit[0][0] = 0;

        // Hướng di chuyển
        int dx[4] = {-1, 0, 1, 0};
        int dy[4] = {0, 1, 0, -1};

        // Min-heap lưu {số chướng ngại vật đã vượt qua, {x, y}}
        priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> pq;
        pq.push({0, {0, 0}});

        while (!pq.empty()) {
            auto [curr_obstacles, pos] = pq.top();
            pq.pop();
            int tx = pos.first, ty = pos.second;

            for (int k = 0; k < 4; k++) {
                int nx = tx + dx[k];
                int ny = ty + dy[k];
                if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
                    int new_obstacles = curr_obstacles + (grid[nx][ny] == 1 ? 1 : 0);
                    if (new_obstacles < visit[nx][ny]) {
                        visit[nx][ny] = new_obstacles;
                        pq.push({new_obstacles, {nx, ny}});
                    }
                }
            }
        }

        return visit[n - 1][m - 1] == INT_MAX ? -1 : visit[n - 1][m - 1];
    }
};