白駿7576号:トマト(Python)
1486 ワード
質問する
白駿7576号:トマト
に答える
bfsで解決した
ソースコード
import sys
from collections import deque
input = sys.stdin.readline
ripetmt, notyet, empty = 1, 0, -1 #익은 토마토, 익지않은 토마토, 비어있음
dir = [(-1, 0),(1, 0),(0, -1),(0, 1)] #상하좌우
def bfs():
ans = 0
while len(ripe)>0:
o = ripe.popleft()
r, c, day = o[0], o[1], o[2]
for d in dir:
nextr, nextc = r+d[0], c+d[1]
if nextr<0 or nextr>=N or nextc<0 or nextc>=M:
#상자 범위 초과
continue
nextb = box[nextr][nextc]
if nextb==empty or nextb==ripetmt:
#비어있거나 이미 익은 상태
continue
else:
# 익지 않은 토마토
# 익은 상태로 바꾼 후에 큐에 넣어준다
box[nextr][nextc] = ripetmt
ans = max(ans, day+1)
ripe.append((nextr, nextc, day+1))
for i in range(N):
for j in range(M):
# 상자에 익지 않은 토마토가 있는지 검사
if box[i][j]==notyet:
ans = -1
break
return ans
M, N = map(int, input().rstrip().split())
box = [list(map(int, input().rstrip().split())) for _ in range(N)]
ripe = deque()
for i in range(N):
for j in range(M):
if box[i][j]==ripetmt:
ripe.append((i, j, 0))
print(bfs())
Reference
この問題について(白駿7576号:トマト(Python)), 我々は、より多くの情報をここで見つけました https://velog.io/@kayoung0/백준-7576번-토마토Pythonテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol