leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1162.cpp (1106B)

      1 class Solution {
      2     int n, m;
      3 
      4     bool valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; }
      5 
      6   public:
      7     int maxDistance(vector<vector<int>> &grid) {
      8         n = grid.size(), m = grid[0].size();
      9         queue<pair<int, int>> q;
     10 
     11         for (int i = 0; i < n; i++) {
     12             for (int j = 0; j < m; j++) {
     13                 if (grid[i][j]) {
     14                     q.push({i, j});
     15                     grid[i][j] = 0;
     16                 } else
     17                     grid[i][j] = -1;
     18             }
     19         }
     20         if (q.empty() || q.size() == n * m) return -1;
     21 
     22         vector<int> offset_x{0, 0, 1, -1}, offset_y{1, -1, 0, 0};
     23 
     24         int res = 0;
     25         while (!q.empty()) {
     26             auto [a, b] = q.front();
     27             q.pop();
     28             res = max(res, grid[a][b]);
     29             for (int i = 0; i < 4; i++) {
     30                 int x = a + offset_x[i];
     31                 int y = b + offset_y[i];
     32                 if (!valid(x, y) || grid[x][y] >= 0) continue;
     33                 grid[x][y] = grid[a][b] + 1;
     34                 q.push({x, y});
     35             }
     36         }
     37 
     38         return res;
     39     }
     40 };