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: 2020-05-25_16h23_17.png

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.

Recommended Posts

Think about depth-priority and width-priority searches in Python
Think about architecture in python
About the difference between "==" and "is" in python
Think about building a Python 3 environment in a Mac environment
About __all__ in python
About python objects and classes
About Python variables and objects
About Python, len () and randint ()
About Python datetime and timezone
Stack and Queue in Python
About Python and regular expressions
Unittest and CI in Python
About "for _ in range ():" in python
About Python and os operations
Python # About reference and copy
About Python sort () and reverse ()
Difference between list () and [] in Python
About installing Pwntools and Python2 series
What beginners think about programming in 2016
Difference between == and is in python
Manipulate files and folders in Python
About python dict and sorted functions
Assignments and changes in Python objects
[Python] About Executor and Future classes
About Python, from and import, as
Check and move directories in Python
Ciphertext in Python: IND-CCA2 and RSA-OAEP
Hashing data in R and Python
I learned about processes in Python
Function synthesis and application in Python
Export and output files in Python
Reverse Hiragana and Katakana in Python2.7
Reading and writing text in Python
[GUI in Python] PyQt5-Menu and Toolbar-
Create and read messagepacks in Python
Think seriously about what language to use in programming education and programming education.
Overlapping regular expressions in Python and Java
Differences in authenticity between Python and JavaScript
Notes using cChardet and python3-chardet in Python 3.3.1.
Modules and packages in Python are "namespaces"
Avoid nested loops in PHP and Python
Differences between Ruby and Python in scope
AM modulation and demodulation in Python Part 2
difference between statements (statements) and expressions (expressions) in Python
Eigenvalues and eigenvectors: Linear algebra in Python <7>
[Python] Sweet Is it sweet? About suites and expressions in the official documentation
Implementation module "deque" in queue and Python
Line graphs and scale lines in python
Vulkan compute with Python with VkInline and think about GPU machine learning and more
Implement FIR filters in Python and C
Differences in syntax between Python and Java
Check and receive Serial port in Python (Port check)
Search and play YouTube videos in Python
Difference between append and + = in Python list
Difference between nonlocal and global in Python
Write O_SYNC file in C and Python
Dealing with "years and months" in Python
Read and write JSON files in Python
Easily graph data in shell and Python
Private methods and fields in python [encryption]
Find and check inverse matrix in Python