diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /unique_paths3.cpp | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'unique_paths3.cpp')
-rw-r--r-- | unique_paths3.cpp | 38 |
1 files changed, 38 insertions, 0 deletions
diff --git a/unique_paths3.cpp b/unique_paths3.cpp new file mode 100644 index 0000000..3e8eb86 --- /dev/null +++ b/unique_paths3.cpp @@ -0,0 +1,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 +} |