980.Unique Paths III
===
###### tags: `Hard`,`Array`,`Backtracking`,`Matrix`,`Bit Manipulation`
[980. Unique Paths III](https://leetcode.com/problems/unique-paths-iii/)
### 題目描述
You are given an `m x n` integer array `grid` where `grid[i][j]` could be:
* `1` representing the starting square. There is exactly one starting square.
* `2` representing the ending square. There is exactly one ending square.
* `0` representing empty squares we can walk over.
* `-1` representing obstacles that we cannot walk over.
Return *the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.*
### 範例
**Example 1:**
![](https://assets.leetcode.com/uploads/2021/08/02/lc-unique1.jpg)
```
Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: We have the following two paths:
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)
```
**Example 2:**
![](https://assets.leetcode.com/uploads/2021/08/02/lc-unique2.jpg)
```
Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
Output: 4
Explanation: We have the following four paths:
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)
```
**Example 3:**
![](https://assets.leetcode.com/uploads/2021/08/02/lc-unique3-.jpg)
```
Input: grid = [[0,1],[2,0]]
Output: 0
Explanation: There is no path that walks over every empty square exactly once.
Note that the starting and ending square can be anywhere in the grid.
```
**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.
### 解答
```python=
class Solution:
def uniquePathsIII(self, grid: List[List[int]]) -> int:
def valid(x,y):
if x>=0 and x<self.m and y>=0 and y<self.n:
return True
return False
def dfs( node,step):
x, y = node[0],node[1]
if grid[x][y] == -1:
return 0
elif grid[x][y] == 0 or grid[x][y] == 1:
for dx,dy in [ (-1,0), (1,0), (0,-1), (0,1)]:
if valid(x+dx, y+dy) and self.visit[x+dx][y+dy]==0:
self.visit[x+dx][y+dy] = step
dfs( (x+dx, y+dy), step+1)
self.visit[x+dx][y+dy] = 0
elif grid[x][y] == 2 and step == self.m*self.n - self.rock_cnt + 1:
self.ans += 1
'''for line in self.visit:
for item in line:
print(item, end=' ')
print('')
print('---')'''
self.m, self.n = len(grid), len(grid[0])
self.visit = [ [0]*self.n for _ in range(self.m) ]
self.ans = 0
self.rock_cnt = 0
for i in range(self.m):
for j in range(self.n):
if grid[i][j] == 1:
begin = (i,j)
self.visit[i][j] = 1
elif grid[i][j] == -1:
self.rock_cnt += 1
#print(begin)
dfs(begin, 2)
return self.ans
```
> [name=玉山]
#### Javascript
```javascript=
function uiquePathIII(grid) {
const start = [];
let empty = 0;
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[i].length; j++) {
if (grid[i][j] === 0) {
empty++;
} else if (grid[i][j] === 1) {
start.push(i, j);
}
}
}
grid[start[0]][start[1]] = -1;
return dfs(grid, start[0], start[1], empty);
}
// 遍歷所有可能的路徑,當遇到2時且剛好空格為0時,代表找到一條路徑
function dfs(grid, x, y, empty) {
const isInBounds = (x, y, xLength, yLength) => x < xLength && x >= 0 && y < yLength && y >= 0;
const neighbors = [
[x + 1, y],
[x - 1, y],
[x, y + 1],
[x, y - 1],
];
let total = 0;
for (const [nx, ny] of neighbors) {
if (!isInBounds(nx, ny, grid.length, grid[0].length)) continue;
if (grid[nx][ny] === -1) continue;
if (grid[nx][ny] === 2) {
if (empty === 0) total++;
continue;
}
grid[nx][ny] = -1;
total += dfs(grid, nx, ny, empty - 1);
grid[nx][ny] = 0;
}
return total;
}
```
> 暴力解超級慢,不知道是不是題目想要的,但暫時沒想到更好的做法。
> [name=Marsgoat][time=Feb 22, 2023]
### Reference
[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)