トマト(BFS使用)
11014 ワード
深度/幅優先ナビゲーション(DFS、BFS)による
に質問
トマト(BFS使用)
賢洙のトマト農場にはトマトを保管する大きな倉庫がある.トマトは下図のように1つずつ四角い格子に入れて倉庫に保管しています.
倉庫に保管されているトマトの中には、熟しているものもあれば、まだ熟していないものもあります.1日保管した後、熟したトマトに隣接する未熟のトマトは、熟したトマトの影響を受けて成熟する.1つのトマトの隣接する場所は、左、右、前、後の4つの方向に位置するトマトを意味する.対角線方向に影響を与えないトマトは、トマトが自分で成熟しないと仮定します.賢洙は倉庫に保管されているトマトが何日後に熟すか、最低日数を知りたいと思っている.
倉庫にトマトのチェックボックスの大きさ、熟したトマトと未熟なトマトの情報を保管している場合、数日後には、トマトが熟しているかどうか、最低日数を求めるプログラムを作成します.しかし、箱のいくつかの格にはトマトが入っていないかもしれません.
■説明の入力
最初の行は、ボックスのサイズを表す2つの整数M,Nを与える.Mは箱の横格子数,Nは箱の縦格子数を表す.しかし,2≦M,N≦1000であった.
2行目から、1つの箱に保存されているトマトの情報が提供されます.つまり、2行目からN行目まで、箱の中のトマトの情報が出てきます.1本の線上で、箱の横線のトマトの状態はM個の整数である.整数1は熟したトマトを表し、整数0は未熟のトマトを表し、整数-1はトマトを含まない格子を表す.
■出力説明
トマトがすべて熟成した最小日付を印刷します.保存からすべてのトマトが熟成している場合は0を、トマトが熟成していない場合は-1を出力します.
■入力例1
6 4
0 0 -1 0 0 0
0 0 1 0 -1 0
0 0 -1 0 0 0
0 0 0 0 -1 1
■出力例1
4
コード#コード#💻
import sys
from collections import deque
#sys.stdin = open("input.txt", "rt") # read text
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(m)]
Q = deque()
dis = [[0] * n for _ in range(m)] # 날짜 계산하는 배열
for i in range(m):
for j in range(n):
if board[i][j] == 1:
Q.append((i, j))
while Q:
tmp = Q.popleft()
for i in range(4):
xx = tmp[0] + dx[i]
yy = tmp[1] + dy[i]
if 0 <= xx < m and 0 <= yy < n and board[xx][yy] == 0:
board[xx][yy] = 1
dis[xx][yy] = dis[tmp[0]][tmp[1]] + 1
Q.append((xx, yy))
flag = 1
for i in range(m):
for j in range(n):
if board[i][j] == 0:
flag = 0
result = 0
if flag == 1:
for i in range(m):
for j in range(n):
if dis[i][j] > result:
result = dis[i][j]
print(result)
else:
print(-1)
リファレンスReference
この問題について(トマト(BFS使用)), 我々は、より多くの情報をここで見つけました https://velog.io/@jsj3282/토마토BFS-활용テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol