# 980. Unique Paths III 不同路径 III

@TOC

## # 题目描述

On a 2-dimensional `grid`, there are 4 types of squares:

• 1 represents the starting square. There is exactly one starting square.
• 2 represents the ending square. There is exactly one ending square.
• 0 represents empty squares we can walk over.
• -1 represents 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:

``````Input: [[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:

``````Input: [[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:

``````Input: [[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.
``````

Note:

1. 1 <= grid.length * grid[0].length <= 20

## # 解题方法

### # 回溯法

c++代码如下：

``````class Solution {
public:
int uniquePathsIII(vector<vector<int>>& grid) {
const int M = grid.size();
const int N = grid[0].size();
int zerocount = 0;
int res = 0;
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (grid[i][j] == 0) {
++zerocount;
}
}
}
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (grid[i][j] == 1) {
dfs(grid, i, j, 0, zerocount, res);
}
}
}
return res;
}

void dfs(vector<vector<int>>& grid, int x, int y, int pathcount, int zerocount, int& res) {
if (grid[x][y] == 2 && pathcount == zerocount)
++res;
const int M = grid.size();
const int N = grid[0].size();
int pre = grid[x][y];
if (pre == 0)
++pathcount;
grid[x][y] = -1;
for (auto d : dirs) {
int nx = x + d.first;
int ny = y + d.second;
if (nx < 0 || nx >= M || ny < 0 || ny >= N || grid[nx][ny] == -1)
continue;
dfs(grid, nx, ny, pathcount, zerocount, res);
}
grid[x][y] = pre;
}
private:
vector<pair<int, int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
};
``````

## # 日期

2019 年 1 月 20 日 —— 这次周赛有点简单