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)

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)

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;
    }
}