leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

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]); 4 5 vector<vector<int>> d(n, vector(m, INT_MAX / 2)); 6 deque<pair<int, int>> dq = {{0, 0}}; 7 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; }; 10 11 for (d[0][0] = 0; !dq.empty();) { 12 const auto [a, b] = dq.front(); 13 dq.pop_front(); 14 15 for (int k = 0; k < 4; k++) { 16 const int x = a + offset[k + 1]; 17 const int y = b + offset[k]; 18 19 if (!valid(x, y) || d[x][y] != INT_MAX / 2) continue; 20 if (d[a][b] + grid[x][y] >= d[x][y]) continue; 21 22 d[x][y] = d[a][b] + grid[x][y]; 23 24 if (grid[x][y] == 1) 25 dq.emplace_back(x, y); 26 else 27 dq.emplace_front(x, y); 28 } 29 } 30 31 return d[n - 1][m - 1]; 32 } 33 };