-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy path4963.py
69 lines (50 loc) · 1.82 KB
/
4963.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
54
55
56
57
58
59
60
61
62
63
64
65
from collections import deque
from sys import stdin
while True:
width, height = [int(x) for x in stdin.readline().split()]
if width == 0 and height == 0:
break
island_matrix = []
island_vector = []
for i in range(height):
map_info = [int(x) for x in stdin.readline().split()]
island_matrix.append(map_info)
for j in range(width):
if map_info[j] == 1:
island_vector.append([i, j])
visited = [["white" for j in range(width)] for i in range(height)]
distance = [[0 for j in range(width)] for i in range(height)]
def bfs(y, x, distance_value):
q = deque()
q.append([y, x])
visited[y][x] = 'gray'
distance[y][x] = distance_value
while q:
y,x = q.popleft()
adjacent_vector = [
[y-1, x], [y+1, x],
[y, x-1], [y, x+1],
[y-1, x-1], [y+1, x-1],
[y-1, x+1], [y+1, x+1]
]
for next_y, next_x in adjacent_vector:
if next_y < 0 or next_y >= height or next_x < 0 or next_x >= width:
continue
if visited[next_y][next_x] == 'gray' or island_matrix[next_y][next_x] == 0:
continue
q.append([next_y, next_x])
distance[next_y][next_x] = distance_value
visited[next_y][next_x] = 'gray'
if len(island_vector) == 0:
print(0)
else:
distance_value = 0
for i, vector in enumerate(island_vector):
y_vector = vector[0]
x_vector = vector[1]
if visited[y_vector][x_vector] == 'white':
distance_value += 1
else:
continue
bfs(y_vector, x_vector, distance_value)
print(distance_value)