Solve with Python [100 past questions that beginners and intermediates should solve] (028 --033 breadth-first search)

1. Purpose

Solve 100 past questions that beginners and intermediates should solve in Python. The goal is to turn light blue by the time you finish solving everything.

This article is "028 --033 breadth-first search".

2. Summary

dfsIf possiblebfsIs almost the same. The difference is that `deque ()` pops from `pop ()` `in` `DFS``` and popleft () in BFS```. Use ``.

3. Main story

028 --033 Breadth-first search

028. ALDS_11_C --Breadth-first search

image.png

Answer


from collections import deque

n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(n):
    i, num, *nodes = map(int, input().split()) # *Collect extra
    graph[i] = nodes #Directed graph
visited = [-1] * (n+1)

q = deque()
q.append(1)
visited[1] = 0

while q:
    node = q.popleft()

    for next in graph[node]:
        if visited[next] != -1:
            continue
        q.append(next)
        visited[next] = visited[node] + 1
        
for i, num in enumerate(visited[1:]):
    print(i+1, num)

This is a basic problem. If you make your own mold here, you will be able to solve other problems with just a little tweaking.

bfsIf you roughly show the flow of

  1. Use `visited` to create a list of search destinations to record.
  2. Prepare `deque ()` for the time being and enter the initial value
  3. Turn `while``` until deque () `` is empty
  4. Use `popleft ()` to retrieve the value first in first out
  5. Examine the ``` graph` `` from the retrieved values to find the destination
  6. Determine if the destination has been searched
  7. Update `append``` and `visited``` if not searching

is.


029. AtCoder Beginner Contest 007 C-Breadth-first search

image.png image.png image.png

Answer


from collections import deque

R, C = map(int, input().split())
sy, sx = map(int, input().split())
sy -= 1 #Fixed to 0 index
sx -= 1
gy, gx = map(int, input().split())
gy -= 1 #Fixed to 0 index
gx -= 1
grid = [list(input()) for _ in range(R)]
visited = [[-1] * C for _ in range(R)]
moves = [(1, 0), (0, 1), (-1, 0), (0, -1)]

q = deque()
q.append((sy, sx))
visited[sy][sx] = 0

while q:
    start_y, start_x = q.popleft()

    for dy, dx in moves:
        moved_y = start_y + dy
        moved_x = start_x + dx

        if grid[moved_y][moved_x] == '#':
            continue
        if visited[moved_y][moved_x] != -1:
            continue
        visited[moved_y][moved_x] = visited[start_y][start_x] + 1
        q.append((moved_y, moved_x))

print(visited[gy][gx])

This is typical of the typical. I will remember it for the time being.


030. JOI 2011 Qualifying 5-Cheese

image.png image.png

Answer

from collections import deque

def bfs(start_y, start_x, target_cheese, H, W, grid):

    visited = [[-1] * W for _ in range(H)]
    moves = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    q = deque()
    q.append((start_y, start_x))
    visited[start_y][start_x] = 0

    while q:
        y, x = q.popleft()
        for dy, dx in moves:
            moved_y = y + dy
            moved_x = x + dx

            if moved_y < 0 or H - 1 < moved_y or moved_x < 0 or W -1 < moved_x:
                continue
            if grid[moved_y][moved_x] == 'X':
                continue
            if visited[moved_y][moved_x] != -1:
                continue
            if grid[moved_y][moved_x] == target_cheese:
                visited[moved_y][moved_x] = visited[y][x] + 1
                return visited[moved_y][moved_x]
 
            visited[moved_y][moved_x] = visited[y][x] + 1
            q.append((moved_y, moved_x))
            

if __name__ == "__main__":
    H, W, N = map(int, input().split())
    grid = [list(input()) for _ in range(H)] #S starts at the nest, numbers are cheese hardness, X is obstacles,.Is a vacant lot
    #Mice eat cheese in numerical order
    #Consider BFS from each number to the next
    #Grasp the start and the position of each number first
    start_y, start_x = 0, 0
    cheese = [(0, 0) for _ in range(10)] #Initial value(0, 0)Keep
    count = 0 #Put the number of cheese in count
    for row in range(H):
        for col in range(W):
            if grid[row][col] == '.' or grid[row][col] == 'X':
                continue
            elif grid[row][col] == 'S':
                start_y, start_x = row, col
            else:
                grid[row][col] = int(grid[row][col]) #Change the contents of the grid to numbers
                cheese[int(grid[row][col])] = (row, col)
                count += 1
                
    # ------- [Explore all points] ----------
    target_cheese = 1
    time_count = 0
    while target_cheese <= count:
        time_count += bfs(start_y, start_x, target_cheese, H, W, grid)
        start_y, start_x = cheese[target_cheese]
        target_cheese += 1

    print(time_count)

The implementation is a little heavy. From the problem statement, the mouse eats cheese from the smallest number to the largest cheese in order, so it seems good to do `BFS``` from each number to the next number. So, set `BFS, which has a fixed start position and goal position, in the order of the cheese numbers. s1ofbfs12ofbfs23ofbfs``` ・・・と行っていき、合計of最短距離が答えとなります。


031. JOI 2012 Qualifying 5 --Illuminations

image.png image.png

Answer


#Add all 0's to the top, bottom, left, and right of the gird,
#Coordinate(0,0)Add up the number of 1s where each 0 point that can be reached from

from collections import deque

# ---------- [Count the number of buildings that are adjacent to places without buildings] --------------
def check_walls(y, x, grid, W, H, even_moves, add_moves):
    count = 0

    if y % 2 == 0:
        moves = even_moves
    else:
        moves = add_moves
    
    for dy, dx in moves:
        moved_y = y + dy
        moved_x = x + dx
        if moved_y < 0 or H + 1 < moved_y or moved_x < 0 or W + 1 < moved_x:
            continue
        if grid[moved_y][moved_x] == 1:
            count += 1
    
    return count

if __name__ == "__main__":
    # ---------- [Input receipt] --------------
    W, H = map(int, input().split())
    grid = []
    grid.append([0] * (W+2))
    for _ in range(H):
        temp = list(map(int, input().split()))
        temp = [0] + temp + [0]
        grid.append(temp)
    grid.append([0] * (W+2))
    visited = [[-1] * (W+2) for _ in range(H+2)]
    answer_count = 0
    # ---------- [Even numbers and odd numbers move in different directions] --------------
    even_moves = [(-1, -1), (-1, 0), (0, 1), (1, 0), (1, -1), (0, -1)] #Clockwise from top left
    add_moves = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (0, -1)] #Clockwise from top left
    # ---------- [Initial value setting] --------------
    q = deque()
    q.append((0, 0)) # (0, 0)Conduct BFS for places where there are no buildings that can be reached from
    count = check_walls(0, 0, grid, W, H, even_moves, add_moves) #Count the number of adjacent buildings
    visited[0][0] = count
    answer_count += count
    # ---------- [BFS start] --------------
    while q:
        y, x = q.popleft()

        if y % 2 == 0:
            moves = even_moves
        else:
            moves = add_moves
        
        for dy, dx in moves:
            moved_y = y + dy
            moved_x = x + dx
            if moved_y < 0 or H + 1 < moved_y or moved_x < 0 or W + 1 < moved_x:
                continue
            if grid[moved_y][moved_x] == 1:
                continue
            if visited[moved_y][moved_x] != -1:
                continue
            q.append((moved_y, moved_x))
            count = check_walls(moved_y, moved_x, grid, W, H, even_moves, add_moves)
            visited[moved_y][moved_x] = count
            answer_count += count

    print(answer_count)

Many problems are based on a grid pattern, but this problem is slightly different because one square is a hexagon. However, the way of thinking and solving does not change much, and the only thing to change is how to set the coordinates of the movement of `` `BFS. Specifically, in my case, it is the part defined by moves```.

In this problem, when the `` `y``` coordinates are even and odd, the destinations that can be moved from each square are different. Therefore, each is defined as follows.


even_moves = [(-1, -1), (-1, 0), (0, 1), (1, 0), (1, -1), (0, -1)] #Clockwise from top left
add_moves = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (0, -1)] #Clockwise from top left

If it is a normal grid pattern, the moving components of up / down / left / right or up / down / left / right + diagonal are defined as follows, so only this is different.


moves = [(1, 0), (0, 1), (-1, 0), (0, -1)] #Only up, down, left and right

moves = [(1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (-1, -1), (1, -1), (-1, 1)] #Up down left right+When diagonal

If you hold down here, the rest will be solved as the following policy

  1. The big policy is to search for "locations without buildings" with `` `BFS```, count the adjacent buildings at each location, and the total is the answer.
  2. For that purpose, first add "places without buildings" to the top, bottom, left, and right of the grid received by default.
  3. Execute `` `BFS``` from the upper left (0, 0) of the grid
  4. At that time, it is not the usual 0, 1 that is recorded in `` `visited```, but the number of adjacent buildings
  5. Therefore, create a function check_walls to count the number of adjacent buildings.
  6. When performing `BFS```, be careful because the behavior differs depending on whether `y``` is even or odd.
  7. The answer is the sum of the numbers returned by `` `check_wallsafter going through BFS```.

is.


032. AOJ 1166 --Maze and Order

image.png image.png

Answer


from collections import deque

def main(w, h):
    tatebou = []
    yokobou = [[0] * w]
    for _ in range(h-1):
        tate = [0] + list(map(int, input().split()))
        yoko = list(map(int, input().split()))
        tatebou.append(tate)
        yokobou.append(yoko)
    tate = [0] + list(map(int, input().split()))
    tatebou.append(tate)
    visited = [[0] * w for _ in range(h)]
    moves = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    q = deque()
    q.append((0, 0))
    visited[0][0] = 1

    while q:
        y, x = q.popleft()

        for dy, dx in moves:
            moved_y = y + dy
            moved_x = x + dx

            if dy == 1 and dx == 0:
                if moved_y < 0 or h-1 < moved_y or moved_x < 0 or w-1 < moved_x: #Outside the maze
                    continue
                if visited[moved_y][moved_x] != 0:
                    continue
                if yokobou[moved_y][moved_x] == 1: #When you go down, you can't move when the destination is 1.
                    continue
                visited[moved_y][moved_x] = visited[y][x] + 1
                q.append((moved_y, moved_x))

            elif dy == -1 and dx == 0:
                if moved_y < 0 or h-1 < moved_y or moved_x < 0 or w-1 < moved_x: #Outside the maze
                    continue
                if visited[moved_y][moved_x] != 0:
                    continue
                if yokobou[y][moved_x] == 1: #When you go up, don't when you're 1
                    continue
                visited[moved_y][moved_x] = visited[y][x] + 1
                q.append((moved_y, moved_x))

            elif dy == 0 and dx == 1:
                if moved_y < 0 or h-1 < moved_y or moved_x < 0 or w-1 < moved_x: #Outside the maze
                    continue
                if visited[moved_y][moved_x] != 0:
                    continue
                if tatebou[moved_y][moved_x] == 1: #When you go to the right, you can't move when the destination is 1.
                    continue
                visited[moved_y][moved_x] = visited[y][x] + 1
                q.append((moved_y, moved_x))
            else: # dy == 0 and dx == -1
                if moved_y < 0 or h-1 < moved_y or moved_x < 0 or w-1 < moved_x: #Outside the maze
                    continue
                if visited[moved_y][moved_x] != 0:
                    continue
                if tatebou[moved_y][x] == 1: #When you go to the left, you can't when you're 1.
                    continue
                visited[moved_y][moved_x] = visited[y][x] + 1
                q.append((moved_y, moved_x))
            
    return visited[h-1][w-1]


if __name__ == "__main__":

    answer_list = []
    while True:
        w, h = map(int, input().split())
        if w == 0 and h == 0:
            break

        answer = main(w, h)
        answer_list.append(answer)

    for answer in answer_list:
        print(answer)


It's basically the same as problem 29. The difference is the collision detection. Problem 29 is easy because it was a collision detection that "you can't go to the square itself", but this problem is not "mass" but "wall". Therefore, it is necessary to separate cases that are not necessary for normal BFS. Specifically, it is necessary to change the hit judgment as shown below depending on how you move up, down, left, and right.



            if dy == 1 and dx == 0:
                if yokobou[moved_y][moved_x] == 1: #When you go down, you can't move when the destination is 1.
                    continue
            elif dy == -1 and dx == 0:
                if yokobou[y][moved_x] == 1: #When you go up, don't when you're 1
                    continue
            elif dy == 0 and dx == 1:
                if tatebou[moved_y][moved_x] == 1: #When you go to the right, you can't move when the destination is 1.
                    continue
            else: # dy == 0 and dx == -1
                if tatebou[moved_y][x] == 1: #When you go to the left, you can't when you're 1.
                    continue

Other than this collision detection, just write normally.


  1. AtCoder Beginner Contest 088 D - Grid Repainting image.png image.png

Answer


#Only white moves(0,0)From(H-1, W-1)go to
#At that time, increase black as much as possible
#The answer is the total white minus the shortest distance

from collections import deque


H, W = map(int, input().split())
grid = [list(input()) for _ in range(H)] # .Is white,#Is black
visited = [[-1] * W for _ in range(H)]
moves = [(1, 0), (0, 1), (-1, 0), (0, -1)]

q = deque()
q.append((0, 0))
visited[0][0] = 0

while q:
    y, x = q.popleft()

    for dy, dx in moves:
        moved_y = y + dy
        moved_x = x + dx

        if moved_y < 0 or H-1 < moved_y or moved_x < 0 or W-1 < moved_x:
            continue
        if grid[moved_y][moved_x] == '#':
            continue
        if visited[moved_y][moved_x] != -1:
            continue

        visited[moved_y][moved_x] = visited[y][x] + 1
        q.append((moved_y, moved_x))

min_route = visited[H-1][W-1]

if min_route == -1:
    answer = -1
else:
    total_white = 0
    for row in grid:
        total_white += row.count('.')

    answer = total_white - min_route - 1

print(answer)


If you can solve other problems, this is pretty easy. If you chew the problem and interpret it, the answer is "the number of black paints when moving from the upper left to the lower right." Interpreting this a little easier is "the number of other places that do not pass when moving from the upper left to the lower right by the shortest distance". Once you know this, you can usually calculate the shortest distance with `` `BFS``` and subtract from the whole.

So the policy is

  1. `(0,0)` Start, `(H-1, W-1) ``` Goal to calculate the shortest distance `min_route```
  2. Calculate the total number of whites `total_white`
  3. The answer is `total_white` minus `min_route``` (` `min_route``` is a zero start, so add -1)

is.


Recommended Posts

Solve with Python [100 past questions that beginners and intermediates should solve] (028 --033 breadth-first search)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (024 --027 Depth-first search)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (015 --017 Full search: Permutation full search)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (010 --014 Full search: Bit full search)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (001 --004 All search: All enumeration)
Solve with Python [100 past questions that beginners and intermediates should solve] (053 --055 Dynamic programming: Others)
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part7 / 22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 4/22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part3 / 22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 1/22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 6/22]
Solve with Python [100 selected past questions that beginners and intermediates should solve] (056 --059 Shortest path problem: Dijkstra's algorithm)
Solve with Python [100 selections of past questions that beginners and intermediates should solve] (034-038 Dynamic programming: Knapsack DP basic)
Solve with Python [100 selections of past questions that beginners and intermediates should solve] (039 --045 Dynamic programming: Knapsack DP variant)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (005 --- 009 All search: All enumeration to reduce the number of streets by devising)
Causal reasoning and causal search with Python (for beginners)
1st Algorithm Practical Test Solve past questions with python
[Python] Depth-first search and breadth-first search
Solving with Ruby and Python AtCoder ABC151 D Breadth-first search
2nd Algorithm Practical Test Solve past questions with python (unfinished)
Solving with Ruby, Perl, Java, and Python AtCoder AGC 033 A Breadth-first search
Automatically search and download YouTube videos with Python
Let's make an app that can search similar images with Python and Flask Part1
Let's make an app that can search similar images with Python and Flask Part2
[For beginners in competition professionals] I tried to solve 40 AOJ "ITP I" questions with python
Solve simultaneous ordinary differential equations with Python and SymPy.
Crawling with Python and Twitter API 1-Simple search function
Implement Depth-First Search (DFS) and Breadth-First Search (BFS) in python
Sequential search with Python
Solve AtCoder 167 with python
Python Exercise 1-Breadth-first search
Solve Sudoku with Python
Binary search with python
Binary search with Python3
Solve POJ 2386 with python
Solve with Ruby and Python AtCoder ABC133 D Cumulative sum
Solve the spiral book (algorithm and data structure) with python!
Solve AtCoder Problems Boot camp for Beginners (Medium 100) with python
This and that for using Step Functions with CDK + Python
Module summary that automates and assists WebDriver installation with Python
[Python] Solve equations with sympy
Programming with Python and Tkinter
[Python] BFS (breadth-first search) ABC168D
Encryption and decryption with Python
Solve AtCoder ABC166 with python
Python and hardware-Using RS232C with Python-
Breadth-first search / bidirectional search (Python version)
Full bit search with Python
python with pyenv and venv
Search engine work with python
Search twitter tweets with python
Solve AtCoder ABC 186 with Python
[Python] BFS (breadth-first search) ABC007C
Streamline web search with python
Works with Python and R
I want to solve APG4b with Python (only 4.01 and 4.04 in Chapter 4)
Crawling with Python and Twitter API 2-Implementation of user search function
Solve with Ruby, Python and Java AtCoder ARC104 B Cumulative sum
Solve the Python knapsack problem with a branch and bound method
Solve the subset sum problem with a full search in Python
About bit full search that often appears in competition pros From the eyes of beginners with python