-
Notifications
You must be signed in to change notification settings - Fork 0
/
solution.py
53 lines (49 loc) · 1.28 KB
/
solution.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import collections
import sys
m,n = map(int,sys.stdin.readline().split())
row = 0
tomato = []
ripen=collections.deque()
obstacle_num =0
ripen_num=0
for i in range(n):
temp = list(map(int,sys.stdin.readline().split()))
for j in range(m):
if temp[j]==1:
ripen.append([row+1,j+1])
ripen_num +=1
elif temp[j] == -1:
obstacle_num+=1
temp.insert(0,-1)
temp.append(-1)
tomato.append(temp)
row+=1
tomato.insert(0, [-1 for i in range(m+2)])
tomato.append([-1 for i in range(m+2)])
answer = -1
while len(ripen) != 0:
answer+=1
_num = len(ripen)
for i in range(_num):
t = ripen.popleft()
#print(t)
if tomato[t[0]+1][t[1]]==0:
ripen.append([t[0]+1,t[1]])
tomato[t[0]+1][t[1]]=1
ripen_num+=1
if tomato[t[0]-1][t[1]]==0:
ripen.append([t[0]-1,t[1]])
tomato[t[0]-1][t[1]]=1
ripen_num+=1
if tomato[t[0]][t[1]+1]==0:
ripen.append([t[0],t[1]+1])
tomato[t[0]][t[1]+1]=1
ripen_num+=1
if tomato[t[0]][t[1]-1]==0:
ripen.append([t[0],t[1]-1])
tomato[t[0]][t[1]-1]=1
ripen_num+=1
if ripen_num+obstacle_num == n*m:
print(answer)
else:
print(-1)