leetcode

Solution to some Leetcode problems written in C++

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

0980.cpp (1475B)

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