mediumBacktrackingPattern: Backtracking
Safe Grid Paths Solution
Problem Statement
Given a grid of size m x n, find all possible paths from the top-left cell to the bottom-right cell while avoiding blocked cells.
Examples
Example 1:
Input:[{"grid":[["1","0","1"],["1","1","0"],["0","0","0"]]}]
Output:[[["1","0","1"],["1","1","0"],["0","0","0"]]]
Explanation: There is only one possible path.
Example 2:
Input:[{"grid":[["1","0","0"],["0","0","1"],["0","0","0"]]}]
Output:[[["1","0","0"],["0","0","1"],["0","0","0"]]]
Explanation: There are multiple possible paths, but we only return one of them.
Constraints
- m and n are positive integers.
- The grid is a 2D array of size m x n.
- Blocked cells are denoted by '0' and empty cells by '1'.
- m and n are not too large (m < 10, n < 10)
- The input grid will not have any cycles in it that would lead to repeated paths.
Time: O(4^(m*n)) Space: O(m*n)
The optimized approach is to use a depth-first search (DFS) with backtracking to find all possible paths. This approach has a time complexity of O(4^(m*n)).
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def safe_grid_paths(grid): m, n = len(grid), len(grid[0]) directions = [[0, 1], [1, 0], [-1, 0], [0, -1]] visited = [[False]*n for _ in range(m)] res = [] def dfs(r, c, path): if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] == 0 or visited[r][c]: return path.append([r, c]) if r == m - 1 and c == n - 1: res.append(path) visited[r][c] = True for d in directions: dfs(r + d[0], c + d[1], path) path.pop() visited[r][c] = False dfs(0, 0, []) return res