Python shortest distance while escaping a binary maze using backtracking

Need help with finding shortest distance in a binary maze, which is a list of lists matrix, where 0 is an empty cell and 1 is a wall. The maze has x,y starting coordinates that default to 0,0 and it's end point is always bottom right corner. Shortest distance always includes the starting point (i.e., if there are four steps needed from the starting point, shortest distance will be 5)

I need to be using backtracking algorithm. So far I could come up with a function that determines if there is an escaping path at all. It works well:

def is_solution(maze, x=0, y=0):        n = len(maze)      m = len(maze[0])        if x == n - 1 and y == m - 1:          return True            maze[x][y] = 1      result = False        for a, b in [(x - 1, y), (x, y - 1), (x + 1, y), (x, y + 1)]:          if 0 <= a < n and 0 <= b < m and maze[a][b] == 0:              result = result or is_solution(maze, a, b)                    maze[x][y] = 0      return result      maze = [        [0, 0, 1, 1],        [1, 0, 0, 0],        [1, 1, 1, 0]      ]    is_solution(maze)  

The above will result to True.

Now I am really struggling with finding the shortest distance. I think it should be relatively easy to update the code above so it showed distance if there is a path and inf if there isn't one. But I got stuck. In the example above shortest distance would be 6 (including the starting point) I also need to add code to be able to get a list of all shortest distances and coordinates of each step in a list of lists format like [[(0, 0), (0, 1), (1, 1), (1, 2), (1, 3), (2, 3)]] . In this case there is only one path, but if there were two of distance six, that list would include also the list of second shortest path as well.

Thank you.

https://stackoverflow.com/questions/66083287/python-shortest-distance-while-escaping-a-binary-maze-using-backtracking February 07, 2021 at 08:06AM