Example of Python algorithm for solving maze problem

This paper gives an example of Python's algorithm for solving the maze problem. To share for your reference, the details are as follows:

Question:

Enter n * m for a 2-dimensional array representing 1 maze
The number zero means obstacle and one means passable
Move to adjacent cells in 1 step

Ideas:

Depth-first traversal, reaching each point, recording the minimum number of steps from the starting point to each point

Initialization case:

[

1 1 0 1 1
1 0 1 1 1
1 0 1 0 0
1 0 1 1 1
1 1 1 0 1
1 1 1 1 1

]

1 Add a loop of -1 around the figure to prevent out of bounds during depth first traversal
2 I'm going to change all the obstacles to -1, and I'm going to change all the places I can walk to 0
3 Every time you walk through a point, if the current node value is 0, save the number of steps taken into the node
If the current node value is -1, it means the obstacle is not traversing it
If the number of steps it takes to get to the current node is less than the number stored in it, modify it

Modified figure:

[

-1 -1 -1 -1 -1 -1 -1
-1 0 0 -1 0 0 -1
-1 0 -1 0 0 0 -1
-1 0 -1 0 -1 -1 -1
-1 0 -1 0 0 0 -1
-1 0 0 0 -1 0 -1
-1 0 0 0 0 0 -1
-1 -1 -1 -1 -1 -1 -1

]

The minus 1 on the outside is what you're going through to prevent it from going out of bounds

By default the point from the top left is the entry and the point from the top right is the exit

Python code:

# -*- coding:utf-8 -*-
def init():
  global graph
  graph.append([-1,  -1, -1, -1, -1, -1,  -1])
  graph.append([-1,  0, 0, -1, 0, 0,  -1])
  graph.append([-1,  0, -1, 0, 0, 0,  -1])
  graph.append([-1,  0, -1, 0, -1, -1,  -1])
  graph.append([-1,  0, -1, 0, 0, 0,  -1])
  graph.append([-1,  0, 0, 0, -1, 0,  -1])
  graph.append([-1,  0, 0, 0, 0, 0,  -1])
  graph.append([-1,  -1, -1, -1, -1, -1,  -1])
# Depth-first traversal 
def deepFirstSearch( steps , x, y ):
  global graph
  current_step = steps + 1
  print(x, y, current_step )
  graph[x][y] = current_step
  next_step = current_step + 1
  '''
   Traverse around 4 A point :
     If the surrounding node is not -1  instructions   Is not an obstacle   On this basis: 
         There is a 0  It says it's not traversed   Let's change it to the number of steps in the current position plus 1
         Inside than the current next_step big   It's not the optimal solution   Just modify it 
         Inside ratio current next_step Indicate that the current is not the best solution, do not modify 
  '''
  if not(x-1== 1 and y==1) and graph[x-1][y] != -1 and ( graph[x-1][y]>next_step or graph[x-1][y] ==0 ) : # On the left 
    deepFirstSearch(current_step, x-1 , y )
  if not(x == 1 and y-1==1) and graph[x][y-1] != -1 and ( graph[x][y-1]>next_step or graph[x][y-1] ==0 ) : # on 
    deepFirstSearch(current_step, x , y-1 )
  if not(x == 1 and y+1==1) and graph[x][y+1] != -1 and ( graph[x][y+1]>next_step or graph[x][y+1]==0 ) : # Under the 
    deepFirstSearch(current_step, x , y+1 )
  if not(x+1== 1 and y==1) and graph[x+1][y] != -1 and ( graph[x+1][y]>next_step or graph[x+1][y]==0 ) : # right 
    deepFirstSearch(current_step, x+1 , y )
if __name__ == "__main__":
  graph = []
  init()
  deepFirstSearch(-1,1,1)
  print(graph[1][5])

Operation results:

[

(1, 1, 0)
(1, 2, 1)
(2, 1, 1)
(3, 1, 2)
(4, 1, 3)
(5, 1, 4)
(5, 2, 5)
(5, 3, 6)
(4, 3, 7)
(3, 3, 8)
(2, 3, 9)
(2, 4, 10)
(1, 4, 11)
(1, 5, 12)
(2, 5, 13)
(2, 5, 11)
(4, 4, 8)
(4, 5, 9)
(5, 5, 10)
(6, 5, 11)
(6, 4, 12)
(6, 3, 13)
(6, 2, 14)
(6, 1, 15)
(6, 3, 7)
(6, 2, 8)
(6, 1, 9)
(6, 4, 8)
(6, 5, 9)
(6, 2, 6)
(6, 1, 7)
(6, 1, 5)
12

]

PS: This site also has an infinite maze game, based on JS implementation, to provide you with reference 1:

Online maze game:
http://tools.ofstack.com/games/migong

For more information about Python, please refer to Python Data Structure and Algorithm Tutorial, Python Coding Skills Summary, Python Function Usage Skills Summary, Python String Manipulation Skills Summary and Python Introductory and Advanced Classic Tutorial.

I hope this article has been helpful in Python programming.