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

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

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

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. s→1ofbfs、1→2ofbfs、2→3ofbfs``` ・・・と行っていき、合計of最短距離が答えとなります。

031. JOI 2012 Qualifying 5 --Illuminations

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

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.

33. AtCoder Beginner Contest 088 D - Grid Repainting

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.