-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path12A.py
36 lines (29 loc) · 819 Bytes
/
12A.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
import sys
from collections import deque
def bfs(x, y):
letter = grid[x][y]
queue = deque([(x, y)])
vis[x][y] = True
a = p = 0
while queue:
r, c = queue.popleft()
a += 1
for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < m and grid[nr][nc] == letter:
if not vis[nr][nc]:
vis[nr][nc] = True
queue.append((nr, nc))
else:
p += 1
return a, p
grid = [list(i) for i in sys.stdin.read().splitlines()]
n, m = len(grid), len(grid[0])
vis = [[False] * m for i in range(n)]
ans = 0
for i in range(n):
for j in range(m):
if not vis[i][j]:
a, p = bfs(i, j)
ans += a * p
print(ans)