aboutsummaryrefslogtreecommitdiff
path: root/unique_paths3.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'unique_paths3.cpp')
-rw-r--r--unique_paths3.cpp38
1 files changed, 0 insertions, 38 deletions
diff --git a/unique_paths3.cpp b/unique_paths3.cpp
deleted file mode 100644
index 37876fa..0000000
--- a/unique_paths3.cpp
+++ /dev/null
@@ -1,38 +0,0 @@
-#include "leetcode.h"
-
-class Solution {
-public:
- int uniquePathsIII(vvd & 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 & 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 grid = {{1, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 2, -1}};
- cout << obj.uniquePathsIII(grid); // expect: 2
-}