leetcodeSolution to some Leetcode problems written in C++ |
git clone git://git.dimitrijedobrota.com/leetcode.git |
Log | Files | Refs | README | LICENSE |
2290.cpp (1040B)
0 class Solution {
1 public:
2 int minimumObstacles(vector<vector<int>> &grid) const {
3 const int n = size(grid), m = size(grid[0]);
5 vector<vector<int>> d(n, vector(m, INT_MAX / 2));
6 deque<pair<int, int>> dq = {{0, 0}};
8 static const int offset[] = {-1, 0, 1, 0, -1};
9 const auto valid = [&](int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; };
11 for (d[0][0] = 0; !dq.empty();) {
12 const auto [a, b] = dq.front();
13 dq.pop_front();
15 for (int k = 0; k < 4; k++) {
16 const int x = a + offset[k + 1];
17 const int y = b + offset[k];
19 if (!valid(x, y) || d[x][y] != INT_MAX / 2) continue;
20 if (d[a][b] + grid[x][y] >= d[x][y]) continue;
22 d[x][y] = d[a][b] + grid[x][y];
24 if (grid[x][y] == 1)
25 dq.emplace_back(x, y);
26 else
27 dq.emplace_front(x, y);
28 }
29 }
31 return d[n - 1][m - 1];
32 }
33 };