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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| from collections import deque
n, m = list(map(int, input().split()))
source_map = []
for _ in range(n):
source_map.append(list(map(int, input().split())))
directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
target = 0
target_value = -1
def find_non_cheese_section(visit_map):
global n, m, target, target_value
queue = deque()
queue.append([0,0])
while len(queue) > 0:
x, y = queue.popleft()
for i in range(4):
nx = x + directions[i][0]
ny = y + directions[i][1]
if nx < 0 or ny < 0 or nx >= n or ny >= m:
continue
if source_map[nx][ny] != target:
continue
if visit_map[nx][ny] == target_value:
continue
visit_map[nx][ny] = target_value
queue.append([nx,ny])
def find_melt_cheese_list(visit_map):
global n, m, target, target_value
melt_pos_list = []
for i in range(n):
for j in range(m):
if visit_map[i][j] == target_value:
continue
count = 0
for k in range(4):
x = i + directions[k][0]
y = j + directions[k][1]
if x < 0 or y < 0 or x >= n or y >= m:
continue
if visit_map[x][y] == target_value:
count += 1
if count >= 2:
melt_pos_list.append([i,j])
return melt_pos_list
def melt_cheese(melt_pos_list):
for x,y in melt_pos_list:
source_map[x][y] = 0
def is_no_cheese_left():
for i in range(n):
for j in range(m):
if source_map[i][j] == 1:
return False
return True
count = 0
while not is_no_cheese_left():
visit_map = [[0] * m for _ in range(n)]
find_non_cheese_section(visit_map)
melt_pos_list = find_melt_cheese_list(visit_map)
melt_cheese(melt_pos_list)
count += 1
print(count)
|