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

}

############

class Solution {
    private int m;
    private int n;
    private int cnt;
    private int[][] grid;
    private boolean[][] vis;

    public int uniquePathsIII(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        this.grid = grid;
        int x = 0, y = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) {
                    ++cnt;
                } else if (grid[i][j] == 1) {
                    x = i;
                    y = j;
                }
            }
        }
        vis = new boolean[m][n];
        vis[x][y] = true;
        return dfs(x, y, 0);
    }

    private int dfs(int i, int j, int k) {
        if (grid[i][j] == 2) {
            return k == cnt + 1 ? 1 : 0;
        }
        int ans = 0;
        int[] dirs = {-1, 0, 1, 0, -1};
        for (int h = 0; h < 4; ++h) {
            int x = i + dirs[h], y = j + dirs[h + 1];
            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] != -1) {
                vis[x][y] = true;
                ans += dfs(x, y, k + 1);
                vis[x][y] = false;
            }
        }
        return ans;
    }
}

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

'''
>>> ( (i,j) for i in range(3) for j in range(3) if i == j )
<generator object <genexpr> at 0x104da5150>
>>> list( (i,j) for i in range(3) for j in range(3) if i == j )
[(0, 0), (1, 1), (2, 2)]
>>> next( (i,j) for i in range(3) for j in range(3) if i == j )
(0, 0)

basically next() is same as list()[0]
'''

class Solution: # dfs
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        def dfs(i, j, k):
            if grid[i][j] == 2:
                return int(k == cnt + 1)
            ans = 0
            for a, b in pairwise(dirs):
                x, y = i + a, j + b
                if 0 <= x < m and 0 <= y < n and (x, y) not in vis and grid[x][y] != -1:
                    vis.add((x, y))
                    ans += dfs(x, y, k + 1)
                    vis.remove((x, y))
            return ans

        m, n = len(grid), len(grid[0])
        start = next((i, j) for i in range(m) for j in range(n) if grid[i][j] == 1)
        dirs = (-1, 0, 1, 0, -1)
        cnt = sum(grid[i][j] == 0 for i in range(m) for j in range(n))
        vis = {start} # start here is a tuple (i,j)
        return dfs(*start, 0)

########

'''
>>> visited = set([(1,1),(2,2)])
>>> visited
{(1, 1), (2, 2)}
>>>
>>> visited | {(3,3), (4,4)}
{(4, 4), (1, 1), (3, 3), (2, 2)}
'''

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

class Solution: # bfs
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        available = 0
        sx = sy = ex = ey = 0 # start x/y, end x/y
        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)]))]) # x, y, count, visited
        
        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

func uniquePathsIII(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	cnt := 0
	vis := make([][]bool, m)
	x, y := 0, 0
	for i, row := range grid {
		vis[i] = make([]bool, n)
		for j, v := range row {
			if v == 0 {
				cnt++
			} else if v == 1 {
				x, y = i, j
			}
		}
	}
	dirs := [5]int{-1, 0, 1, 0, -1}
	var dfs func(i, j, k int) int
	dfs = func(i, j, k int) int {
		if grid[i][j] == 2 {
			if k == cnt+1 {
				return 1
			}
			return 0
		}
		ans := 0
		for h := 0; h < 4; h++ {
			x, y := i+dirs[h], j+dirs[h+1]
			if x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] != -1 {
				vis[x][y] = true
				ans += dfs(x, y, k+1)
				vis[x][y] = false
			}
		}
		return ans
	}
	vis[x][y] = true
	return dfs(x, y, 0)
}

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