diff options
Diffstat (limited to 'other/unique_paths3.cpp')
-rw-r--r-- | other/unique_paths3.cpp | 38 |
1 files changed, 0 insertions, 38 deletions
diff --git a/other/unique_paths3.cpp b/other/unique_paths3.cpp deleted file mode 100644 index 37876fa..0000000 --- a/other/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 -} |