-
Notifications
You must be signed in to change notification settings - Fork 1
/
ice.py
90 lines (74 loc) · 2.33 KB
/
ice.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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
'''
Submitted; Results below show the outcome for each judge test case
*
1 2 3 4 5 6 7 8 9 10 11
10.6mb 10.6mb 10.6mb 11.0mb 11.4mb 12.2mb 13.0mb 14.0mb 15.2mb t t
187ms 200ms 194ms 604ms 844ms 1160ms 1529ms 1867ms 2093ms
*
'''
from collections import deque
f = open('perimeter.in')
N = int(f.readline())
print(N)
grid = [ [-1]*(N+2) for _ in range(N+2)]
for i in range(N):
s = f.readline()
for j in range(N):
if s[j] == '#':
grid[i+1][j+1] = 0
#print(grid)
f.close()
cnt = 0
'''
def flood_fill(grid, cnt, i, j):
if grid[i][j] != 0:
return
grid[i][j] = cnt
flood_fill(grid, cnt, i+1, j)
flood_fill(grid, cnt, i-1, j)
flood_fill(grid, cnt, i, j+1)
flood_fill(grid, cnt, i, j-1)
# RecursionError: maximum recursion depth exceeded in comparison
for i in range(1, N+1):
for j in range(1, N+1):
if grid[i][j] == 0:
cnt += 1
flood_fill(grid, cnt, i, j)
'''
dirs = [(1,0), (-1,0), (0,1), (0, -1)]
for i in range(1, N+1):
for j in range(1, N+1):
if grid[i][j] == 0:
cnt += 1
de = deque()
de.append((i,j))
while len(de) > 0:
m,n = de.popleft()
if grid[m][n] != 0:
continue
else:
grid[m][n] = cnt
for d in dirs:
x = m+d[0]
y = n+d[1]
if grid[x][y] == 0:
de.append((x,y))
max_area, min_perimeter = 0, (N+1)*(N+1)
areas = [0] * (cnt+1)
perimeters = [0] * (cnt+1)
for i in range(1, N+1):
for j in range(1, N+1):
x = grid[i][j]
if x > 0:
areas[x] += 1
if grid[i+1][j] == -1: perimeters[x] += 1
if grid[i-1][j] == -1: perimeters[x] += 1
if grid[i][j+1] == -1: perimeters[x] += 1
if grid[i][j-1] == -1: perimeters[x] += 1
max_area = max(areas)
for i in range(cnt+1):
if areas[i] == max_area:
min_perimeter = min(min_perimeter,perimeters[i])
print(f'{max_area} {min_perimeter}')
with open('perimeter.out','w') as f:
f.write(f'{max_area} {min_perimeter}\n')