leetcode

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 };