[PYTHON] [At Coder] Solving a typical BFS problem [A --Darker and Darker]

[This site (AtCoder version! Ant book (beginner))](https://qiita.com/drken/items/e77685614f3c6bf86f44#%E4%BE%8B%E9%A1%8C-2-5-5warshall-floyd -% E3% 82% 92% E4% BD% BF% E3% 81% 86% E5% 95% 8F% E9% A1% 8C) is used as a reference to solve the AtCoder problem and solidify the basics of the algorithm. The solution this time is AtCoder's A --Darker and Darker. It is an educational and typical problem of breadth-first search (BFS), which is a kind of full search (it seems). (Reference: Kenchon's blog)

problem

The squares painted in black and white with H rows vertically and W columns horizontally are given. When painting the top, bottom, left, and right of all black squares in black with one operation, how many operations can you paint the whole in black? Is the problem. 1 ≦ H ,W ≦ 1000

solution

In the case of this problem ・ Problem to find the maximum value of "the shortest distance from the black square in all white squares" It can be said. In other words, it can be regarded as the shortest path problem and solved by BFS. It's a good problem because it's easy to understand the image of solving with BFS instead of DFS.

There are multiple start positions, but the point is to add them to the queue regardless and use BFS to make them "simultaneous".

• It seems that such a problem is called a "multi-point start shortest path problem". It is also important to prepare a list that records the distance from the "black square at the start". (Initialize all starting points to 0)

[Memo] By the way, if I changed the queue from list to tuple, the execution time was shortened and the memory consumption was also reduced.

from collections import deque

H, W = map(int, input().split())
grid = [input() for i in range(H)]

#Early black('#')Distance from the position of
dist = [[-1]*W for _ in range(H)]

# '#'Add the position of to the queue (= Since there are multiple this time, it will be multiple starts)
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    """
Use BFS to find the number of times to blacken all squares
    
    Args:
        black_cells:Queue containing the coordinates of "black square at the start" (multiple coordinates available)
        dist:List with distance from "black square at the start"[[-1, -1, 0], ...]
(The initial value of the white square is 0)
        
    Returns:
        g:Number of repeated operations
    """
    d = 0
    while black_cells:
        #Because it is used as a queue, pop()Not popleft()
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  #Cell is white('.')Synonymous with
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)