[白俊]7569号-トマト

📩 ソース

質問する

獣医トマト農場にはトマトを保管する大きな倉庫がある.トマトは下図のように1つずつ四角い格子に入れて倉庫に保管しています.

倉庫に保管されているトマトの中には、熟しているものもあれば、まだ熟していないものもあります.1日保管した後、熟したトマトに隣接する未熟のトマトは、熟したトマトの影響を受けて成熟する.1つのトマトの隣接する場所は、左、右、前、後の4つの方向に位置するトマトを意味する.対角線方向に影響を与えないトマトは、トマトが自分で成熟しないと仮定します.哲洙は倉庫に保管されているトマトが何日で熟れるか、最低日数を知りたいと思っている.
倉庫にトマトのチェックボックスの大きさ、熟したトマトと未熟なトマトの情報を保管している場合、数日後には、トマトが熟しているかどうか、最低日数を求めるプログラムを作成します.しかし、箱のいくつかの格にはトマトが入っていないかもしれません.

入力

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を出力します.

👉 の意見を打診

基本的には、未熟のトマト(0)をbfsで熟したトマト(1)に変えた.

熟したトマト(1)をオーブンに入れ、visitedの値を1にします.熟していないトマトの個数(cnt)も同時に調べた.

cntが0なら、いずれも熟したトマトなので、0に戻ります.

でない場合、キューから値が取得されます.ここで、熟したトマトの位置を持ってきて、上、下、左、右に移動したときの値はインデックスから離れず、まだ熟していないトマトであればQが持ってきた値に1を加えます.

は1日1個熟成しているので、熟し始めたばかりのトマトの中で隣接するトマトが1日熟成して過ぎていく様子を表現するためにvisited[nk][ni][nj] = visited[k][i][j] + 1と書かれています.

ビットのコードを打つと、最初に完熟したトマトが完熟していないトマトを完熟したトマトに変えたことを意味するので、cntの値も-1です.

dayは最後の戻り値で、箱の中のトマトがすべて熟成した일を返すために使用され、[nk][ni][nj]にアクセスした値は最初に熟成したトマト(0)から1増加した.つまり、最後の完熟トマトの値(アクセス[nk][ni][nj])では、1は私たちが望む値を意味する.

whileは外に出て、cntが0でなければ、熟したトマトがあるかどうかを意味して、熟したトマトがないので、-1に戻って、さもなくばdayに戻ります!

def bfs():
    q = [0] * (m*n*h)
    front = -1
    rear = -1
    # 안익은 토마토 개수
    cnt = 0
    day = 0
    for k in range(h):
        for i in range(n):
            for j in range(m):
                if tomato[k][i][j] == 1:
                    rear += 1
                    q[rear] = (k, i, j)
                elif tomato[k][i][j] == 0:
                    cnt += 1
    if cnt == 0:
        return 0
    while front != rear:
        front += 1
        k, i, j = q[front]
        for dk, di, dj in [[-1, 0, 0], [1, 0, 0], [0, -1, 0, ], [0, 1, 0], [0, 0, -1], [0, 0, 1]]:
            nk, ni, nj = k + dk, i + di, j + dj
            if 0 <= nk < h and 0 <= ni < n and 0 <= nj < m and tomato[nk][ni][nj] == 0 and visited[nk][ni][nj] == 0:
                visited[nk][ni][nj] = visited[k][i][j] + 1
                cnt -= 1
                if visited[nk][ni][nj] > day:
                    day = visited[nk][ni][nj]
                rear += 1
                q[rear] = (nk, ni, nj)
    if cnt != 0:
        return -1
    else:
        return day

m, n, h = map(int, input().split())
tomato = [[list(map(int, input().split())) for _ in range(n)] for _ in range(h)]
visited = [[[0] * m for _ in range(n)] for _ in range(h)]
print(bfs())