leetcode

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

0980.cpp (1475B)

      1 class Solution {
      2     vector<pair<int, int>> offset = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
      3     int m, n;
      4 
      5     bool valid(int x, int y) { return x >= 0 && x < m && y >= 0 && y < n; }
      6 
      7     int find(vector<vector<int>> &grid, int x, int y, int obs) {
      8         stack<pair<int, int>> st;
      9         st.push({x, y});
     10 
     11         int count = 0, goal = m * n - obs - 1, crnt = 0;
     12         while (!st.empty()) {
     13             auto p = st.top();
     14 
     15             if (grid[p.first][p.second] == 3) {
     16                 st.pop();
     17                 grid[p.first][p.second] = 0;
     18                 crnt--;
     19                 continue;
     20             }
     21 
     22             grid[p.first][p.second] = 3;
     23             crnt++;
     24             for (auto &o : offset) {
     25                 int x = p.first + o.first;
     26                 int y = p.second + o.second;
     27                 if (!valid(x, y) || grid[x][y] == 3 || grid[x][y] == -1) continue;
     28                 if (grid[x][y] == 2)
     29                     count += crnt == goal;
     30                 else
     31                     st.push({x, y});
     32             }
     33         }
     34         return count;
     35     }
     36 
     37   public:
     38     int uniquePathsIII(vector<vector<int>> &grid) {
     39         m = grid.size(), n = grid[0].size();
     40 
     41         int x, y, count = 0;
     42         for (int i = 0; i < m; i++)
     43             for (int j = 0; j < n; j++)
     44                 if (grid[i][j] == 1)
     45                     x = i, y = j;
     46                 else if (grid[i][j] == -1)
     47                     count++;
     48 
     49         return find(grid, x, y, count);
     50     }
     51 };