1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
int minimumObstacles(vector<vector<int>> &grid) {
int m = grid.size(), n = grid[0].size(), ds[] = {1, 0, -1, 0, 1};
vector<vector<int>> dist(m, vector<int>(n, 0x3f3f3f3f));
dist[0][0] = 0;
deque<pair<int, int>> q;
q.emplace_front(0, 0);
while (!q.empty()) {
auto [x, y] = q.front(); q.pop_front();
for (int i = 0; i < 4; ++i) {
int nx = x + ds[i], ny = y + ds[i + 1];
if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
int w = grid[nx][ny];
if (dist[nx][ny] > dist[x][y] + w) {
dist[nx][ny] = dist[x][y] + w;
if (w == 0) q.emplace_front(nx, ny);
else q.emplace_back(nx, ny);
}
}
}
return dist[m - 1][n - 1];
}
};
|