Formatted question description: https://leetcode.ca/all/980.html

980. Unique Paths III

Level

Hard

Description

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:

(0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(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:

(0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
(0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,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)
(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

Solution

First find the starting square and the ending square.

Then use backtrack to count the number of walks. During the walk, maintain each square’s state (visited, unvisited or blocked) the number of remaining squares.

If the ending square is reached, the walk is valid if and only if there is only one remaining square.

Finally, return the number of walks.

public class Unique_Paths_III {
    class Solution {
        private int height;
        private int width;
        private int result;
        private final int[][] direction = new int[][]{ {0, 1}, {0, -1}, {1, 0}, {-1, 0} };

        public int uniquePathsIII(int[][] grid) {
            height = grid.length;
            width = grid[0].length;
            int count = 0;
            int startX = -1, startY = -1;
            for (int i = 0; i < height; i++) {
                for (int j = 0; j < width; j++) {
                    if (grid[i][j] == 1) {
                        startX = i;
                        startY = j;
                    } else if (grid[i][j] == 0)
                        count++;
                }
            }
            boolean[][] isVistied = new boolean[height][width];
            isVistied[startX][startY] = true;
            dfs(startX, startY, grid, count, isVistied);
            return this.result;
        }

        private void dfs(int row, int col, int[][] grid, int count, boolean[][] isVistied) {
            if (count == -1 && grid[row][col] == 2) { // @note: -1 because final -1 for ending position-2
                this.result++;
            } else {
                int tx = 0, ty = 0;
                for (int d = 0; d < 4; d++) { // try all 4 directions
                    tx = row + direction[d][0];
                    ty = col + direction[d][1];
                    if (tx >= 0 && tx < height && ty >= 0 && ty < width && !isVistied[tx][ty] && grid[tx][ty] != -1) {
                        isVistied[tx][ty] = true;
                        dfs(tx, ty, grid, count - 1, isVistied);
                        isVistied[tx][ty] = false;
                    }
                }
            }
        }
    }


    class Solution_DP {
        private int height;
        private int width;
        private int[][] dp;
        private final int[][] direction = new int[][]{ {0, 1}, {0, -1}, {1, 0}, {-1, 0} };

        public int uniquePathsIII(int[][] grid) {
            this.height = grid.length;
            this.width = grid[0].length;
            this.dp = new int[height * width][1 << (height * width)];
            int startX = -1, startY = -1;
            int state = 0;
            for (int i = 0; i < height; i++) {
                for (int j = 0; j < width; j++) {
                    if (grid[i][j] == 0 || grid[i][j] == 2)
                        state |= (1 << (i * width) + j);
                    else if (grid[i][j] == 1) {
                        startX = i;
                        startY = j;
                    }
                }
            }
            return dfs(grid, startX, startY, state);
        }

        private int dfs(int[][] grid, int row, int col, int state) {
            if (dp[row * width + col][state] > 0) return dp[row * width + col][state];
            if (state == 0 && grid[row][col] == 2) return 1;
            int tx = 0, ty = 0;
            for (int d = 0; d < 4; d++) {
                tx = row + direction[d][0];
                ty = col + direction[d][1];
                if (tx >= 0 && tx < height && ty >= 0 && ty < width && grid[tx][ty] != -1) {
                    if ((state & (1 << (tx * width + ty))) == 0) continue;
                    dp[row * width + col][state] += dfs(grid, tx, ty, state ^ (1 << (tx * width + ty)));
                }
            }
            return dp[row * width + col][state];
        }
    }

}

// OJ: https://leetcode.com/problems/unique-paths-iii/
// Time: O(3^(MN))
// Space: O(MN) due to call stack
class Solution {
public:
    int uniquePathsIII(vector<vector<int>>& A) {
        int M = A.size(), N = A[0].size(), sx, sy, goal = 0, ans = 0, dirs[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
        function<void(int, int)> dfs = [&](int x, int y) {
            if (A[x][y] == 2) {
                ans += goal == 1;
                return;
            }
            A[x][y] = -1;
            --goal;
            for (auto &[dx, dy] : dirs) {
                int a = x + dx, b = y + dy;
                if (a < 0 || a >= M || b < 0 || b >= N || A[a][b] == -1) continue;
                dfs(a, b);
            }
            ++goal;
            A[x][y] = 0;
        };
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (A[i][j] != -1) ++goal;
                if (A[i][j] == 1) sx = i, sy = j;
            }
        }
        dfs(sx, sy);
        return ans;
    }
};

# 980. Unique Paths III
# https://leetcode.com/problems/unique-paths-iii/

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        available = 0
        sx = sy = ex = ey = 0
        res = 0
        
        for x in range(rows):
            for y in range(cols):
                if grid[x][y] != -1:
                    available += 1
                
                if grid[x][y] == 1:
                    sx, sy = x, y
                elif grid[x][y] == 2:
                    ex, ey = x, y
                    
        queue = deque([(sx, sy, 1, set([(sx, sy)]))])
        
        while queue:
            x, y, count, visited = queue.popleft()
            
            if x == ex and y == ey and count == available:
                res += 1
                continue
            
            for dx, dy in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
                if 0 <= dx < rows and 0 <= dy < cols and grid[dx][dy] != -1 and count + 1 <= available and (dx, dy) not in visited:
                    new_visited = visited | {(dx, dy)}
                    queue.append((dx, dy, count + 1, new_visited))
        
        return res

Java

class Solution {
    final int BLOCK = -1;
    final int UNVISITED = 0;
    final int VISITED = 1;
    int paths = 0;

    public int uniquePathsIII(int[][] grid) {
        int startRow = 0, startColumn = 0, endRow = 0, endColumn = 0;
        int rows = grid.length, columns = grid[0].length;
        int[][] states = new int[rows][columns];
        int squares = rows * columns;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (grid[i][j] == -1) {
                    squares--;
                    states[i][j] = BLOCK;
                } else if (grid[i][j] == 1) {
                    startRow = i;
                    startColumn = j;
                } else if (grid[i][j] == 2) {
                    endRow = i;
                    endColumn = j;
                }
            }
        }
        backtrack(grid, states, squares, startRow, startColumn, endRow, endColumn);
        return paths;
    }

    public void backtrack(int[][] grid, int[][] states, int squares, int startRow, int startColumn, int endRow, int endColumn) {
        if (startRow == endRow && startColumn == endColumn) {
            if (squares == 1)
                paths++;
        } else {
            int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
            int rows = grid.length, columns = grid[0].length;
            squares--;
            states[startRow][startColumn] = VISITED;
            for (int[] direction : directions) {
                int row = startRow + direction[0], column = startColumn + direction[1];
                if (row >= 0 && row < rows && column >= 0 && column < columns && states[row][column] == UNVISITED)
                    backtrack(grid, states, squares, row, column, endRow, endColumn);
            }
            squares++;
            states[startRow][startColumn] = UNVISITED;
        }
    }
}

// OJ: https://leetcode.com/problems/unique-paths-iii/
// Time: O(3^(MN))
// Space: O(MN) due to call stack
class Solution {
public:
    int uniquePathsIII(vector<vector<int>>& A) {
        int M = A.size(), N = A[0].size(), sx, sy, goal = 0, ans = 0, dirs[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
        function<void(int, int)> dfs = [&](int x, int y) {
            if (A[x][y] == 2) {
                ans += goal == 1;
                return;
            }
            A[x][y] = -1;
            --goal;
            for (auto &[dx, dy] : dirs) {
                int a = x + dx, b = y + dy;
                if (a < 0 || a >= M || b < 0 || b >= N || A[a][b] == -1) continue;
                dfs(a, b);
            }
            ++goal;
            A[x][y] = 0;
        };
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (A[i][j] != -1) ++goal;
                if (A[i][j] == 1) sx = i, sy = j;
            }
        }
        dfs(sx, sy);
        return ans;
    }
};

# 980. Unique Paths III
# https://leetcode.com/problems/unique-paths-iii/

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        available = 0
        sx = sy = ex = ey = 0
        res = 0
        
        for x in range(rows):
            for y in range(cols):
                if grid[x][y] != -1:
                    available += 1
                
                if grid[x][y] == 1:
                    sx, sy = x, y
                elif grid[x][y] == 2:
                    ex, ey = x, y
                    
        queue = deque([(sx, sy, 1, set([(sx, sy)]))])
        
        while queue:
            x, y, count, visited = queue.popleft()
            
            if x == ex and y == ey and count == available:
                res += 1
                continue
            
            for dx, dy in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
                if 0 <= dx < rows and 0 <= dy < cols and grid[dx][dy] != -1 and count + 1 <= available and (dx, dy) not in visited:
                    new_visited = visited | {(dx, dy)}
                    queue.append((dx, dy, count + 1, new_visited))
        
        return res

980 - Unique Paths III

980. Unique Paths III

Level

Description

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

980. Unique Paths III

Level

Description

Solution

All Problems

All Solutions