aboutsummaryrefslogtreecommitdiff
path: root/unique_paths3.cpp
blob: 3e8eb86c589063475fc6af0d9ebfbaeddf48cc41 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include "leetcode.h"

class Solution {
public:
  int uniquePathsIII(vvd(int) & grid) {
    auto i1 = 0, j1 = 0, t_steps = 0;
    for (auto i = 0; i < grid.size(); ++i)
      for (auto j = 0; j < grid[0].size(); ++j) {
        if (grid[i][j] == 1)
          i1 = i, j1 = j;
        if (grid[i][j] != -1)
          ++t_steps;
      }
    return dfs(grid, i1, j1, 1, t_steps);
  }

private:
  int dfs(vvd(int) & grid, int i, int j, int step, int t_step) {
    if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() ||
        grid[i][j] == -1)
      return 0;
    if (grid[i][j] == 2)
      return step == t_step ? 1 : 0;
    grid[i][j] = -1;
    int paths = dfs(grid, i + 1, j, step + 1, t_step) +
                dfs(grid, i - 1, j, step + 1, t_step) +
                dfs(grid, i, j + 1, step + 1, t_step) +
                dfs(grid, i, j - 1, step + 1, t_step);
    grid[i][j] = 0;
    return paths;
  }
};

int main() {
  Solution obj;
  vvd(int) grid = {{1, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 2, -1}};
  cout << obj.uniquePathsIII(grid); // expect: 2
}