[アルゴリズム]白駿7576
9237 ワード
https://www.acmicpc.net/problem/7576
dfs/bfs粉砕3日目
問題の解き方:
1.トマトが熟していることを表していますが、基本的な迷路問題と同じです.
2.基本的なbfsアルゴリズムを実装してから、異常処理を行います!
dfs/bfs粉砕3日目
問題の解き方:
1.トマトが熟していることを表していますが、基本的な迷路問題と同じです.
2.基本的なbfsアルゴリズムを実装してから、異常処理を行います!
from collections import deque
m,n = map(int,input().split())
queue = deque()
arr = []
for _ in range(n):
arr.append(list(map(int,input().split())))
for i in range(n):
for j in range(m):
if arr[i][j] == 1 :
queue.append((i,j)) #익은 토마토 넣어주기
dx = [-1,1,0,0]
dy = [0,0,-1,1]
def dfs():
while queue:
x,y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx <= -1 or nx >= n or ny <= -1 or ny >= m:
continue
if arr[nx][ny] == -1 :
continue
if arr[nx][ny] == 0 :
queue.append((nx,ny))
arr[nx][ny] = arr[x][y] + 1
result = max(map(max,arr)) - 1 #map 이용해서 이차원 배열 max값
br = False
for row in arr :
for col in row :
if col == 0:
result = -1
br = True #이중포문 빠져나가기 위해
break
if br == True:
break
return result
print(dfs())
Reference
この問題について([アルゴリズム]白駿7576), 我々は、より多くの情報をここで見つけました https://velog.io/@yoongja/알고리즘-백준7576テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol