An example of depth first traversal of python maze problem

1. Introduction to the Maze

Use python to solve the maze problem. The maze is a 2-dimensional list. This time, use depth first to solve the maze problem. Define the starting point and the end point. From one position to the next one position, you can only take one step up or down or left or right. From the starting point, how to find a path to the end point.

2. Depth-first traversal

Simple that our case is to say, choose a road casually, go straight, can't walk, and then go back and choose a new road again

# 1  For the wall, 0  For the road 
maze = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 1, 1, 0, 0, 0, 1, 1, 1],
    [1, 0, 1, 1, 1, 1, 0, 0, 1, 1],
    [1, 0, 1, 0, 0, 0, 0, 0, 1, 1],
    [1, 0, 1, 0, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 0, 1, 1, 1, 1, 1, 1],
    [1, 1, 1, 0, 0, 0, 0, 1, 1, 1],
    [1, 1, 1, 0, 0, 1, 0, 1, 1, 1],
    [1, 1, 1, 1, 1, 1, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
]

First, let's set a starting point and an ending point

start = (1, 1)
end = (8, 8)

Judging the current point, 0 means the road can go, and 1 means the wall can't go
Sitting standard description for the next 1 point of 1 point:

Go up: r-1, c Go down: r + 1, c Left: r, c-1 Go right: r, c + 1

Then one point of our maze has reached the point where we can't walk, which is a dead end, and it has to go back the same way

At this time, we have a concept, that is, stack, and the idea of stack is: first in, then out

How to understand it, you can give a small example, that is, the aunt in the canteen steams steamed buns every morning. He puts the steamer on one floor and one floor
When students come to eat steamed buns, they often take them from the top, the top is the last one, and the bottom is the first one, so it is called first in and then out

In fact, list is a stack. For example, we put an empty list, and then we use this list to directly append

If you fetch it with pop, you will get the last element of append

#  Define a list, and put it in the list is every 1 The coordinates of walking, [r, c]
#  No. 1 1 Step is the starting position, which is start
list01 = [start]

The road traveled is defined as 2

row, col = now
# python  Deconstruction in is also called unpacking  now Includes two locations, 1 A line, 1 Column 
maze[row][col] = 2
#  This representative is the point of walking, which is 2 Because you can't walk the road you have walked, except when you can't go back, but also to go back according to the original road you have walked.  

Core code:

if maze[row - 1][col] == 0:
    #  You can walk above 
    list01.append((row - 1, col))
    continue
elif maze[row][col + 1] == 0:
    #  You can walk on the right 
    list01.append((row, col + 1))
    continue
elif maze[row + 1][col] == 0:
    #  You can walk below 
    list01.append((row + 1, col))
    continue
elif maze[row][col - 1] == 0:
    #  You can walk on the left 
    list01.append((row, col - 1))
    continue

The final code, you can run 1 try:

maze = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 1, 1, 0, 0, 0, 1, 1, 1],
    [1, 0, 1, 1, 1, 1, 0, 0, 1, 1],
    [1, 0, 1, 0, 0, 0, 0, 0, 1, 1],
    [1, 0, 1, 0, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 0, 1, 1, 1, 1, 1, 1],
    [1, 1, 1, 0, 0, 0, 0, 1, 1, 1],
    [1, 1, 1, 0, 0, 1, 0, 1, 1, 1],
    [1, 1, 1, 1, 1, 1, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
]

start = (1, 1)
end = (8, 8)

#  Define a list, and put it in the list is every 1 The coordinates of walking, [r, c]
#  No. 1 1 Step is the starting position, which is start
list01 = [start]

#  Define the loop and let it go 
#  The last thing in the list is the following 1 Where you walk, there is something in the current list to continue walking 
while list01:
    #  What is the node you are currently walking to 1 Node, that is, the last one to go 1 Step, where is it 1 Step, go to the last of the list 1 A value is an index -1
    now = list01[-1]
    if now == end:  #  If the present now Equal to the end point we defined before end
        print(list01)
        print(" Come out ")
        break
    row, col = now
    # python  Deconstruction in is also called unpacking  now Includes two locations, 1 A line, 1 Column 
    maze[row][col] = 2
    #  This representative is the point of walking, which is 2 Because you can't walk the road, except when you can't go back, that is, you can't go back according to the original road. 

	# continue  End this cycle and judge walking from a new start 
    if maze[row - 1][col] == 0:
        #  You can walk above 
        list01.append((row - 1, col))
        continue
    elif maze[row][col + 1] == 0:
        #  You can walk on the right 
        list01.append((row, col + 1))
        continue
    elif maze[row + 1][col] == 0:
        #  You can walk below 
        list01.append((row + 1, col))
        continue
    elif maze[row][col - 1] == 0:
        #  You can walk on the left 
        list01.append((row, col - 1))
        continue
    else: #  If you can't get through, you can kill every one in a direct cycle 1 Step, readjust the route 
        list01.pop()

else:
    print(" This maze won't work ")

Summarize