[白俊][Python]7569号トマト

[伯俊]7569号トマト

https://www.acmicpc.net/problem/7569

問題の説明📖

▶関連する質問👉🏻 これは白駿7576号トマト(2次元)の三次元問題です.
チョルスのトマト農場にはトマトを保管する大きな倉庫がある.トマトは下図のように一個ずつ四角い箱の格子に入れ、箱を垂直に積み上げて倉庫に保管します.

倉庫に保管されているトマトの中には、熟しているものもあれば、まだ熟していないものもあります.1日保管した後、熟したトマトに隣接する未熟のトマトは、熟したトマトの影響を受けて成熟する.1つのトマトに隣接する場所は、上、下、左、右、前、後の6方向に位置するトマトを意味する.対角線方向に影響を与えないトマトは、トマトが自分で成熟しないと仮定します.哲洙は倉庫に保管されているトマトが数日で熟成できるかどうか、少なくとも日数を知りたいと思っている.
倉庫にトマトのチェックボックスの大きさ、熟したトマトと未熟なトマトの情報を保管している場合、数日後には、トマトが熟しているかどうか、最低日数を求めるプログラムを作成します.しかし、箱のいくつかの格にはトマトが入っていないかもしれません.
入力
1行目は、ブロックサイズを表す2つの整数M、N、およびスタックされたブロック数を表すHを与える.Mは箱の横格子数,Nは箱の縦格子数を表す.しかし,2≦M≦100,2≦N≦100,1≦H≦100であった.2行目から、一番下の箱から一番上の箱まで、中に貯まっているトマトの情報があります.つまり、2行目からN行目まで、箱の中のトマトの情報が与えられます.各行の箱の横線のトマトの状態はM個の整数です.整数1は熟したトマトを表し、整数0は未熟のトマトを表し、整数-1はトマトを含まない格子を表す.このようなN線はH回繰り返し与えられる.
トマトが1つ以上ある場合にのみ入力します.
しゅつりょく
トマトを計算するには少なくとも数日かかります.保存からすべてのトマトが熟成している場合は0を、トマトが熟成していない場合は-1を出力します.
I/O例

質問へのアクセス💡

BFS実施

の3 Dアレイを作成し、6方向(前、後、上、下、左、右)を設定します.

1を価格の配列位置としてキューに入れます.

BFSで6方向を確認し、完熟していないトマト(0)がある場合は各+1個とした.

は最大値-1を出力します.(1から+1を行うので、dayは-1を行う必要があります.)

すべてのトマトは1時に0を出力します.

未熟トマト(0)がある場合-1を出力します.

問題を解く💡

import sys
from collections import deque

m, n, h = map(int, input().split())

matrix = [[list(map(int, sys.stdin.readline().split())) for _ in range(n)] for _ in range(h)]
visited = [[[False]*m for _ in range(n)] for _ in range(h)]

queue = deque()

dx = [-1,1,0,0,0,0]
dy = [0,0,-1,1,0,0]
dz = [0,0,0,0,-1,1]

answer = 0

def bfs():
    while queue:
        x,y,z = queue.popleft()

        for i in range(6):
            nx = x + dx[i]
            ny = y + dy[i]
            nz = z + dz[i]

            if nx < 0 or nx >= h or ny < 0 or ny >= n or nz < 0 or nz >= m:
                continue

            if matrix[nx][ny][nz] == 0 and visited[nx][ny][nz] == False:
                queue.append((nx,ny,nz))
                matrix[nx][ny][nz] = matrix[x][y][z] + 1
                visited[nx][ny][nz] = True


# 모두 1이 아닐 경우

for a in range(h):
    for b in range(n):
        for c in range(m):
            if matrix[a][b][c] == 1 and visited[a][b][c] == 0:
                queue.append((a,b,c))
                visited[a][b][c] = True
bfs()

# 토마토 확인

for a in matrix:
    for b in a:
        for c in b:
            if c == 0:
                print(-1)
                exit(0)            
        answer = max(answer, max(b))

print(answer-1)

# 어차피 모두 1이라면 0이 출력된다.

質問のヒント💡

1時間半も時間がかかったので、本当に疲れ果てた問題です.
与えられたテスト用例はすべて正しいが、伯俊に置くと間違っていて、反例を探すのに苦労した.
私のようなテストケースが正しいのですが、伯俊さんに間違いがあったら以下の事項を確認してください.
1.トマトが完熟した1の位置はすべてQに入れてスタート.
私が無視した部分はこの部分です.熟したトマトは6方向のトマトを同時に煮る.
BFSを実装するには、まずシングルポジションをすべてキューに入れてから開始します.
次の例があります.

3 3 2
0 0 1
0 -1 0
1 0 0
0 1 0
-1 0 0 
0 0 0

答えは3です.
5を印刷しました.あらかじめ1の位置をQに置くのではなく、for文で順番にQに置く.
breakは重複文を1つだけ漏らした.終了時にexit(0)を書きます.
熟していないトマトがあれば、-1を出力してプログラムを閉じるべきです.
このときbreakを使うと熟していないトマトがあるたびに-1が出力されます.
3.print(答え-1)なので、すべてのトマトが1であれば、どうせ0を出力します.

もとは、トマトがすべて1であれば、出力0のコードを別途書きました.

問題の条件をよく考えなさい.
トマトが熟したら(いずれも1なら)、0を出力します.
よく知っていれば、bfs関数を迂回して、どうせprint(答え-1)の答えは0です.
これでもう少し時間を減らすことができます.