白俊派森7576号.

https://www.acmicpc.net/problem/7576
一応BFSとDFSの問題を解決する予定です.

この問題には複数のBFS起点がある.

複数の始点を有するBFS

もし一人一人がBFSの始点を実行したら?
たとえば、ボックスの状態
0 0 0
0 1 0
0の場合.
(1、1)BFSを運転し、その後
(2,0)BFSを実行する.
ただし、これにより、最終日の取得方法が複雑になります.
BFSの時間的複雑度はO(NxM)であるため,いくつかのNxMが熟成トマトで最も多かった.
全時間複雑度はO(NxM)^2であった.かなり時間がかかるかもしれません.
どうすればいいですか.
BFSを実行する前に、Queueに始点を挿入します.
ボックスを入力したら、インデックスを1つずつチェックし、トマトが熟す(1)とQueueに入れます.BFS特性のため、後でQueueに入るインデックスの日付は、以前にインデックスに入った日付よりも大きいか等しい.これは当然の結果です.後で検査したからです.
このように一度キューに入れてBFSを実行することで時間を短縮できます.
今から実施しましょう.

インプリメンテーション

BFSでQueueを入れる対象は未茹でトマトです.
そのため、熟していないトマトと(熟したトマトとスペース)を区別します.
分け方は、熟していないトマトの日付を-1にします.
また,Queueに入る条件は,日付値が0未満である.つまり、熟していないトマトだけを入れます.
注意しなければならないのは、日付がゼロ未満であることです.0以下に設定すると、スペースまたは完熟トマトにもアクセスできます.
これはずっと「間違った」結果を受け取っていたからだ.

NOTE

Queueに入る目標は何ですか?
入るオブジェクトと入らないオブジェクトをどのように区別しますか.
Queueに入るとどのような効果が出るか(本問題は更新日)
よく考えたほうがいい.

CODE

import sys
from collections import deque

m, n = map(int, input().split())
box = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

day = [[0] * m for _ in range(n)]
dx = [0, 0, -1, 1]  # E,W,S,N
dy = [1, -1, 0, 0]


def how_long(arr: list):
    queue = deque([])

    # 익은 토마토 고르기 COLLECT 1
    for i in range(n):
        for j in range(m):
            if arr[i][j] == 1:
                queue.append([i, j])

            # 안 익은 토마토는 날짜를 -1로 변경
            elif arr[i][j] == 0:
                day[i][j] = -1

    # start BFS
    while queue:
        cur_x, cur_y = queue.popleft()
        for k in range(4):
            next_x = cur_x + dx[k]
            next_y = cur_y + dy[k]

            # 배열 범위 밖
            # 인접한 인덱스의 날짜가 0이상일 때, 즉, 안 익은 토마토가 아닐 때 무시
            if next_x < 0 or next_x >= n or next_y < 0 or next_y >= m or day[next_x][next_y] >= 0:
                continue  
                
            # 안 익은 토마토의 날짜 변경
            queue.append([next_x, next_y])
            day[next_x][next_y] = day[cur_x][cur_y] + 1
    
    # 날짜 최대값 구하기
    max_day = 0
    for p in range(n):
        for q in range(m):

            # 안 익은 토마토가 있다면 -1
            if day[p][q] == -1:
                return -1

            # 최대값 갱신
            if day[p][q] > max_day:
                max_day = day[p][q]
    return max_day


print(how_long(box))