Untitled
unknown
plain_text
5 months ago
1.5 kB
4
Indexable
#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]; } };
Editor is loading...
Leave a Comment