Think about depth-priority and width-priority searches in Python

Hello: grinning: This time, we will consider depth-first search and breadth-first search using a maze. The maze used this time: arrow_down:

input

Input is done on n lines.

--The first line is the start and finish points of the maze ――The second line is the vertical and horizontal length of the maze --Lines 3 to n are maze information

n-2 is the vertical length of the maze, and # is given where there is no space. ex.)

S G
3 5
# B E F G
S A C H #
# D # # #

output

The output is 3 lines. The first line is the distance between the start point and the goal point The second line is the number of searches The third line is the route from the start point to the goal point ex.)

Distance between start and finish points: 5
Number of searches: 10
Route: G<= F <= H <= C <= A <= S

Depth-first search

Code flow

1. Read the information to be entered
2. Add Start to various lists
3. Remove from stack
4. Goal judgment
5. Add adjacent points to the stack
6. Add to checked list and return to 3

Implementation

stack

# cording = utf-8
start, goal = input().split()  #Start point and goal point
height, width = map(int, input().split())  #Maze length and width
maze, stack, checked, route = [], [], [], {}
num_of_t = 0  #Number of searches
for i in range(height):
    x = input().split()
    maze.append(x) #maze
    if start in maze[i]:
        now_height, now_width = i, maze[i].index(start)
start_height, start_width = now_height, now_width #Save the coordinates of the starting point
stack += start
checked += start
route[maze[now_height][now_width]] = "Start"


def search(h, w, x = maze, y = stack, z = checked):
    if x[h][w] != "#" and x[h][w] not in z:
        y += x[h][w]
        z += x[h][w]


while stack[-1] != goal:
    stack.pop()
    if now_height < height-1:
        search(now_height+1, now_width)
    if now_width < width-1:
        search(now_height, now_width+1)
    if now_height > 0:
        search(now_height-1, now_width)
    if now_width > 0:
        search(now_height, now_width-1)
    num_of_t += 1
    for j in range(height):
        if stack[-1] in maze[j]:
            route[stack[-1]] = maze[now_height][now_width]
            now_height, now_width = j, maze[j].index(stack[-1])
print("Distance between start and finish points:" + str(abs(now_height - start_height) + abs(now_width - start_width)))
print("Number of searches:" + str(num_of_t))
print("root:", end = "")
while route[goal] != "Start":
    print(goal + " <= ", end="")
    goal = route[goal]
print(goal)

Output result

Distance between start and finish points: 5
Number of searches: 5
Route: G<= F <= E <= B <= A <= S

Breadth-first search

Code flow

Changed stack of depth-first search to queue

Implementation

queue

# cording = utf-8
start, goal = input().split() #Enter the start point and goal point
height, width = map(int, input().split()) #Vertical and horizontal length of the maze
maze, queue, checked, route = [], [], [], {}
num_of_t = 0 #Number of searches
for i in range(height):
    x = input().split()
    maze.append(x)  #maze
    if "A" in maze[i]:
        now_height, now_width = i, maze[i].index(start)
start_height, start_width = now_height, now_width #Save the coordinates of the starting point
queue += start
checked += start
route[maze[now_height][now_width]] = "Start"


def search(h, w, x = maze, y = queue, z = checked):
    if x[h][w] != "#" and x[h][w] not in z:
        y += x[h][w]
        z += x[h][w]


while queue[0] != goal:
    place = queue.pop(0)
    tmp = len(queue)
    if now_height < height-1:
        search(now_height+1, now_width)
    if now_width < width-1:
        search(now_height, now_width+1)
    if now_height > 0:
        search(now_height-1, now_width)
    if now_width > 0:
        search(now_height, now_width-1)
    num_of_t += 1
    if tmp < len(queue):
        for i in range(1, len(queue) - tmp+1):
            route[queue[-i]] = place
    for j in range(height):
        if queue[0] in maze[j]:
            now_height, now_width = j, maze[j].index(queue[0])
print("Distance between start and finish points:" + str(abs(now_height - start_height) + abs(now_width - start_width)))
print("Number of searches:" + str(num_of_t))
print("root:", end = "")
while route[goal] != "Start":
    print(goal + " <= ", end="")
    goal = route[goal]
print(goal)

Output result

Distance between start and finish points: 5
Number of searches: 8
Route: G<= F <= H <= C <= A <= S

Consideration

The knowledge about the algorithm has been deepened sufficiently. Some people may be able to write it shorter, but at the moment I am like this.