# 980.Unique-Paths-III

## 980. Unique Paths III

## 题目地址

<https://leetcode.com/problems/unique-paths-iii/>

## 题目描述

```
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 <= grid.length * grid[0].length <= 20
```

## 代码

### Approach 1: Backtracking DFS

**Complexity Analysis**

* Time Complexity: O(3^N)
* Space Complexity: O(N)

```java
class Solution {

  int[] dr = new int[] {0, -1, 0, 1};
  int[] dc = new int[] {1, 0, -1, 0};
  int ans = 0;

  public int uniquePathsIII(int[][] grid) {
    int R = grid.length;
    int C = grid[0].length;

    int todo = 0;
    int sr = 0, sc = 0;
    int tr = 0, tc = 0;
    for (int r = 0; r < R; r++) {
      for (int c = 0; c < C; c++) {
        if (grid[r][c] != -1) {
          todo++;
        }

        if (grid[r][c] == 1) {
          sr = r;
          sc = c;
        } else if (grid[r][c] == 2) {
          tr = r;
          tc = c;
        }
      }
    }

    ans = 0;
    dfs(sr, sc, tr, tc, grid, todo);
    return ans;
  }

  public void dfs(int sr, int sc, int tr, int tc, int[][] grid, int todo) {
    todo--;
    if (todo < 0) return;
    if (sr == tr && sc == tc) {
      if (todo == 0) ans++;
      return;
    }

    int R = grid.length;
    int C = grid[0].length;
    grid[sr][sc] = 3;
    for (int k = 0; k < 4; k++) {
      int nr = sr + dr[k];
      int nc = sc + dc[k];
      if (nr >= 0 && nr < R && nc >= 0 && nc < C) {
        if (grid[nr][nc] == 0 || grid[nr][nc] == 2) {
          dfs(nr, nc, tr, tc, grid, todo);
        }
      }
    }
    grid[sr][sc] = 0;
  }
}
```

### Approach #2 DFS

* Time Complexity: O(3^N)
* Space Complexity: O(N)

```java
class Solution {
    int ans;
    int[][] grid;
    int R, C;
    int tr, tc, target;
    int[] dr = new int[]{0, -1, 0, 1};
    int[] dc = new int[]{1, 0, -1, 0};
    Integer[][][] memo;

    public int uniquePathsIII(int[][] grid) {
      this.grid = grid;
      R = grid.length;
      C = grid[0].length;
      target = 0;

      int sr = 0, sc = 0;
      for (int r = 0; r < R; ++r)
        for (int c = 0; c < C; ++c) {
          if (grid[r][c] % 2 == 0)
              target |= code(r, c);

          if (grid[r][c] == 1) {
              sr = r;
              sc = c;
          } else if (grid[r][c] == 2) {
              tr = r;
              tc = c;
          }
        }

      memo = new Integer[R][C][1 << R*C];
      return dp(sr, sc, target);
    }

    public int code(int r, int c) {
        return 1 << (r * C + c);
    }

    public Integer dp(int r, int c, int todo) {
      if (memo[r][c][todo] != null)
          return memo[r][c][todo];

      if (r == tr && c == tc) {
          return todo == 0 ? 1 : 0;
      }

      int ans = 0;
      for (int k = 0; k < 4; ++k) {
          int nr = r + dr[k];
          int nc = c + dc[k];
          if (0 <= nr && nr < R && 0 <= nc && nc < C) {
              if ((todo & code(nr, nc)) != 0)
                  ans += dp(nr, nc, todo ^ code(nr, nc));
          }
      }
      memo[r][c][todo] = ans;
      return ans;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wentao-shao.gitbook.io/leetcode/dynamic-programming/1.position/980.unique-paths-iii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.