time O(4^(n^2))
space O(n^2)
State Variables
currentPath""
Found Paths:
None yet
Start finding paths for the Rat in the 4x4 maze.
Pseudocode
Pseudocode
1function findPaths(maze, n):
2 paths = []
3 visited = empty nxn grid
4 function backtrack(r, c, currentPath):
5 if r == n-1 and c == n-1:
6 paths.push(currentPath)
7 return
8 visited[r][c] = true
9 for dir in ['D', 'L', 'R', 'U']:
10 nextR, nextC = move(r, c, dir)
11 if isSafe(maze, nextR, nextC, visited):
12 backtrack(nextR, nextC, currentPath + dir)
13 visited[r][c] = false
14 if maze[0][0] == 1:
15 backtrack(0, 0, '')
16 return paths