0

I need to find the shortest path in a maze of 0's and 1's of m x n (where 1 is a wall and 0 is an empty space) from [0][0] to [m-1][n-1] and the allowed moves are U, D, L and R. By path I mean the number of cells to cover, including the source and the destination.

For some purposes I need to do it recursively. I wrote a function that finds all the paths possible and their length. In a brute way it just looks around (U, D, L, R) and if the cell has not been visited yet and it is not a wall, it recursively visits it.

def find_path(maze, i = 0, j = 0, path = 1):
    m = len(maze)
    n = len(maze[0])
    if i == m - 1 and j == n - 1:
        print("Path to destination [m - 1][n - 1]: {0}".format(path))
    maze[i][j] = 1
    if 0 <= i < m and 0 <= j - 1 < n and maze[i][j - 1] == 0:
        find_path(maze, i, j - 1, path + 1)
    if 0 <= i < m and 0 <= j + 1 < n and maze[i][j + 1] == 0:
        find_path(maze, i, j + 1, path + 1)
    if 0 <= i - 1 < m and 0 <= j < n and maze[i - 1][j] == 0:
        find_path(maze, i - 1, j, path + 1)
    if 0 <= i + 1 < m and 0 <= j < n and maze[i + 1][j] == 0:
        find_path(maze, i + 1, j, path + 1)
    maze[i][j] = 0
    return path

My problem:

  1. I do not understand how to save the shortest path and pass it to all the function calls when I reach the destination. Somewhere in the function should be a line something like if path < shortest_path: shortest_path = path;

  2. I don't understand how to return the shortest path from the function. Should I return a tuple (path, shortest_path) or what?

alekscooper
  • 795
  • 1
  • 7
  • 19
  • 1
    I think you will find [this Q&A](https://stackoverflow.com/a/65512563/633183) to be helpful – Mulan Jan 30 '21 at 19:27
  • 2
    You expect the return `path` is the total `steps` (of the path-way), correct? You should try `BFS` - it's more straightforward. – Daniel Hao Jan 31 '21 at 00:17
  • @DanielHao I know. But for some reason I need to use exactly this method. – alekscooper Jan 31 '21 at 06:05
  • 1
    When you take a step, append to the path list. When you return from a recursive call without having reached the destination, that was the wrong path so pop the path list. But, as Daniel mentions, DFS doesn't guarantee the shortest path, so you effectively have to exhaust the entire search space. BFS is much more appropriate for this and because it doesn't risk crashing on large mazes, although you'd probably use a dict to store "came from" per step, then reconstruct the path by repeatedly keying into the dict back to the root. – ggorlen Feb 01 '21 at 21:48

0 Answers0