Python

🐒 名トマト

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

私の草

from collections import deque



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


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

def bfs():
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx<0 or nx>=n or ny<0 or ny>=m:
                continue
            if matrix[nx][ny] == 0:
                matrix[nx][ny] = matrix[x][y] + 1
                queue.append((nx,ny))
        

matrix = []
for _ in range(n):
    matrix.append(list(map(int, input().split())))

queue = deque()
for i in range(n):
    for j in range(m):
        if matrix[i][j] == 1:
            queue.append((i,j))

bfs()
result = 0
for i in matrix:
    for j in i:
        if j == 0:
            print(-1)
            exit(0)
    result = max(result, max(i))
print(result - 1)

前の問題と似ていますが、bfsキューの使用は少し異なります.

🧠 問題を理解する

6 4
1 -1  0  0  0  0
0 -1  0  0  0  0
0  0  0  0 -1  0
0  0  0  0 -1  1

例では、上記の入力を示します.
DFSアルゴリズムを使用すると、質問に要求された答えが出力されにくくなります.
BFSでは、まず熟トマト1をブラウズし、(1、1)および(6、4)をキューに添付してbfsを実行することができる.両端から出発したトマトが真ん中で出会う.

1, -1,  7,  6,  5, 4
2, -1,  6,  5,  4, 3
3,  4,  5,  6, -1, 2
4,  5,  6,  7, -1, 1