Unique Paths III
You are given an m x n integer array grid where grid[i][j] could be:
1representing the starting square. There is exactly one starting square.2representing the ending square. There is exactly one ending square.0representing empty squares we can walk over.-1representing obstacles that we cannot walk over.
Return the number of 4-directional walks from the starting square to the ending square, where the walk visits every non-obstacle square exactly once.
Example 1
1 0 0 0 0 0 0 0 0 0 2 -1
Input
grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]Output
2There are exactly two valid paths that start at the starting square, end at the ending square, and walk over every non-obstacle square exactly once.
Example 2
1 0 0 0 0 0 0 0 0 0 0 2
Input
grid = [[1,0,0,0],[0,0,0,0],[0,0,0,2]]Output
4There are exactly four valid paths that start at the starting square, end at the ending square, and walk over every non-obstacle square exactly once.
Constraints
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 20
- 1 <= m * n <= 20
- -1 <= grid[i][j] <= 2
- There is exactly one starting cell and one ending cell.