AISing Programming Contest 2019 - Alternating Path

There is a grid with H rows and W columns, where each square is painted black or white.

You are given H strings S_1, S_2, ..., S_H, each of length W. If the square at the i-th row from the top and the j-th column from the left is painted black, the j-th character in the string S_i is `#`; if that square is painted white, the j-th character in the string S_i is `.`.

Find the number of pairs of a black square c_1 and a white square c_2 that satisfy the following condition:

* There is a path from the square c_1 to the square c_2 where we repeatedly move to a vertically or horizontally adjacent square through an alternating sequence of black and white squares: black, white, black, white...

Constraints

* 1 \leq H, W \leq 400
* |S_i| = W (1 \leq i \leq H)
* For each i (1 \leq i \leq H), the string S_i consists of characters `#` and `.`.

Input

Input is given from Standard Input in the following format:


H W
S_1
S_2
:
S_H


Output

Print the answer.

Examples

Input

3 3
.#.
..#
#..


Output

10


Input

3 3
.#.
..#
..


Output

10


Input

2 4
....
....


Output

0


Input

4 3


...


Output

6

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
(h, w) = map(int, input().split())
S = [input() for _ in range(h)]
avail = [[True] * w for _ in range(h)]

def search(i, j, data):
	if S[i][j] == '#':
		data[0] += 1
	else:
		data[1] += 1
	avail[i][j] = False
	if i + 1 < h and S[i + 1][j] != S[i][j] and avail[i + 1][j]:
		search(i + 1, j, data)
	if j + 1 < w and S[i][j + 1] != S[i][j] and avail[i][j + 1]:
		search(i, j + 1, data)
	if i > 0 and S[i][j] != S[i - 1][j] and avail[i - 1][j]:
		search(i - 1, j, data)
	if j > 0 and S[i][j] != S[i][j - 1] and avail[i][j - 1]:
		search(i, j - 1, data)
ans = 0
for i in range(h):
	for j in range(w):
		if avail[i][j]:
			data = [0, 0]
			search(i, j, data)
			ans += data[0] * data[1]
print(ans)


(h, w) = map(int, input().split())
s = [[''] * (w + 2)]
s += [[''] + list(input()) + [''] for _ in range(h)]
s += [[''] * (w + 2)]
m = [[1] * (w + 2)]
m += [[1] + [0] * w + [1] for _ in range(h)]
m += [[1] * (w + 2) for _ in range(h + 2)]
ans = 0
for i in range(1, h + 1):
	for j in range(1, w + 1):
		if m[i][j] == 1:
			continue
		m[i][j] = 1
		qs = [[i, j]]
		white = 0
		black = 0
		while len(qs) != 0:
			q = qs.pop(0)
			if s[q[0]][q[1]] == '.':
				white += 1
			else:
				black += 1
			m[q[0]][q[1]] = 1
			for k in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
				if m[q[0] + k[0]][q[1] + k[1]] == 0 and s[q[0]][q[1]] != s[q[0] + k[0]][q[1] + k[1]]:
					m[q[0] + k[0]][q[1] + k[1]] = 1
					qs.append([q[0] + k[0], q[1] + k[1]])
		ans += black * white
print(ans)


import sys
sys.setrecursionlimit(10 ** 9)

def dfs(x: int, y: int) -> None:
	global blk, wht
	seen[x][y] = 1
	cur = S[x][y]
	if cur:
		blk += 1
	else:
		wht += 1
	for (dx, dy) in dxy:
		(nx, ny) = (x + dx, y + dy)
		if 0 <= nx < H and 0 <= ny < W and (S[nx][ny] != cur) and (not seen[nx][ny]):
			dfs(nx, ny)

def main():
	global H, W, S, seen, dxy, blk, wht
	(H, W, *S) = open(0).read().split()
	(H, W) = (int(H), int(W))
	S = [[1 if i == '#' else 0 for i in s] for s in S]
	seen = [[0] * W for _ in range(H)]
	dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
	ans = 0
	for i in range(H):
		for j in range(W):
			if not seen[i][j]:
				(blk, wht) = (0, 0)
				dfs(i, j)
				ans += blk * wht
	print(ans)
main()


(h, w) = map(int, input().split())
s = [input() for _ in range(h)]
check = [[False for _ in range(w)] for __ in range(h)]
import queue
q = queue.Queue()
nh = [1, 0, -1, 0]
nw = [0, 1, 0, -1]
ans = 0
for i in range(h):
	for j in range(w):
		if check[i][j]:
			continue
		check[i][j] = True
		cnt = [0] * 2
		cnt[s[i][j] == '#'] += 1
		q.put([i, j])
		while not q.empty():
			(nowi, nowj) = q.get()
			for ne in range(4):
				ni = nowi + nh[ne]
				nj = nowj + nw[ne]
				if ni < 0 or h <= ni or nj < 0 or (w <= nj):
					continue
				if s[nowi][nowj] == s[ni][nj]:
					continue
				if check[ni][nj]:
					continue
				check[ni][nj] = True
				cnt[s[ni][nj] == '#'] += 1
				q.put([ni, nj])
		ans += cnt[0] * cnt[1]
print(ans)


import sys
sys.setrecursionlimit(300000)
(H, W) = map(int, input().split())
S = [input() for y in range(H)]
visited = [[False] * W for y in range(H)]

def color(y, x):
	if y < 0 or H <= y or x < 0 or (W <= x) or visited[y][x]:
		return '@'
	else:
		return S[y][x]

def dfs(y, x):
	b = 0
	w = 0
	nxt = 'n'
	if color(y, x) == '.':
		w = 1
		nxt = '#'
	elif color(y, x) == '#':
		b = 1
		nxt = '.'
	visited[y][x] = True
	if color(y - 1, x) == nxt:
		(_b, _w) = dfs(y - 1, x)
		b += _b
		w += _w
	if color(y + 1, x) == nxt:
		(_b, _w) = dfs(y + 1, x)
		b += _b
		w += _w
	if color(y, x - 1) == nxt:
		(_b, _w) = dfs(y, x - 1)
		b += _b
		w += _w
	if color(y, x + 1) == nxt:
		(_b, _w) = dfs(y, x + 1)
		b += _b
		w += _w
	return (b, w)
ans = 0
for y in range(H):
	for x in range(W):
		(b, w) = dfs(y, x)
		ans += b * w
print(ans)


import queue
(H, W) = map(int, input().split())
S = [list(map(int, input().replace('.', '0').replace('#', '1'))) for h in range(H)]
Search = [(-1, 0), (0, -1), (1, 0), (0, 1)]
Total = 0
Visited = [[False for w in range(W)] for h in range(H)]
for h in range(H):
	for w in range(W):
		if not Visited[h][w]:
			Visited[h][w] = True
			Color = [1, 0] if S[h][w] == 0 else [0, 1]
			Q = queue.Queue()
			Q.put((h, w, S[h][w]))
			while not Q.empty():
				(nh, nw, nc) = Q.get()
				for s in Search:
					(nexth, nextw) = (nh + s[0], nw + s[1])
					if 0 <= nexth < H and 0 <= nextw < W:
						if not Visited[nexth][nextw] and S[nexth][nextw] != nc:
							nextc = S[nexth][nextw]
							Visited[nexth][nextw] = True
							Q.put((nexth, nextw, nextc))
							Color[nextc] += 1
			Total += Color[0] * Color[1]
print(Total)


import sys
sys.setrecursionlimit(10 ** 7)
(h, w) = map(int, input().split())
s = [input() for _ in range(h)]
flag = [[0] * w for _ in range(h)]

def dfs(th, tw):
	global flag, h, w, s
	flag[th][tw] = True
	tblack = 0
	twhite = 0
	if s[th][tw] == '#':
		tblack += 1
	else:
		twhite += 1
	for (x, y) in ([0, 1], [0, -1], [1, 0], [-1, 0]):
		nth = th + x
		ntw = tw + y
		if nth >= 0 and nth < h and (ntw >= 0) and (ntw < w):
			if not flag[nth][ntw] and s[th][tw] != s[nth][ntw]:
				(ttb, ttw) = dfs(nth, ntw)
				tblack += ttb
				twhite += ttw
	return [tblack, twhite]

def main():
	global flag, h, w, s
	res = 0
	for i in range(h):
		for j in range(w):
			if not flag[i][j]:
				(black, white) = dfs(i, j)
				res += black * white
	return res
print(main())


from collections import deque

def bfs(S):
	que = deque([S])
	(b, w) = (0, 0)
	while len(que) > 0:
		(p, q) = que.popleft()
		b += int(s[p][q] == '#')
		w += int(s[p][q] == '.')
		for (i, j) in near[p][q]:
			if (i, j) in frag:
				continue
			(que.append((i, j)), frag.add((i, j)))
	return b * w
(h, w) = map(int, input().split())
s = [input() for _ in range(h)]
near = [[set() for j in range(w)] for i in range(h)]
for (i, si) in enumerate(s):
	for (j, sij) in enumerate(si):
		for (p, q) in [(i - 1, j), (i, j - 1), (i + 1, j), (i, j + 1)]:
			if 0 <= p < h and 0 <= q < w and (s[p][q] != sij):
				near[i][j].add((p, q))
(ans, frag) = (0, set())
for i in range(h):
	for j in range(w):
		if (i, j) not in frag:
			frag.add((i, j))
			ans += bfs((i, j))
print(ans)


import collections
(H, W) = map(int, input().split())
S = [list(input()) for i in range(H)]
remaining = set()
for i in range(H):
	for j in range(W):
		remaining.add((i, j))
q = collections.deque()
ans = 0
while remaining:
	(i, j) = remaining.pop()
	q.append((i, j))
	black = 0
	white = 0
	while q:
		(y, x) = q.popleft()
		if S[y][x] == '#':
			black += 1
		else:
			white += 1
		if (y - 1, x) in remaining and S[y][x] != S[y - 1][x]:
			remaining.remove((y - 1, x))
			q.append((y - 1, x))
		if (y, x - 1) in remaining and S[y][x] != S[y][x - 1]:
			remaining.remove((y, x - 1))
			q.append((y, x - 1))
		if (y + 1, x) in remaining and S[y][x] != S[y + 1][x]:
			remaining.remove((y + 1, x))
			q.append((y + 1, x))
		if (y, x + 1) in remaining and S[y][x] != S[y][x + 1]:
			remaining.remove((y, x + 1))
			q.append((y, x + 1))
	ans += black * white
print(ans)


import sys
sys.setrecursionlimit(10000000)
(H, W) = map(int, input().split())
S = [input() for _ in range(H)]
seen = [[0] * W for _ in range(H)]

def rec(h, w, seen):
	if S[h][w] == '.':
		res = [1, 0]
	else:
		res = [0, 1]
	dh = [-1, 1, 0, 0]
	dw = [0, 0, -1, 1]
	seen[h][w] = 1
	for i in range(4):
		nh = h + dh[i]
		nw = w + dw[i]
		if 0 <= nh <= H - 1 and 0 <= nw <= W - 1:
			if seen[nh][nw] == 0 and S[nh][nw] != S[h][w]:
				(r0, r1) = rec(nh, nw, seen)
				res[0] += r0
				res[1] += r1
	return res
ans = 0
for h in range(H):
	for w in range(W):
		if seen[h][w] != 1:
			(t0, t1) = rec(h, w, seen)
			ans += t0 * t1
print(ans)


import sys
sys.setrecursionlimit(1000 * 1000)
(H, W) = map(int, input().split(' '))
map_info = [input() for i in range(H)]
visit = [[False for j in range(W)] for i in range(H)]
ans = 0

def search(i, j, want_color):
	if i < 0 or i >= H:
		return
	if j < 0 or j >= W:
		return
	if visit[i][j]:
		return
	this_color = map_info[i][j]
	if want_color != this_color:
		return
	global white
	global black
	visit[i][j] = True
	if this_color == '.':
		white += 1
		next_color = '#'
	else:
		black += 1
		next_color = '.'
	search(i, j + 1, next_color)
	search(i, j - 1, next_color)
	search(i + 1, j, next_color)
	search(i - 1, j, next_color)
for i in range(H):
	for j in range(W):
		white = 0
		black = 0
		search(i, j, map_info[i][j])
		ans += black * white
print(ans)


belong = list()
group = list()
C = list()

def init(X):
	global belong, group, C
	belong = list(range(X))
	group = [[i] for i in range(X)]
	C = [[S[i // W][i % W] == '#', S[i // W][i % W] == '.'] for i in range(X)]

def unite(x, y):
	if len(group[belong[x]]) < len(group[belong[y]]):
		(x, y) = (y, x)
	if belong[x] == belong[y]:
		return True
	z = belong[y]
	for i in range(len(group[z])):
		belong[group[z][-1]] = belong[x]
		group[belong[x]].append(group[z][-1])
		del group[z][-1]
	for i in range(2):
		C[belong[x]][i] += C[z][i]
		C[z][i] = 0
	return False
(H, W) = map(int, input().split())
S = [input() for i in range(H)]
init(H * W)
for i in range(H):
	for j in range(W):
		if i:
			if S[i][j] != S[i - 1][j]:
				unite(i * W + j, i * W + j - W)
		if j:
			if S[i][j] != S[i][j - 1]:
				unite(i * W + j, i * W + j - 1)
		if i + 1 < H:
			if S[i][j] != S[i + 1][j]:
				unite(i * W + j, i * W + j + W)
		if j + 1 < W:
			if S[i][j] != S[i][j + 1]:
				unite(i * W + j, i * W + j + 1)
P = 0
for i in range(H * W):
	P += C[i][0] * C[i][1]
print(P)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
(h, w) = map(int, input().split())
n = h * w
fld = ''.join([input().rstrip() for _ in range(h)])

def to_v(i, j):
	return i * w + j

def generate_v2(v):
	(i, j) = divmod(v, w)
	if 0 < i:
		yield (v - w)
	if i < h - 1:
		yield (v + w)
	if 0 < j:
		yield (v - 1)
	if j < w - 1:
		yield (v + 1)

def dfs(v, c=0):
	if visited[v]:
		return
	visited[v] = 1
	cnt[c] += 1
	for v2 in generate_v2(v):
		if fld[v] == fld[v2]:
			continue
		dfs(v2, c ^ 1)
visited = [0] * n
ans = 0
for v in range(n):
	if visited[v]:
		continue
	cnt = [0, 0]
	dfs(v)
	ans += cnt[0] * cnt[1]
print(ans)


(t, *grid) = open(0)
(h, w) = map(int, t.split())
vis = [[False] * w for _ in range(h)]
ans = 0
for y in range(h):
	for x in range(w):
		if vis[y][x]:
			continue
		q = [(y, x)]
		d = {'#': 0, '.': 0}
		while q:
			(cy, cx) = q.pop(0)
			for (ny, nx) in ((cy + 1, cx), (cy - 1, cx), (cy, cx + 1), (cy, cx - 1)):
				if not (0 <= ny < h and 0 <= nx < w) or vis[ny][nx] or grid[cy][cx] == grid[ny][nx]:
					continue
				d[grid[ny][nx]] += 1
				vis[ny][nx] = True
				q.append((ny, nx))
		ans += d['#'] * d['.']
print(ans)


(h, w) = map(int, input().split())
s = [input() for i in range(h)]
mx = [1, -1, 0, 0]
my = [0, 0, 1, -1]
vis = [[0] * w for i in range(h)]
import queue
q = queue.Queue()
ans = 0
for i in range(h):
	for j in range(w):
		if vis[i][j] == 0:
			white = 0
			black = 0
			q.put([i, j])
			vis[i][j] = 1
			while not q.empty():
				(y, x) = q.get()
				if s[y][x] == '.':
					white += 1
				else:
					black += 1
				for k in range(4):
					nx = x + mx[k]
					ny = y + my[k]
					if 0 <= nx <= w - 1 and 0 <= ny <= h - 1 and (vis[ny][nx] == 0):
						if s[y][x] != s[ny][nx]:
							q.put([ny, nx])
							vis[ny][nx] = 1
			if white + black != 1:
				ans += white * black
print(ans)


import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def DFS(add, next, cnt):
	(x, y) = add
	for (i, j) in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
		(X, Y) = (x + i, y + j)
		if 0 <= X < h and 0 <= Y < w:
			if S[X][Y] == next and color[X][Y] == 'white':
				color[X][Y] = str(cnt)
				DFS([X, Y], '.' if next == '#' else '#', cnt)
(h, w) = map(int, input().split())
S = [list(input()) for _ in range(h)]
cnt = 0
color = [['white' for _ in range(w)] for _ in range(h)]
for i in range(h):
	for j in range(w):
		if S[i][j] == '#' and color[i][j] == 'white':
			cnt += 1
			DFS([i, j], '.', cnt)
dictionary = {str(i + 1): [0, 0] for i in range(cnt)}
for i in range(h):
	for j in range(w):
		if color[i][j] != 'white':
			if S[i][j] == '.':
				dictionary[color[i][j]][0] += 1
			else:
				dictionary[color[i][j]][1] += 1
ans = 0
for (v, m) in dictionary.values():
	ans += v * m
print(ans)


(h, w) = [int(j) for j in input().split()]
s = [input() for i in range(h)]
par = [-1 for i in range(h * w)]

def root(a):
	if par[a] < 0:
		return a
	else:
		return root(par[a])

def size(a):
	return -par[root(a)]

def connect(a, b):
	a = root(a)
	b = root(b)
	if a == b:
		return False
	if size(a) < size(b):
		(a, b) = (b, a)
	par[a] += par[b]
	par[b] = a
	return True
for i in range(h):
	for j in range(w):
		for (x, y) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
			(p, q) = (i + x, j + y)
			if 0 <= p < h and 0 <= q < w:
				if s[p][q] != s[i][j]:
					if root(w * p + q) != root(w * i + j):
						connect(w * p + q, w * i + j)
from collections import Counter
c = Counter()
for i in range(h):
	for j in range(w):
		p = i * w + j
		q = root(p)
		if c[q] == 0:
			c[q] = [0, 0]
		if s[i][j] == '#':
			c[q][0] += 1
		else:
			c[q][1] += 1
ans = 0
for i in c:
	ans += c[i][0] * c[i][1]
print(ans)


import collections
import sys
sys.setrecursionlimit(1000000)
(H, W) = map(int, input().split())
S = [list(input()) for _ in range(H)]
seen = [[False] * W for i in range(H)]
move = ((-1, 0), (1, 0), (0, -1), (0, 1))
q = collections.deque()

def bfs(i, j):
	(b, w) = (0, 0)
	seen[i][j] = True
	q.append((i, j))
	while q:
		(ci, cj) = q.popleft()
		if S[ci][cj] == '#':
			b += 1
		else:
			w += 1
		for (di, dj) in move:
			ni = ci + di
			nj = cj + dj
			if 0 <= ni < H and 0 <= nj < W:
				if seen[ni][nj] is False and S[ci][cj] != S[ni][nj]:
					seen[ni][nj] = True
					q.append((ni, nj))
	return b * w
ans = 0
for i in range(H):
	for j in range(W):
		if S[i][j] == '#' and seen[i][j] is False:
			ans += bfs(i, j)
print(ans)


import sys
sys.setrecursionlimit(4100000)
(H, W) = map(int, input().split())
S = []
for _ in range(H):
	S.append(list(input()))
C = [[1 for i in range(W)] for j in range(H)]
L = ['.', '#']
D = {'.': 0, '#': 1}
tx = [1, 0, -1, 0]
ty = [0, 1, 0, -1]

def dfs(x, y, c, l):
	C[x][y] = 0
	l[c] += 1
	for i in range(4):
		nx = x + tx[i]
		ny = y + ty[i]
		if 0 <= nx < H and 0 <= ny < W and C[nx][ny] and (L[c] != S[nx][ny]):
			l = dfs(nx, ny, 1 - c, l)
	return l
ans = 0
for i in range(H):
	for j in range(W):
		l = dfs(i, j, D[S[i][j]], [0, 0])
		ans += l[0] * l[1]
print(ans)


(h, w) = map(int, input().split())
P = []
for i in range(h):
	C = [str(_) for _ in input()]
	P += C
par = [[-1, 0, 0] for _ in range(h * w)]

def find(x):
	if par[x][0] < 0:
		return x
	else:
		par[x][0] = find(par[x][0])
		return par[x][0]

def unite(x, y):
	x = find(x)
	y = find(y)
	if x == y:
		return False
	else:
		if par[x][0] > par[y][0]:
			(x, y) = (y, x)
		par[x][0] += par[y][0]
		par[y][0] = x
		return True

def same(x, y):
	return find(x) == find(y)

def size(x):
	return -par[find(x)][0]
for i in range(h * w):
	if P[i] == '#':
		par[i][1] += 1
		if (i + 1) % w != 0 and P[i + 1] == '.':
			unite(i, i + 1)
		if i + w < h * w and P[i + w] == '.':
			unite(i, i + w)
	else:
		par[i][2] += 1
		if (i + 1) % w != 0 and P[i + 1] == '#':
			unite(i, i + 1)
		if i + w < h * w and P[i + w] == '#':
			unite(i, i + w)
ans = 0
for (p, x, y) in par:
	if p >= 0:
		par[find(p)][1] += x
		par[find(p)][2] += y
for (p, x, y) in par:
	if p < -1:
		ans += x * y
print(ans)


import sys
sys.setrecursionlimit(410000)
(h, w) = map(int, input().split())
F = []
for i in range(h):
	F.append(list(input()))
V = [[False] * w for _ in range(h)]

def dfs(y, x, c):
	V[y][x] = True
	black = 0
	white = 0
	if c == '#':
		black += 1
	else:
		white += 1
	for (dy, dx) in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
		ny = y + dy
		nx = x + dx
		if 0 <= ny < h and 0 <= nx < w:
			if F[ny][nx] != c and V[ny][nx] == False:
				nc = '#'
				if c == '#':
					nc = '.'
				(bn, wn) = dfs(ny, nx, nc)
				black += bn
				white += wn
	return (black, white)
ans = 0
for i in range(h):
	for j in range(w):
		if F[i][j] == '#':
			(black, white) = dfs(i, j, '#')
			ans += black * white
print(ans)


(h, w) = map(int, input().split())
S = [input() for i in range(h)]
M = [[] for i in range(h * w)]
for i in range(h * w):
	a = i // w
	b = i % w
	for d in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
		aa = d[0] + a
		bb = d[1] + b
		if 0 <= aa < h and 0 <= bb < w and (S[a][b] != S[aa][bb]):
			M[a * w + b].append(aa * w + bb)
ans = 0
V = [0] * (h * w)
D = {'.': 0, '#': 1}
for i in range(h * w):
	if V[i] == 0:
		ANS = [0, 0]
		Q = [i]
		s = 0
		V[i] = 1
		ANS[D[S[i // w][i % w]]] += 1
		while s < len(Q):
			i = Q[s]
			for x in M[i]:
				if V[x] == 0:
					V[x] = 1
					ANS[D[S[x // w][x % w]]] += 1
					Q.append(x)
			s += 1
		ans += ANS[0] * ANS[1]
print(ans)


import sys
sys.setrecursionlimit(10 ** 7)

def dfs(i, j):
	visited[i][j] = True
	res_b = 0
	res_w = 0
	if N[i][j]:
		res_b += 1
	else:
		res_w += 1
	for (di, dj) in d:
		if i + di < 0 or i + di >= H or j + dj < 0 or (j + dj >= W):
			continue
		if N[i][j] == N[i + di][j + dj]:
			continue
		if visited[i + di][j + dj]:
			continue
		(tmp_b, tmp_w) = dfs(i + di, j + dj)
		res_b += tmp_b
		res_w += tmp_w
	return (res_b, res_w)
(H, W) = map(int, input().split())
N = [[False] * W for _ in range(H)]
for i in range(H):
	s = input()
	for j in range(W):
		N[i][j] = s[j] == '#'
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
visited = [[False] * W for _ in range(H)]
ans = 0
for i in range(H):
	for j in range(W):
		if not N[i][j]:
			continue
		if visited[i][j]:
			continue
		(b, w) = dfs(i, j)
		ans += b * w
print(ans)


(h, w) = map(int, input().split())
m = [input() for _ in range(h)]
seen = [[0] * w for _ in range(h)]
dxy = [(1, 0), (0, 1), (-1, 0), (0, -1)]
cnt = 0
for i in range(h):
	for j in range(w):
		if not seen[i][j]:
			(bcnt, wcnt) = (0, 0)
			q = [(i, j)]
			while q:
				(y, x) = q.pop()
				if seen[y][x]:
					continue
				if m[y][x] == '#':
					bcnt += 1
				else:
					wcnt += 1
				seen[y][x] = 1
				for (dx, dy) in dxy:
					if 0 <= x + dx < w and 0 <= y + dy < h and (not seen[y + dy][x + dx]) and (m[y + dy][x + dx] != m[y][x]):
						q.append((y + dy, x + dx))
			cnt += bcnt * wcnt
print(cnt)


from collections import deque
(H, W) = [int(_) for _ in input().split()]
S = [input() for _ in range(H)]
move = ((1, 0), (-1, 0), (0, 1), (0, -1))
visited = [[False] * W for _ in range(H)]

def bfs(i, j):
	(b, w) = (0, 0)
	visited[i][j] = True
	que = deque([(i, j)])
	while que:
		(ci, cj) = que.popleft()
		if S[ci][cj] == '#':
			b += 1
		else:
			w += 1
		for (di, dj) in move:
			(ni, nj) = (ci + di, cj + dj)
			if not (0 <= ni < H and 0 <= nj < W) or visited[ni][nj]:
				continue
			if S[ci][cj] != S[ni][nj]:
				visited[ni][nj] = True
				que.append((ni, nj))
	return b * w
result = 0
for i in range(H):
	for j in range(W):
		if visited[i][j]:
			continue
		result += bfs(i, j)
print(result)


from collections import defaultdict as dd
(n, mm) = [int(i) for i in input().split()]
c = 0
A = []
m = dd(tuple)
for i in range(n):
	B = input()
	for j in range(mm):
		m[i, j] = c
		c += 1
	A.append([i == '#' for i in B])
par = [i for i in range(c)]

def find(a):
	if par[a] == a:
		return a
	par[a] = find(par[a])
	return par[a]

def unite(a, b):
	if a < b:
		(a, b) = (b, a)
	par[find(a)] = find(b)

def issafe(x, y):
	return x >= 0 and x < n and (y >= 0) and (y < mm)
for i in range(n):
	for j in range(mm):
		dx = [[-1, 0], [0, 1], [0, -1], [1, 0]]
		for k in range(len(dx)):
			if issafe(i + dx[k][0], j + dx[k][1]) and A[i][j] != A[i + dx[k][0]][j + dx[k][1]]:
				unite(m[i, j], m[i + dx[k][0], j + dx[k][1]])
bl = [0] * c
wh = [0] * c
for i in range(n):
	for j in range(mm):
		if A[i][j] == 1:
			bl[find(m[i, j])] += 1
		else:
			wh[find(m[i, j])] += 1
ans = 0
for i in range(c):
	ans += bl[i] * wh[i]
print(ans)


from collections import deque
(h, w) = map(int, input().split())
sq = [list(input()) for i in range(h)]
prt = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
	for j in range(w):
		c = i + j
		if sq[i][j] == '#':
			c += 1
		prt[i][j] = c % 2
que = deque([])
ans = 0
visited = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
	for j in range(w):
		if visited[i][j] != 1:
			que.append((i, j))
			cnt = 0
			cntb = 0
			while que:
				(x, y) = que.popleft()
				if visited[x][y] != 1:
					cnt += 1
					if sq[x][y] == '#':
						cntb += 1
					visited[x][y] = 1
					for (n_x, n_y) in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
						if 0 <= n_x < h and 0 <= n_y < w:
							if visited[n_x][n_y] != 1 and prt[n_x][n_y] == prt[x][y]:
								que.append((n_x, n_y))
			ans += cntb * (cnt - cntb)
print(ans)


(H, W) = map(int, input().split())
s_list = []
for i in range(H):
	s_list.append(input())
check = [[False for _ in range(W)] for _ in range(H)]
move_x = [1, 0, -1, 0]
move_y = [0, 1, 0, -1]
import sys
sys.setrecursionlimit(10 ** 9)

def dfs(i, j):
	check[i][j] = True
	if s_list[i][j] == '#':
		cnt[0] += 1
	else:
		cnt[1] += 1
	for m in range(4):
		next_i = i + move_y[m]
		next_j = j + move_x[m]
		if 0 <= next_i < H and 0 <= next_j < W and (s_list[i][j] != s_list[next_i][next_j]) and (not check[next_i][next_j]):
			dfs(next_i, next_j)
ans = 0
for i in range(H):
	for j in range(W):
		cnt = [0] * 2
		dfs(i, j)
		ans += cnt[0] * cnt[1]
print(ans)


dxdy = [(0, 1), (0, -1), (1, 0), (-1, 0)]
(h, w) = map(int, input().split())
s = [list(input()) for _ in range(h)]
for i in range(h):
	for j in range(w):
		if (i + j) % 2:
			if s[i][j] == '.':
				s[i][j] = '#'
			else:
				s[i][j] = '.'
d = [[True] * w for _ in range(h)]
ans = 0
for i in range(h):
	for j in range(w):
		if not d[i][j]:
			continue
		d[i][j] = False
		st = [(i, j)]
		(b, wh) = (0, 0)
		while st:
			(y, x) = st.pop()
			if (x + y) % 2:
				b += 1
			else:
				wh += 1
			for (dx, dy) in dxdy:
				if 0 <= x + dx < w and 0 <= y + dy < h and d[y + dy][x + dx] and (s[y][x] == s[y + dy][x + dx]):
					st.append((y + dy, x + dx))
					d[y + dy][x + dx] = False
		ans += b * wh
print(ans)


import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline
(H, W) = map(int, input().split())
S = []
for i in [0] * H:
	l = input()
	S.append([1 if x == '#' else -1 for x in l])
bk = 0
wh = 0

def check(S, x, y):
	global bk, wh
	n = S[y][x]
	if n == 0:
		return
	elif n == 1:
		bk += 1
	elif n == -1:
		wh += 1
	S[y][x] = 0
	if 0 < y and S[y - 1][x] == -n:
		check(S, x, y - 1)
	if 0 < x and S[y][x - 1] == -n:
		check(S, x - 1, y)
	if y < H - 1 and S[y + 1][x] == -n:
		check(S, x, y + 1)
	if x < W - 1 and S[y][x + 1] == -n:
		check(S, x + 1, y)
	return
cnt = 0
for y in range(H):
	for x in range(W):
		if S[y][x] == 1:
			check(S, x, y)
			cnt += wh * bk
			wh = 0
			bk = 0
print(cnt)


from itertools import product
(H, W) = map(int, input().split())
s = [input() for _ in range(H)]
visited = [[0] * W for _ in range(H)]
ans = 0
for (y, x) in product(range(H), range(W)):
	if visited[y][x]:
		continue
	visited[y][x] = 1
	(w, b) = (0, 0)
	if s[y][x] == '#':
		b += 1
	else:
		w += 1
	stack = [(y, x)]
	while stack:
		(cy, cx) = stack.pop()
		for (dy, dx) in ((cy + 1, cx), (cy - 1, cx), (cy, cx + 1), (cy, cx - 1)):
			if not (0 <= dy < H and 0 <= dx < W) or visited[dy][dx] or s[cy][cx] == s[dy][dx]:
				continue
			visited[dy][dx] = 1
			if s[dy][dx] == '#':
				b += 1
			else:
				w += 1
			stack.append((dy, dx))
	ans += w * b
print(ans)


from collections import deque
(H, W) = map(int, input().split())
index = '.#'.index
S = [list(map(index, input())) for i in range(H)]
dd = ((-1, 0), (0, -1), (1, 0), (0, 1))
used = [[0] * W for i in range(H)]
ans = 0
for i in range(H):
	for j in range(W):
		if used[i][j]:
			continue
		que = deque([(i, j)])
		used[i][j] = 1
		C = [0, 0]
		C[S[i][j]] += 1
		f = i + j & 1 ^ S[i][j]
		while que:
			(x, y) = que.popleft()
			s = x + y & 1 ^ 1
			for (dx, dy) in dd:
				nx = x + dx
				ny = y + dy
				if not 0 <= nx < H or not 0 <= ny < W or used[nx][ny] or (s ^ S[nx][ny] != f):
					continue
				que.append((nx, ny))
				used[nx][ny] = 1
				C[S[nx][ny]] += 1
		ans += C[0] * C[1]
print(ans)


(H, W) = map(int, input().split())
S = [list(input()) for _ in range(H)]
check = [[0] * W for _ in range(H)]
ans = 0
move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
for h in range(H):
	for w in range(W):
		if check[h][w] == 1:
			continue
		black = 0
		white = 0
		stack = [[h, w]]
		check[h][w] = 1
		if S[h][w] == '#':
			black += 1
		elif S[h][w] == '.':
			white += 1
		while len(stack) != 0:
			(x, y) = stack.pop()
			tmp = S[x][y]
			for (dx, dy) in move:
				nx = x + dx
				ny = y + dy
				if 0 <= nx < H and 0 <= ny < W and (tmp != S[nx][ny]) and (check[nx][ny] == 0):
					check[nx][ny] = 1
					stack.append([nx, ny])
					if S[nx][ny] == '#':
						black += 1
					elif S[nx][ny] == '.':
						white += 1
		ans += black * white
print(ans)


import sys
sys.setrecursionlimit(10 ** 9)
(h, w) = map(int, input().split())
b = [[0] * (w + 1)]
for i in range(h):
	b.append([0])
	for j in input():
		if j == '.':
			b[-1].append(1)
		else:
			b[-1].append(2)
	b[-1].append(0)
b.append([0] * (w + 1))
d = [[0, 1], [0, -1], [1, 0], [-1, 0]]
a = 0

def s(i, j):
	global B
	B[b[i][j] - 1] += 1
	v = b[i][j]
	b[i][j] = 0
	for k in d:
		if v ^ 3 != b[i + k[0]][j + k[1]]:
			continue
		s(i + k[0], j + k[1])
for i in range(1, h + 1):
	for j in range(1, w + 1):
		B = [0, 0]
		s(i, j)
		a += B[0] * B[1]
print(a)


from collections import deque
(h, w) = map(int, input().split())
s = [list(input()) for i in range(h)]
q = deque()
ans = 0

def bfs(i, j):
	global ans
	white = 0
	black = 0
	q.append((i, j))
	while q:
		(y, x) = q.popleft()
		if s[y][x] == '#':
			black += 1
		if s[y][x] == '.':
			white += 1
		for (dy, dx) in ((1, 0), (0, 1), (-1, 0), (0, -1)):
			ny = y + dy
			nx = x + dx
			if 0 <= ny < h and 0 <= nx < w and (s[y][x] != s[ny][nx]) and (field[ny][nx] == False):
				field[ny][nx] = True
				q.append((ny, nx))
	ans += black * white
field = [[False] * w for j in range(h)]
for i in range(h):
	for j in range(w):
		if s[i][j] == '.' and field[i][j] == False:
			field[i][j] = True
			bfs(i, j)
print(ans)


(H, W) = map(int, input().split())
M = [list(input()) for _ in range(H)]
used = [[False for _ in range(W)] for __ in range(H)]

def dfs(sx, sy):
	global used
	if used[sy][sx]:
		return (0, 0)
	black = white = 0
	stack = [(sx, sy)]
	used[sy][sx] = True
	while stack:
		(x, y) = stack.pop()
		if M[y][x] == '#':
			black += 1
		else:
			white += 1
		for (dx, dy) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
			(nx, ny) = (x + dx, y + dy)
			if 0 <= nx < W and 0 <= ny < H and (not used[ny][nx]):
				if M[y][x] != M[ny][nx]:
					stack.append((nx, ny))
					used[ny][nx] = True
	return (black, white)
ans = 0
for y in range(H):
	for x in range(W):
		(black, white) = dfs(x, y)
		ans += black * white
print(ans)


(H, W) = map(int, input().split())
S = [[c == '.#'[(i + j) % 2] for (j, c) in enumerate(input())] for i in range(H)]
V = [[-1] * W for _ in [0] * H]
ans = 0
for si in range(H):
	for sj in range(W):
		if V[si][sj] != -1:
			continue
		V[si][sj] = 0
		cnt = [0, 0]
		cnt[(S[si][sj] + si + sj) % 2] += 1
		q = [[si, sj]]
		while q:
			(i, j) = q.pop()
			for (di, dj) in ((1, 0), (-1, 0), (0, 1), (0, -1)):
				if not 0 <= i + di < H or not 0 <= j + dj < W:
					continue
				if V[i + di][j + dj] != -1:
					continue
				if S[i][j] != S[i + di][j + dj]:
					continue
				V[i + di][j + dj] = V[i][j]
				q.append([i + di, j + dj])
				cnt[(S[i][j] + i + di + j + dj) % 2] += 1
		ans += cnt[0] * cnt[1]
print(ans)


from collections import deque
(H, W) = map(int, input().split())
S = []
for i in range(H):
	s = input()
	temp = []
	for j in range(W):
		temp.append(s[j])
	S.append(temp)
ret = 0
for i in range(H):
	for j in range(W):
		if S[i][j] != '?':
			q = deque()
			q.appendleft((i, j))
			white = 0
			black = 0
			while q:
				(h, w) = q.pop()
				color = S[h][w]
				if color == '?':
					continue
				elif color == '#':
					black += 1
				else:
					white += 1
				S[h][w] = '?'
				cand = [(h + 1, w), (h - 1, w), (h, w + 1), (h, w - 1)]
				for (hc, wc) in cand:
					if 0 <= hc < H and 0 <= wc < W and (S[hc][wc] not in [color, '?']):
						q.appendleft((hc, wc))
			ret += black * white
print(ret)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
(h, w) = map(int, input().split())
n = h * w
fld = ''.join([input().rstrip() for _ in range(h)])
edges = [set() for _ in range(n)]

def to_v(i, j):
	return i * w + j
for i in range(h):
	for j in range(w):
		v = to_v(i, j)
		dirc = [(-1, 0), (0, 1), (1, 0), (0, -1)]
		for (di, dj) in dirc:
			(x, y) = (i + di, j + dj)
			if x < 0 or h <= x or y < 0 or (w <= y):
				continue
			v2 = to_v(x, y)
			if fld[v] != fld[v2]:
				edges[v].add(v2)
				edges[v2].add(v)

def dfs(v, c=0):
	if visited[v]:
		return
	visited[v] = 1
	cnt[c] += 1
	for v2 in edges[v]:
		dfs(v2, c ^ 1)
visited = [0] * n
ans = 0
for v in range(n):
	if visited[v]:
		continue
	cnt = [0, 0]
	dfs(v)
	ans += cnt[0] * cnt[1]
print(ans)


from collections import deque
(h, w) = map(int, input().split())
p = ['-' * (w + 2)]
for i in range(h):
	p.append('-' + input() + '-')
p.append('-' * (w + 2))
isl = []
v = [[0 for i in range(w + 2)] for j in range(h + 2)]
d = [[0, 1], [1, 0], [-1, 0], [0, -1]]

def bfs(x, y):
	if v[x][y] != 0:
		return
	q = deque()
	q.append((x, y))
	v[x][y] = 1
	(br, wh) = (0, 0)
	cnt = 0
	while len(q) > 0:
		(ch, cw) = q.popleft()
		if p[ch][cw] == '#':
			br += 1
			for (dh, dw) in d:
				if p[ch + dh][cw + dw] == '.' and v[ch + dh][cw + dw] == 0:
					q.append((ch + dh, cw + dw))
					v[ch + dh][cw + dw] = 1
		elif p[ch][cw] == '.':
			wh += 1
			for (dh, dw) in d:
				if p[ch + dh][cw + dw] == '#' and v[ch + dh][cw + dw] == 0:
					q.append((ch + dh, cw + dw))
					v[ch + dh][cw + dw] = 1
	isl.append((br, wh))
for i in range(1, h + 1):
	for j in range(1, w + 1):
		bfs(i, j)
ans = 0
for (br, wh) in isl:
	ans += br * wh
print(ans)


from collections import deque
(H, W) = map(int, input().split())
inl = [input() for _ in range(H)]
checked = set([])
lis = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def bfs(i, j):
	fifo = deque([])
	fifo.append((i, j))
	checked.add((i, j))
	cntBlack = 0
	cntWhite = 0
	while fifo:
		(i, j) = fifo.popleft()
		if inl[i][j] == '.':
			cntWhite += 1
		else:
			cntBlack += 1
		for (di, dj) in lis:
			if i + di >= 0 and i + di < H and (j + dj >= 0) and (j + dj < W) and (not (i + di, j + dj) in checked) and (inl[i][j] != inl[i + di][j + dj]):
				checked.add((i + di, j + dj))
				fifo.append((i + di, j + dj))
	return cntBlack * cntWhite
res = 0
for i in range(H):
	for j in range(W):
		if not (i, j) in checked:
			res += bfs(i, j)
print(res)


import sys
sys.setrecursionlimit(1000000)
move = ((1, 0), (0, 1), (-1, 0), (0, -1))

def dfs(used, mat, node, nums):
	(y, x) = node
	color = mat[y][x]
	if used[y][x] == 1 or color == '!':
		return
	used[y][x] = 1
	nums[color] += 1
	for (i, j) in move:
		if mat[y + i][x + j] != color and mat[y + i][x + j] != '!':
			dfs(used, mat, (y + i, x + j), nums)
(H, W) = list(map(int, input().split()))
grid = ['!' * (W + 2)]
used = [[0 for _ in range(W + 2)] for _ in range(H + 2)]
for i in range(H):
	grid.append('!' + input() + '!')
grid.append('!' * (W + 2))
ans = 0
for i in range(H + 2):
	for j in range(W + 2):
		nums = {'#': 0, '.': 0}
		dfs(used, grid, (i, j), nums)
		ans += nums['#'] * nums['.']
print(ans)


from sys import setrecursionlimit
setrecursionlimit(10 ** 9)
(H, W) = [int(i) for i in input().split()]
S = [[j for j in input()] for i in range(H)]
INF = int(1000000000000.0)

def dfs(h, w, p):
	b_cnt = 0
	w_cnt = 0
	if h < 0 or h >= H or w < 0 or (w >= W):
		return (0, 0)
	if S[h][w] == p or S[h][w] == 'x':
		return (0, 0)
	if S[h][w] == '#':
		b_cnt += 1
	elif S[h][w] == '.':
		w_cnt += 1
	t = S[h][w]
	S[h][w] = 'x'
	for (dh, dw) in ((0, 1), (0, -1), (1, 0), (-1, 0)):
		res = dfs(h + dh, w + dw, t)
		b_cnt += res[0]
		w_cnt += res[1]
	return (b_cnt, w_cnt)
ans = 0
for h in range(H):
	for w in range(W):
		if S[h][w] == '#':
			(b_cnt, w_cnt) = dfs(h, w, '.')
			ans += b_cnt * w_cnt
print(ans)


def find(x):
	if x == Tree[x]:
		return x
	else:
		Tree[x] = find(Tree[x])
		return Tree[x]

def unite(x, y):
	s1 = find(x)
	s2 = find(y)
	if s1 != s2:
		Tree[s2] = s1
		size[s1][0] += size[s2][0]
		size[s1][1] += size[s2][1]
(H, W) = map(int, input().split())
Tree = [i for i in range(H * W)]
S = []
size = [[0, 0] for i in range(H * W)]
for i in range(H):
	S.append(input())
	for j in range(W):
		t = i * W + j
		if S[-1][j] == '.':
			size[t][0] = 1
		else:
			size[t][1] = 1
for i in range(1, W):
	if S[0][i] != S[0][i - 1]:
		unite(i, i - 1)
for i in range(1, H):
	if S[i][0] != S[i - 1][0]:
		unite(i * W, (i - 1) * W)
for i in range(1, H):
	for j in range(1, W):
		if S[i][j] != S[i][j - 1]:
			t = i * W + j
			unite(t, t - 1)
		if S[i][j] != S[i - 1][j]:
			t = i * W + j
			unite(t, t - W)
ans = 0
for i in range(H * W):
	if i == Tree[i]:
		ans += size[i][0] * size[i][1]
print(ans)


from collections import deque, defaultdict
(H, W) = map(int, input().split())
S = [input() for i in range(H)]
visited = [[False] * W for i in range(H)]
ans = 0
for i in range(H):
	for j in range(W):
		if visited[i][j]:
			continue
		q = deque()
		q.append((i, j))
		visited[i][j] = True
		n = defaultdict(int)
		while len(q) > 0:
			(si, sj) = q.popleft()
			n[S[si][sj]] += 1
			for (di, dj) in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
				if 0 <= si + di < H and 0 <= sj + dj < W and (S[si][sj] != S[si + di][sj + dj]) and (not visited[si + di][sj + dj]):
					q.append((si + di, sj + dj))
					visited[si + di][sj + dj] = True
		ans += n['#'] * n['.']
print(ans)


from collections import deque
(h, w) = map(int, input().split())
grid = [input() for _ in range(h)]
visited = [[0] * w for _ in range(h)]
moves = ((1, 0), (-1, 0), (0, 1), (0, -1))
ans = 0
for i in range(h):
	for j in range(w):
		if not visited[i][j]:
			(bcnt, wcnt) = (0, 0)
			q = deque([(i, j)])
			while q:
				(cx, cy) = q.popleft()
				if visited[cx][cy]:
					continue
				if grid[cx][cy] == '#':
					bcnt += 1
				else:
					wcnt += 1
				visited[cx][cy] = 1
				for (dx, dy) in moves:
					if 0 <= cx + dx < h and 0 <= cy + dy < w and (not visited[cx + dx][cy + dy]) and (grid[cx + dx][cy + dy] != grid[cx][cy]):
						q.append((cx + dx, cy + dy))
			ans += bcnt * wcnt
print(ans)


import sys
sys.setrecursionlimit(10 ** 6)
(H, W) = map(int, input().split())
S = [input() for i in range(H)]
visited = [[0] * W for i in range(H)]

def dfs(y, x):
	(b, w) = (0, 0)
	if S[y][x] == '#':
		b += 1
	else:
		w += 1
	for (dy, dx) in ((0, 1), (1, 0), (0, -1), (-1, 0)):
		(ny, nx) = (y + dy, x + dx)
		if ny < 0 or ny >= H or nx < 0 or (nx >= W):
			continue
		if S[y][x] == S[ny][nx] or visited[ny][nx]:
			continue
		visited[ny][nx] = 1
		(n, m) = dfs(ny, nx)
		b += n
		w += m
	return (b, w)
ans = 0
for i in range(H):
	for j in range(W):
		if not visited[i][j]:
			visited[i][j] = 1
			(b, w) = dfs(i, j)
			ans += b * w
print(ans)


from collections import defaultdict as dd
(H, W) = map(int, input().split())
S = [input() for _ in range(H)]
i = 0
color = []
edge = dd(lambda : dd(int))
for h in range(H):
	for w in range(W):
		color.append(S[h][w])
		if w != 0:
			j = i - 1
			if S[h][w - 1] != S[h][w]:
				edge[i][j] = 1
				edge[j][i] = 1
		if h != 0:
			j = i - W
			if S[h - 1][w] != S[h][w]:
				edge[i][j] = 1
				edge[j][i] = 1
		i += 1
visited = [False] * i
ans = 0
for k in range(i):
	if not visited[k]:
		count = {'#': 0, '.': 0}
		queue = set([k])
		while queue:
			j = queue.pop()
			count[color[j]] += 1
			visited[j] = True
			for dst in edge[j]:
				if not visited[dst]:
					queue.add(dst)
		ans += count['#'] * count['.']
print(ans)


from collections import deque
(H, W) = map(int, input().split())
S = [input() for i in range(H)]
ans = 0
flag = [[0] * W for i in range(H)]
for i in range(H * W):
	(x, y) = (i % W, i // W)
	if flag[y][x] == 1:
		continue
	flag[y][x] = 1
	bw = [0, 0]
	bw[['.', '#'].index(S[y][x])] += 1
	queue = deque([[x, y]])
	while queue:
		(x, y) = queue.popleft()
		for (a, b) in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
			if 0 <= x + a < W and 0 <= y + b < H and (flag[y + b][x + a] == 0) and (S[y][x] != S[y + b][x + a]):
				queue.append([x + a, y + b])
				flag[y + b][x + a] = 1
				bw[['.', '#'].index(S[y + b][x + a])] += 1
	ans += bw[0] * bw[1]
print(ans)


(H, W) = map(int, input().split())
S = [0] * (H + 2)
S[0] = '*' * (W + 2)
S[H + 1] = '*' * (W + 2)
for h in range(1, H + 1):
	S[h] = '*' + input() + '*'
import sys
sys.setrecursionlimit(10 ** 8)
bw = ['#', '.']
visited = [[False] * (W + 2) for h in range(H + 2)]
ans = 0
dh = [0, 1, 0, -1]
dw = [1, 0, -1, 0]

def dfs(h, w, c):
	for i in range(4):
		h0 = h + dh[i]
		w0 = w + dw[i]
		if S[h0][w0] == bw[c ^ 1] and visited[h0][w0] == False:
			visited[h0][w0] = True
			bw_count[c ^ 1] += 1
			dfs(h0, w0, c ^ 1)
for h in range(H + 2):
	for w in range(W + 2):
		if S[h][w] == '#' and visited[h][w] == False:
			bw_count = [1, 0]
			visited[h][w] = True
			dfs(h, w, 0)
			ans += bw_count[0] * bw_count[1]
print(ans)


(h, w) = map(int, input().split())
s = []
for _ in range(h):
	s.append(input())
num = [[-1] * w for _ in range(h)]
stack = []

def dfs():
	while stack:
		r = stack.pop()
		for x in ((1, 0), (-1, 0), (0, 1), (0, -1)):
			(a, b, c, d) = (r[0], r[1], x[0], x[1])
			if 0 <= a + c < h and 0 <= b + d < w:
				if s[a + c][b + d] != s[a][b] and num[a + c][b + d] == -1:
					num[a + c][b + d] = num[a][b]
					stack.append((a + c, b + d))
color = 0
for i in range(h):
	for j in range(w):
		if num[i][j] == -1:
			stack.append((i, j))
			num[i][j] = color
			dfs()
			color += 1
color_num = [[0, 0] for _ in range(color)]
for i in range(h):
	for j in range(w):
		if s[i][j] == '.':
			color_num[num[i][j]][0] += 1
		else:
			color_num[num[i][j]][1] += 1
ans = 0
for x in color_num:
	ans += x[0] * x[1]
print(ans)


import sys
sys.setrecursionlimit(10 ** 7)
(h, w) = map(int, input().split())
s = [input() for i in range(h)]
t = [[None] * w for i in range(h)]
d = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def dfs(i, j, bw):
	global h, w
	if not (0 <= i < h and 0 <= j < w) or s[i][j] == bw or t[i][j]:
		return (0, 0)
	t[i][j] = True
	(W, b) = (0, 0)
	if s[i][j] == '#':
		b += 1
	else:
		W += 1
	for k in d:
		(n, m) = dfs(i + k[0], j + k[1], s[i][j])
		W += n
		b += m
	return (W, b)
ans = 0
for i in range(h):
	for j in range(w):
		(X, Y) = dfs(i, j, 'u shi ta pu ni chi a ku n wara')
		ans += X * Y
print(ans)


(H, W) = map(int, input().split())
S = [input() for _ in range(H)]
ans = 0
visited = [[0] * W for _ in range(H)]
stack = []
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
for i in range(H):
	for j in range(W):
		(b, w) = (0, 0)
		if not visited[i][j]:
			stack.append([i, j])
			visited[i][j] = 1
			while stack:
				(x, y) = stack.pop()
				if S[x][y] == '#':
					b += 1
				else:
					w += 1
				for k in range(4):
					(nx, ny) = (x + dx[k], y + dy[k])
					if not (0 <= nx < H and 0 <= ny < W):
						continue
					if not visited[nx][ny] and S[x][y] != S[nx][ny]:
						visited[nx][ny] = 1
						stack.append([nx, ny])
			ans += b * w
print(ans)


from collections import deque
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def dfs(x, y):
	stack = deque()
	stack.append((x, y))
	num_w = 0
	num_b = 0
	while stack:
		(cx, cy) = stack.popleft()
		cc = S[cy][cx]
		for (i, j) in zip(dx, dy):
			nx = i + cx
			ny = j + cy
			if (0 <= nx < w and 0 <= ny < h) and (not visited[ny][nx]) and (S[ny][nx] != cc):
				visited[ny][nx] = True
				stack.append((nx, ny))
				if cc == '.':
					num_w += 1
				else:
					num_b += 1
	else:
		return (num_w, num_b)
(h, w) = map(int, input().split())
S = [list(input()) for _ in range(h)]
visited = [[False] * w for _ in range(h)]
ans = 0
for i in range(w):
	for j in range(h):
		if not visited[j][i]:
			(num_w, num_b) = dfs(i, j)
			ans += num_b * num_w
print(ans)


import sys
sys.setrecursionlimit(1000000)
(h, w) = map(int, input().split())
s = [input() for _ in range(h)]
t = [[None] * w for _ in range(h)]

def dfs(i, j, color):
	if not (0 <= i < h and 0 <= j < w):
		return (0, 0)
	if s[i][j] == color:
		return (0, 0)
	if t[i][j]:
		return (0, 0)
	t[i][j] = True
	(wh, bl) = (0, 0)
	if s[i][j] == '#':
		bl += 1
	else:
		wh += 1
	(tmp1, tmp2) = dfs(i + 1, j, s[i][j])
	(wh, bl) = (wh + tmp1, bl + tmp2)
	(tmp1, tmp2) = dfs(i - 1, j, s[i][j])
	(wh, bl) = (wh + tmp1, bl + tmp2)
	(tmp1, tmp2) = dfs(i, j - 1, s[i][j])
	(wh, bl) = (wh + tmp1, bl + tmp2)
	(tmp1, tmp2) = dfs(i, j + 1, s[i][j])
	(wh, bl) = (wh + tmp1, bl + tmp2)
	return (wh, bl)
ans = 0
for i in range(h):
	for j in range(w):
		(a, b) = dfs(i, j, '!')
		ans += a * b
print(ans)


from collections import deque
(H, W) = map(int, input().split())
S = []
for i in range(H):
	S.append(input())
q = deque([])
T = []
seen = [[0] * W for _ in range(H)]
step = [[0, 1], [0, -1], [1, 0], [-1, 0]]
for h in range(H):
	for w in range(W):
		temp = []
		if seen[h][w] == 0:
			temp.append(S[h][w])
			seen[h][w] = 1
			q.append([h, w, S[h][w]])
			while q:
				(oh, ow, m) = q.popleft()
				for (dh, dw) in step:
					if 0 <= oh + dh < H and 0 <= ow + dw < W:
						if seen[oh + dh][ow + dw] == 0 and m != S[oh + dh][ow + dw]:
							temp.append(S[oh + dh][ow + dw])
							seen[oh + dh][ow + dw] = 1
							q.append([oh + dh, ow + dw, S[oh + dh][ow + dw]])
			T.append(temp)
ans = 0
for i in range(len(T)):
	black = 0
	white = 0
	for s in T[i]:
		if s == '#':
			black += 1
		else:
			white += 1
	ans += black * white
print(ans)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
from collections import deque
(h, w) = map(int, input().split())
s = [input() for _ in range(h)]
memo = [[0] * w for _ in range(h)]
dir = [(0, 1), (0, -1), (1, 0), (-1, 0)]

def dfs(i, j, color):
	if not (0 <= i <= h - 1 and 0 <= j <= w - 1):
		return (0, 0)
	if memo[i][j] == 1:
		return (0, 0)
	if s[i][j] == color:
		return (0, 0)
	memo[i][j] = 1
	(white, black) = (0, 0)
	if s[i][j] == '.':
		white += 1
	else:
		black += 1
	for (dx, dy) in dir:
		(cur_w, cur_b) = dfs(i + dx, j + dy, s[i][j])
		white += cur_w
		black += cur_b
	return (white, black)
ans = 0
for i in range(h):
	for j in range(w):
		if s[i][j] == '.':
			(white, black) = dfs(i, j, '#')
		else:
			(white, black) = dfs(i, j, '.')
		ans += white * black
print(ans)


import sys
sys.setrecursionlimit(10 ** 6)
(H, W) = map(int, input().split())
S = [input() for _ in range(H)]
check = [[0] * W for _ in range(H)]
di = [-1, 0, 1, 0]
dj = [0, -1, 0, 1]
(black, white) = (0, 0)

def dfs(i, j):
	global check, black, white
	if check[i][j]:
		return
	else:
		check[i][j] = 1
	if S[i][j] == '#':
		black += 1
	else:
		white += 1
	for dir in range(4):
		ni = i + di[dir]
		nj = j + dj[dir]
		if ni < 0 or ni >= H or nj < 0 or (nj >= W):
			continue
		if S[i][j] == S[ni][nj]:
			continue
		dfs(ni, nj)
	return
ans = 0
for i in range(H):
	for j in range(W):
		(black, white) = (0, 0)
		dfs(i, j)
		ans += black * white
print(ans)


import sys
sys.setrecursionlimit(10 ** 7)
(h, w) = [int(item) for item in input().split()]
field = []
for i in range(h):
	field.append(input().rstrip())
black = 0
white = 0
visited = [[0] * w for _ in range(h)]

def dfs(is_black, i, j):
	global black
	global white
	visited[i][j] = 1
	for (x, y) in [[1, 0], [0, 1], [0, -1], [-1, 0]]:
		if i + x < 0 or i + x >= h or j + y < 0 or (j + y >= w):
			continue
		if visited[i + x][j + y] != 0:
			continue
		if is_black:
			if field[i + x][j + y] == '.':
				white += 1
				dfs(False, i + x, j + y)
		if not is_black:
			if field[i + x][j + y] == '#':
				black += 1
				dfs(True, i + x, j + y)
ans = 0
for i in range(h):
	for j in range(w):
		if visited[i][j] != 0:
			continue
		if field[i][j] == '#':
			white = 0
			black = 1
			dfs(True, i, j)
		else:
			white = 1
			black = 0
			dfs(False, i, j)
		ans += white * black
print(ans)


import itertools
(h, w) = map(int, input().split())
s = [input() for _ in range(h)]
diffs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
t = [[0] * w for _ in range(h)]
group = 1
for (i, j) in itertools.product(range(h), range(w)):
	if t[i][j] != 0:
		continue
	stack = [(i, j)]
	while stack:
		(x, y) = stack.pop()
		t[x][y] = group
		for (dx, dy) in diffs:
			nx = x + dx
			ny = y + dy
			if 0 <= nx < h and 0 <= ny < w and (t[nx][ny] == 0) and (s[x][y] != s[nx][ny]):
				stack.append((nx, ny))
	group += 1
d = [[0] * 2 for _ in range(group)]
for (i, j) in itertools.product(range(h), range(w)):
	d[t[i][j]][0 if s[i][j] == '.' else 1] += 1
ans = sum((d[i][0] * d[i][1] for i in range(len(d))))
print(ans)


from collections import deque
(dx, dy) = ([1, 0, -1, 0], [0, 1, 0, -1])
(H, W) = map(int, input().split())
seen = [[False] * W for _ in range(H)]
(c, S) = (0, [])
for _ in range(H):
	S.append(input())
for i in range(H):
	for j in range(W):
		if S[i][j] == '#' and (not seen[i][j]):
			d = deque()
			d.append((i, j))
			(seen[i][j], b, w) = (True, 1, 0)
			while d:
				(px, py) = d.popleft()
				for (x, y) in zip(dx, dy):
					(nx, ny) = (px + x, py + y)
					if nx < 0 or ny < 0 or nx >= H or (ny >= W) or seen[nx][ny]:
						continue
					if S[px][py] == '#' and S[nx][ny] == '.':
						d.append((nx, ny))
						seen[nx][ny] = 1
						w += 1
					elif S[px][py] == '.' and S[nx][ny] == '#':
						d.append((nx, ny))
						seen[nx][ny] = 1
						b += 1
			c += b * w
print(c)


from collections import deque
(h, w) = map(int, input().split())
s = [list(input()) for i in range(h)]
used = [[0] * w for i in range(h)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
ans = 0
for i in range(h):
	for j in range(w):
		if used[i][j]:
			continue
		cw = 0
		cb = 0
		q = deque([])
		q.append([i, j])
		used[i][j] = 1
		while q:
			(x, y) = q.popleft()
			if s[x][y] == '#':
				cb += 1
			else:
				cw += 1
			for k in range(4):
				nx = x + dx[k]
				ny = y + dy[k]
				if 0 <= nx < h and 0 <= ny < w:
					if not used[nx][ny] and s[x][y] != s[nx][ny]:
						used[nx][ny] = 1
						q.append([nx, ny])
		ans += cw * cb
print(ans)


from collections import deque

def bfs(y, x):
	global s
	global fl
	global h
	global w
	global ans
	dx = [0, 1, 0, -1]
	dy = [1, 0, -1, 0]
	count = 1
	black = 0
	d = deque()
	d.append([y, x])
	fl[y][x] = 1
	if s[y][x] == '#':
		black += 1
	while len(d):
		p = d.pop()
		for k in range(4):
			if 0 <= p[1] + dx[k] < w and 0 <= p[0] + dy[k] < h and (s[p[0]][p[1]] != s[p[0] + dy[k]][p[1] + dx[k]]):
				if fl[p[0] + dy[k]][p[1] + dx[k]]:
					continue
				d.append([p[0] + dy[k], p[1] + dx[k]])
				count += 1
				fl[p[0] + dy[k]][p[1] + dx[k]] = 1
				if s[p[0] + dy[k]][p[1] + dx[k]] == '#':
					black += 1
	ans += black * (count - black)
(h, w) = map(int, input().split())
s = [input() for i in range(h)]
fl = [[0 for _ in range(w)] for _ in range(h)]
ans = 0
for i in range(h):
	for j in range(w):
		if not fl[i][j]:
			bfs(i, j)
print(ans)


import sys
sys.setrecursionlimit(2 * 10 ** 5)
(H, W) = map(int, input().split())
s = [input() for _ in range(H)]
ans = 0
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
un_reached = [[True for i in range(W)] for j in range(H)]

def dfs(x, y):
	un_reached[x][y] = False
	if s[x][y] == '#':
		cc[1] += 1
	else:
		cc[0] += 1
	for i in range(4):
		nx = x + dx[i]
		ny = y + dy[i]
		if 0 <= nx < H and 0 <= ny < W and (s[nx][ny] != s[x][y]) and un_reached[nx][ny]:
			dfs(nx, ny)
for i in range(H):
	for j in range(W):
		if un_reached[i][j]:
			cc = [0 for _ in range(2)]
			dfs(i, j)
			ans += cc[1] * cc[0]
print(ans)


def aising19_c():
	from collections import deque
	(h, w) = (int(x) for x in input().split())
	color = [[s == '#' for s in str(input())] for _ in range(h)]
	used = [[False] * w for _ in range(h)]
	ans = 0
	for i in range(h):
		for j in range(w):
			if used[i][j]:
				continue
			(bk, wt) = (0, 0)
			que = deque()
			used[i][j] = True
			que.append((i, j))
			while que:
				(ci, cj) = que.popleft()
				if color[ci][cj]:
					bk += 1
				else:
					wt += 1
				for (di, dj) in ((-1, 0), (0, -1), (0, 1), (1, 0)):
					(ni, nj) = (ci + di, cj + dj)
					if ni < 0 or h <= ni or nj < 0 or (w <= nj):
						continue
					if color[ci][cj] == color[ni][nj]:
						continue
					if used[ni][nj]:
						continue
					used[ni][nj] = True
					que.append((ni, nj))
			ans += bk * wt
	print(ans)
aising19_c()


(H, W) = map(int, input().split())
C = [input() for i in range(H)]
import sys
sys.setrecursionlimit(500000)
itta = [[0] * W for i in range(H)]

def search(x, y, z):
	if y >= H or x >= W or x < 0 or (y < 0):
		return
	elif C[y][x] == z:
		return
	elif itta[y][x] == 1:
		return
	elif C[y][x] == z:
		return
	else:
		itta[y][x] = 1
		if C[y][x] == '.':
			bw_count[0] += 1
		else:
			bw_count[1] += 1
		prez = C[y][x]
	search(x + 1, y, prez)
	search(x - 1, y, prez)
	search(x, y + 1, prez)
	search(x, y - 1, prez)
ans = 0
for y in range(H):
	for x in range(W):
		if itta[y][x] == 1:
			pass
		else:
			bw_count = [0, 0]
			search(x, y, '-')
			ans += bw_count[0] * bw_count[1]
print(ans)


(H, W) = map(int, input().split())
fields = [list(input()) for i in range(H)]
seen = [[False] * W for i in range(H)]
mv = [(0, 1), (0, -1), (1, 0), (-1, 0)]
from collections import deque
from collections import defaultdict
ans = 0
for i in range(H):
	for j in range(W):
		if seen[i][j]:
			continue
		d = defaultdict(int)
		q = deque()
		q.append((i, j))
		while len(q) > 0:
			(h, w) = q.popleft()
			s = fields[h][w]
			for (dh, dw) in mv:
				if 0 <= h + dh < H and 0 <= w + dw < W:
					if seen[h + dh][w + dw]:
						continue
					t = fields[h + dh][w + dw]
					if t == s:
						continue
					d[s] += 1
					q.append((h + dh, w + dw))
					seen[h + dh][w + dw] = True
		ans += d['#'] * d['.']
print(ans)


f = lambda x: x if p[x] < 0 else f(p[x])

def u(x, y):
	(x, y) = (f(x), f(y))
	if x != y:
		if p[x] > p[y]:
			(x, y) = (y, x)
		p[x] += p[y]
		p[y] = x
(h, *s) = open(0)
(h, w) = map(int, h.split())
r = range(h * w)
p = [-1] * h * w
for i in r:
	(j, k) = (i // w, i % w)
	h > j + 1 and s[j][k] != s[j + 1][k] and u(i, i + w) or (w > k + 1 and s[j][k] != s[j][k + 1] and u(i, i + 1))
d = [[0, 0] for _ in r]
for i in r:
	d[f(i)][s[i // w][i % w] < '.'] += 1
print(sum((i * j for (i, j) in d)))


from collections import deque
(H, W) = map(int, input().split())
S = [input() for _ in range(H)]
visited = [[False] * W for _ in range(H)]
ans = 0
for si in range(H):
	for sj in range(W):
		if visited[si][sj]:
			continue
		visited[si][sj] = True
		queue = deque()
		queue.append((si, sj))
		black = 0
		white = 0
		while queue:
			(i, j) = queue.popleft()
			if S[i][j] == '#':
				black += 1
			else:
				white += 1
			for (di, dj) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
				(ni, nj) = (i + di, j + dj)
				if 0 <= ni < H and 0 <= nj < W and (not visited[ni][nj]) and (S[i][j] != S[ni][nj]):
					visited[ni][nj] = True
					queue.append((ni, nj))
		ans += black * white
print(ans)


(H, W) = map(int, input().split())
grid = [-1] * (W + 4) * 2
black_ind = []
for _ in range(H):
	grid += [-1] * 2
	I = input()
	for i in range(W):
		if I[i] == '#':
			grid.append(1)
			black_ind.append(len(grid) - 1)
		else:
			grid.append(0)
	grid += [-1] * 2
grid += [-1] * (W + 4) * 2
move = [1, -1, W + 4, -(W + 4)]
ans = 0
for b in black_ind:
	if grid[b] == 2:
		continue
	cnt_b = 1
	cnt_w = 0
	q = [b]
	grid[b] = 2
	while q:
		cp = q.pop()
		if grid[cp] == 2:
			for d in move:
				if grid[cp + d] == 0:
					grid[cp + d] = 3
					cnt_w += 1
					q.append(cp + d)
		elif grid[cp] == 3:
			for d in move:
				if grid[cp + d] == 1:
					grid[cp + d] = 2
					cnt_b += 1
					q.append(cp + d)
	ans += cnt_b * cnt_w
print(ans)


from collections import deque
(H, W) = [int(_) for _ in input().split()]
S = [input() for _ in range(H)]
di = (1, 0, -1, 0)
dj = (0, 1, 0, -1)
visited = [[False] * W for _ in range(H)]
result = 0
for i in range(H):
	for j in range(W):
		if visited[i][j]:
			continue
		visited[i][j] = True
		(b, w) = (0, 0)
		que = deque([(i, j)])
		while que:
			(ci, cj) = que.pop()
			if S[ci][cj] == '#':
				b += 1
			else:
				w += 1
			for d in range(4):
				(ni, nj) = (ci + di[d], cj + dj[d])
				if not (0 <= ni < H and 0 <= nj < W):
					continue
				if S[ci][cj] == S[ni][nj]:
					continue
				if visited[ni][nj]:
					continue
				visited[ni][nj] = True
				que.append((ni, nj))
		result += b * w
print(result)


def dfs(sx: int, sy: int) -> None:
	color = [0] * 2
	s_col = S[sx][sy]
	color[s_col] += 1
	S[sx][sy] = 2
	stack = [(sx, sy, s_col)]
	while stack:
		(x, y, col) = stack.pop()
		for (dx, dy) in dxy:
			(nx, ny) = (x + dx, y + dy)
			if 0 <= nx < H and 0 <= ny < W and (S[nx][ny] == col ^ 1):
				stack.append((nx, ny, S[nx][ny]))
				color[S[nx][ny]] += 1
				S[nx][ny] = 2
	return color[0] * color[1]

def main():
	global H, W, S, dxy, blk, wht
	(H, W, *S) = open(0).read().split()
	(H, W) = (int(H), int(W))
	S = [[1 if i == '#' else 0 for i in s] for s in S]
	dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
	ans = 0
	for i in range(H):
		for j in range(W):
			if S[i][j] != 2:
				ans += dfs(i, j)
	print(ans)
main()


from collections import deque
dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]
(H, W) = map(int, input().split())
a = [[None for _ in range(W)] for _ in range(H)]
reached = [[False for _ in range(W)] for _ in range(H)]
for r in range(H):
	s = input()
	for c in range(W):
		a[r][c] = s[c] == '#'
ans = 0
for r in range(H):
	for c in range(W):
		if reached[r][c]:
			continue
		reached[r][c] = True
		b = 0
		w = 0
		dq = deque()
		dq.append((r, c))
		while dq:
			(rr, cc) = dq.popleft()
			if a[rr][cc]:
				b += 1
			else:
				w += 1
			for di in range(4):
				nr = rr + dr[di]
				if not 0 <= nr < H:
					continue
				nc = cc + dc[di]
				if not 0 <= nc < W:
					continue
				if a[rr][cc] == a[nr][nc]:
					continue
				if reached[nr][nc]:
					continue
				reached[nr][nc] = True
				dq.append((nr, nc))
		ans += b * w
print(ans)


import itertools
(H, W) = [int(_) for _ in input().split()]
S = [input() for _ in range(H)]
A = [[0 for _ in range(W)] for _ in range(H)]

def dfs(p, q):
	if A[p][q] == 1:
		return 0
	count = {'#': 0, '.': 0}
	stack = [[p, q]]
	while stack:
		(x, y) = stack.pop()
		if A[x][y] != 1:
			count[S[x][y]] += 1
			A[x][y] = 1
			dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]
			for (dx, dy) in dxy:
				(nx, ny) = (x + dx, y + dy)
				if 0 <= nx < H and 0 <= ny < W and (S[x][y] != S[nx][ny]):
					stack += [[nx, ny]]
	return count['#'] * count['.']
print(sum([dfs(i, j) for (i, j) in itertools.product(range(H), range(W))]))


import sys
sys.setrecursionlimit(10 ** 7)
(h, w) = map(int, input().split())
s = [list(input()) for _ in range(h)]
visited = [[False] * w for _ in range(h)]

def dfs(y, x):
	visited[y][x] = True
	(blk, wht) = (0, 0)
	for (dy, dx) in zip((-1, 1, 0, 0), (0, 0, -1, 1)):
		(ny, nx) = (y + dy, x + dx)
		if not 0 <= ny < h or not 0 <= nx < w or visited[ny][nx]:
			continue
		if s[y][x] != s[ny][nx]:
			(nb, nw) = dfs(ny, nx)
			blk += nb
			wht += nw
	if s[y][x] == '#':
		blk += 1
	else:
		wht += 1
	return (blk, wht)
ans = 0
for i in range(h):
	for j in range(w):
		if not visited[i][j]:
			(blk, wht) = dfs(i, j)
			ans += blk * wht
print(ans)


(h, w) = map(int, input().split())
S = [[1 if i == '#' else 0 for i in input()] for _ in range(h)]
dy = (1, 0, -1, 0)
dx = (0, 1, 0, -1)
seen = [[False] * w for _ in range(h)]

def dfs(y, x):
	white = 0
	black = 0
	stack = [(y, x)]
	seen[y][x] = True
	while stack:
		(s, t) = stack.pop()
		if S[s][t]:
			black += 1
		else:
			white += 1
		for (di, dj) in zip(dy, dx):
			(ny, nx) = (s + di, t + dj)
			if 0 <= ny < h and 0 <= nx < w:
				if seen[ny][nx]:
					continue
				if S[s][t] ^ S[ny][nx]:
					seen[ny][nx] = True
					stack.append((ny, nx))
	return (black, white)
ans = 0
for i in range(h):
	for j in range(w):
		if not seen[i][j]:
			(black, white) = dfs(i, j)
			ans += black * white
print(ans)


from collections import deque
(h, w) = map(int, input().split())
field = [['*' for i in range(w + 2)]] + [['*'] + list(input()) + ['*'] for i in range(h)] + [['*'] * (w + 2)]
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
visited = [[False for i in range(w + 2)] for j in range(h + 2)]
s = {'#': 0, '.': 1}
ans = 0

def bfs(a, b):
	if visited[a][b] or field[a][b] == '*':
		return 0
	D = deque([(a, b)])
	visited[a][b] = True
	cnt = [0, 0]
	while D:
		pos = D.popleft()
		cnt[s[field[pos[0]][pos[1]]]] += 1
		for (i, j) in zip(dx, dy):
			if field[pos[0] + i][pos[1] + j] == '*' or visited[pos[0] + i][pos[1] + j] or field[pos[0] + i][pos[1] + j] == field[pos[0]][pos[1]]:
				continue
			visited[pos[0] + i][pos[1] + j] = True
			D.append((pos[0] + i, pos[1] + j))
	return cnt[0] * cnt[1]
for i in range(h + 2):
	for j in range(w + 2):
		ans += bfs(i, j)
print(ans)


(H, W) = map(int, input().split())
h = range(H)
w = range(W)
S = [input() for _ in h]
M = [[-1] * W for _ in h]
k = 0
for y in h:
	for x in w:
		if M[y][x] != -1:
			continue
		M[y][x] = k
		Q = [(y, x)]
		while len(Q) > 0:
			(i, j) = Q.pop()
			s = S[i][j]
			p = i + 1
			q = i - 1
			r = j + 1
			t = j - 1
			if p < H and M[p][j] == -1 and (s != S[p][j]):
				M[p][j] = k
				Q += [(p, j)]
			if i > 0 and M[q][j] == -1 and (s != S[q][j]):
				M[q][j] = k
				Q += [(q, j)]
			if r < W and M[i][r] == -1 and (s != S[i][r]):
				M[i][r] = k
				Q += [(i, r)]
			if j > 0 and M[i][t] == -1 and (s != S[i][t]):
				M[i][t] = k
				Q += [(i, t)]
		k += 1
s = {}
d = {}
for i in h:
	for j in w:
		m = M[i][j]
		if S[i][j] == '#':
			s[m] = s.get(m, 0) + 1
		else:
			d[m] = d.get(m, 0) + 1
print(sum((s.get(i, 0) * d.get(i, 0) for i in range(k))))


import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
(H, W) = map(int, input().split())
S = [input() for _ in range(H)]
seen = [[False for _ in range(W)] for _ in range(H)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
numb = 0
numw = 0

def dfs(y, x):
	global numb
	global numw
	seen[y][x] = True
	if S[y][x] == '#':
		numb += 1
	if S[y][x] == '.':
		numw += 1
	for i in range(4):
		if not 0 <= y + dy[i] < H or not 0 <= x + dx[i] < W:
			continue
		if seen[y + dy[i]][x + dx[i]]:
			continue
		if S[y][x] == S[y + dy[i]][x + dx[i]]:
			continue
		dfs(y + dy[i], x + dx[i])
ans = 0
for i in range(H):
	for j in range(W):
		numb = 0
		numw = 0
		if S[i][j] == '#' and (not seen[i][j]):
			dfs(i, j)
			ans += numb * numw
print(ans)


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')
from collections import defaultdict
(rows, cols) = map(int, input().split())
n = rows * cols
ns = defaultdict(set)
ss = [None] * rows
color = [None] * n
for i in range(rows):
	s = input()
	ss[i] = s
	for (j, c) in enumerate(s):
		u = i * cols + j
		color[u] = c
		if i > 0:
			if c != ss[i - 1][j]:
				v = u - cols
				ns[u].add(v)
				ns[v].add(u)
		if j > 0:
			if c != s[j - 1]:
				v = u - 1
				ns[u].add(v)
				ns[v].add(u)
seen = [False] * n
ans = 0
for u in range(n):
	if seen[u]:
		continue
	q = [u]
	s = set([u])
	while q:
		u = q.pop()
		for v in ns[u]:
			if seen[v]:
				continue
			seen[v] = True
			s.add(v)
			q.append(v)
	ans += sum((color[item] == '#' for item in s)) * sum((color[item] == '.' for item in s))
print(ans)


import sys
input = sys.stdin.readline
from collections import deque
(h, w) = map(int, input().split())
s = [input() for _ in range(h)]
memo = [[0] * w for _ in range(h)]
dir = [(0, 1), (0, -1), (1, 0), (-1, 0)]
ans = 0
for i in range(h):
	for j in range(w):
		if memo[i][j] == 1:
			continue
		memo[i][j] = 1
		black = 0
		white = 0
		if s[i][j] == '.':
			white += 1
		else:
			black += 1
		q = deque([(i, j)])
		while q:
			(x, y) = q.popleft()
			for (dx, dy) in dir:
				if not (0 <= x + dx <= h - 1 and 0 <= y + dy <= w - 1):
					continue
				if memo[x + dx][y + dy] == 0 and s[x][y] != s[x + dx][y + dy]:
					memo[x + dx][y + dy] = 1
					if s[x + dx][y + dy] == '.':
						white += 1
					else:
						black += 1
					q.append((x + dx, y + dy))
		ans += black * white
print(ans)


from collections import deque
(H, W) = map(int, input().split())
S = []
for _ in range(H):
	S.append(list(input()))
ans = 0
for h in range(H):
	for w in range(W):
		if S[h][w] == 'x':
			continue
		q = deque()
		q.append((h, w))
		shw = S[h][w]
		bl = wh = 0
		while len(q):
			(i, j) = q.popleft()
			if not 0 <= i < H or not 0 <= j < W:
				continue
			if S[i][j] == 'x':
				continue
			dist = i + j - h - w
			if dist % 2 == 0 and shw != S[i][j]:
				continue
			if dist % 2 == 1 and shw == S[i][j]:
				continue
			if S[i][j] == '#':
				bl += 1
			else:
				wh += 1
			S[i][j] = 'x'
			q.append((i - 1, j))
			q.append((i + 1, j))
			q.append((i, j - 1))
			q.append((i, j + 1))
		ans += bl * wh
print(ans)


from collections import deque
(H, W) = list(map(int, input().split()))
Sn = [input() for _ in range(H)]

def func(h, w):
	move = [(0, -1), (-1, 0), (0, 1), (1, 0)]
	w_cnt = 0
	b_cnt = 0
	que = deque()
	que.append((h, w))
	while len(que) > 0:
		(xh, xw) = que.popleft()
		if visited[xh][xw] == 0:
			visited[xh][xw] = 1
			if Sn[xh][xw] == '#':
				b_cnt += 1
			else:
				w_cnt += 1
		else:
			continue
		for (mh, mw) in move:
			if 0 <= xh + mh < H and 0 <= xw + mw < W:
				if Sn[xh][xw] != Sn[xh + mh][xw + mw] and visited[xh + mh][xw + mw] == 0:
					que.append((xh + mh, xw + mw))
	return (b_cnt, w_cnt)
cnt = 0
visited = [[0 for _ in range(W)] for _ in range(H)]
for i in range(H):
	for j in range(W):
		if Sn[i][j] == '#' and visited[i][j] == 0:
			(b_cnt, w_cnt) = func(i, j)
			cnt += b_cnt * w_cnt
print(cnt)


from sys import setrecursionlimit

def dfs(i, j, c):
	visited[i][j] = 1
	current.append((i, j))
	for (di, dj) in ((1, 0), (-1, 0), (0, 1), (0, -1)):
		(ni, nj) = (i + di, j + dj)
		if not (0 <= ni < H and 0 <= nj < W and (not visited[ni][nj])):
			continue
		if S[ni][nj] == c:
			continue
		dfs(ni, nj, not c)
setrecursionlimit(2 * 10 ** 5)
(H, W) = map(int, input().split())
S = [[c == '#' for c in input()] for _ in range(H)]
ans = 0
visited = [[0] * W for _ in range(H)]
for i in range(H):
	for j in range(W):
		if S[i][j] and (not visited[i][j]):
			current = []
			dfs(i, j, True)
			(b, w) = (0, 0)
			for (k, l) in current:
				if S[k][l]:
					b += 1
				else:
					w += 1
			ans += b * w
print(ans)


(H, W) = map(int, input().split())
S = []
for i in range(H):
	ss = input()
	S.append(ss)
UF = list(range(H * W))

def par(m):
	if UF[m] == m:
		return m
	r = par(UF[m])
	UF[m] = r
	return r

def unite(m, n):
	i = par(m)
	j = par(n)
	UF[i] = j
for i in range(H):
	for j in range(W):
		if i + 1 < H and S[i][j] != S[i + 1][j]:
			unite(i * W + j, (i + 1) * W + j)
		if j + 1 < W and S[i][j] != S[i][j + 1]:
			unite(i * W + j, i * W + j + 1)
nsb = [0] * (H * W)
nsw = [0] * (H * W)
for i in range(H):
	for j in range(W):
		p = par(i * W + j)
		if S[i][j] == '#':
			nsb[p] += 1
		if S[i][j] == '.':
			nsw[p] += 1
r = 0
for p in range(H * W):
	r += nsb[p] * nsw[p]
print(r)


(h, w) = list(map(int, input().split()))
sss = ['x' * (w + 2)] + list(('x' + input() + 'x' for _ in range(h))) + ['x' * (w + 2)]
checked = [[False] * (w + 2) for _ in range(h + 2)]
ans = 0
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def dfs(i, j):
	(w_cnt, b_cnt) = (0, 0)
	q = [(i, j, sss[i][j] == '.')]
	while q:
		(y, x, is_white) = q.pop()
		if checked[y][x]:
			continue
		checked[y][x] = True
		if is_white:
			w_cnt += 1
		else:
			b_cnt += 1
		for (di, dj) in move:
			ni = y + di
			nj = x + dj
			if checked[ni][nj]:
				continue
			nc = sss[ni][nj]
			if nc == 'x':
				continue
			elif (nc == '.') == is_white:
				continue
			else:
				q.append((ni, nj, nc == '.'))
	return w_cnt * b_cnt
for i in range(1, h + 1):
	for j in range(1, w + 1):
		if checked[i][j]:
			continue
		ans += dfs(i, j)
print(ans)


(h, w) = map(int, input().split())
s = [list(input()) for _ in range(h)]
check = [[0] * w for _ in range(h)]
move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
ans = 0
for i in range(h):
	for j in range(w):
		if check[i][j] == 1:
			continue
		(black, white) = (0, 0)
		stack = [[i, j]]
		check[i][j] = 1
		if s[i][j] == '#':
			black += 1
		else:
			white += 1
		while len(stack) > 0:
			(x, y) = stack.pop()
			tmp = s[x][y]
			for (dx, dy) in move:
				(nx, ny) = (x + dx, y + dy)
				if 0 <= nx < h and 0 <= ny < w and (tmp != s[nx][ny]) and (check[nx][ny] == 0):
					stack.append([nx, ny])
					check[nx][ny] = 1
					if s[nx][ny] == '#':
						black += 1
					else:
						white += 1
		ans += black * white
print(ans)


import sys
readline = sys.stdin.readline
(H, W) = map(int, readline().split())
grid = [readline().rstrip() for i in range(H)]
visited = set()
ans = 0
from collections import deque
cases = ((0, 1), (0, -1), (1, 0), (-1, 0))
for i in range(H):
	for j in range(W):
		if (i, j) in visited:
			continue
		if grid[i][j] == '.':
			continue
		q = deque()
		black = 0
		white = 0
		q.append([i, j, 1])
		aim = '.#'
		while q:
			(y, x, isblack) = q.popleft()
			if (y, x) in visited:
				continue
			if aim[isblack] != grid[y][x]:
				continue
			visited.add((y, x))
			if isblack:
				black += 1
			else:
				white += 1
			isblack ^= 1
			for c in cases:
				if 0 <= y + c[0] < H and 0 <= x + c[1] < W:
					q.append([y + c[0], x + c[1], isblack])
		ans += black * white
print(ans)


from collections import deque
(h, w) = map(int, input().split())
G = [['@'] * (w + 2) for i in range(h + 2)]
for i in range(1, h + 1):
	G[i] = ['@'] + list(input()) + ['@']
V = [[0] * (w + 2) for i in range(h + 2)]
X = deque([])
Y = deque([])
XX = [-1, 0, 0, 1]
YY = [0, -1, 1, 0]
ans = 0
for i in range(h + 2):
	for j in range(w + 2):
		if V[i][j] == 0 and G[i][j] == '#':
			X.append(i)
			Y.append(j)
			V[i][j] = 1
			C = [1, 0]
			while len(X) > 0:
				x = X[0]
				y = Y[0]
				X.popleft()
				Y.popleft()
				if G[x][y] == '#':
					for k in range(4):
						if V[x + XX[k]][y + YY[k]] == 0 and G[x + XX[k]][y + YY[k]] == '.':
							X.append(x + XX[k])
							Y.append(y + YY[k])
							V[x + XX[k]][y + YY[k]] = 1
							C[1] += 1
				else:
					for k in range(4):
						if V[x + XX[k]][y + YY[k]] == 0 and G[x + XX[k]][y + YY[k]] == '#':
							X.append(x + XX[k])
							Y.append(y + YY[k])
							V[x + XX[k]][y + YY[k]] = 1
							C[0] += 1
			ans = ans + C[0] * C[1]
print(ans)


(h, w) = map(int, input().split())
grid = [[1 if i == '#' else 0 for i in input()] for _ in range(h)]
seen = [[0] * w for _ in range(h)]
DX = (0, 1, 0, -1)
DY = (1, 0, -1, 0)
ans = 0

def dfs(X, Y, cnt):
	todo = [(X, Y)]
	seen[X][Y] = cnt
	black = 0
	white = 1
	while todo:
		(x, y) = todo.pop()
		now = grid[x][y]
		for (dx, dy) in zip(DX, DY):
			nx = x + dx
			ny = y + dy
			if nx < 0 or ny < 0 or nx >= h or (ny >= w):
				continue
			if seen[nx][ny] == cnt or now == grid[nx][ny]:
				continue
			if 1 - now:
				black += 1
			else:
				white += 1
			seen[nx][ny] = cnt
			todo.append((nx, ny))
	return black * white
cnt = 1
for i in range(h):
	for j in range(w):
		if grid[i][j] or seen[i][j]:
			continue
		ans += dfs(i, j, cnt)
		cnt += 1
print(ans)


from collections import deque
(h, w) = (int(i) for i in input().split())
maze = [input() for _ in range(h)]
visited = [[False] * w for _ in range(h)]

def solve2(i, j):
	d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
	queue = deque([(i, j)])
	(b, c) = (0, 0)
	while queue:
		(x, y) = queue.popleft()
		if maze[x][y] == '#':
			b += 1
		else:
			c += 1
		visited[x][y] = True
		for (dx, dy) in d:
			(nx, ny) = (x + dx, y + dy)
			if nx <= -1 or nx >= h or ny <= -1 or (ny >= w):
				continue
			if visited[nx][ny]:
				continue
			if maze[nx][ny] != maze[x][y]:
				visited[nx][ny] = True
				queue.append([nx, ny])
	return b * c
ans = 0
for i in range(h):
	for j in range(w):
		if not visited[i][j]:
			ans += solve2(i, j)
print(ans)


import sys
sys.setrecursionlimit(1000000)
(H, W) = map(int, input().split())
S = []
for i in range(H):
	S.append(input())

def DFS(h, w, black, white, m):
	(black, white) = BorW(h, w, black, white)
	step = [[0, 1], [0, -1], [1, 0], [-1, 0]]
	seen[h][w] = 1
	for (dh, dw) in step:
		nh = h + dh
		nw = w + dw
		if 0 <= nh < H and 0 <= nw < W:
			if seen[nh][nw] == 0 and m != S[nh][nw]:
				seen[nh][nw] = 1
				(black, white) = DFS(nh, nw, black, white, S[nh][nw])
	return (black, white)

def BorW(h, w, black, white):
	if S[h][w] == '#':
		black += 1
	else:
		white += 1
	return (black, white)
seen = [[0] * W for _ in range(H)]
L = []
for h in range(H):
	for w in range(W):
		black = 0
		white = 0
		if seen[h][w] == 0:
			(black, white) = DFS(h, w, black, white, S[h][w])
			L.append([black, white])
ans = 0
for (b, w) in L:
	ans += b * w
print(ans)


from collections import deque
(H, W) = map(int, input().split())
S = []
for _ in [0] * H:
	S.append(list(input().rstrip()))
visited = []
for _ in [0] * H:
	visited.append([False] * W)
delta = [[1, 0], [0, 1], [-1, 0], [0, -1]]
ans = 0
for x in range(H):
	for y in range(W):
		if visited[x][y]:
			continue
		b = 0
		w = 0
		queue = deque()
		queue.append([x, y])
		visited[x][y] = True
		while len(queue) is not 0:
			(px, py) = queue[0]
			queue.popleft()
			if S[px][py] == '#':
				b += 1
			else:
				w += 1
			found = False
			for (dx, dy) in delta:
				nx = px + dx
				ny = py + dy
				if 0 <= nx < H and 0 <= ny < W and (not visited[nx][ny]):
					if S[px][py] != S[nx][ny]:
						found = True
						visited[nx][ny] = True
						queue.append([nx, ny])
		ans += b * w
print(ans)


import sys
sys.setrecursionlimit(100000000)

def trace(i, j, S, col, num_color):
	next_col = 1 - col
	num_color[col] += 1
	S[i][j] = 2
	if S[i - 1][j] == next_col:
		trace(i - 1, j, S, next_col, num_color)
	if S[i][j - 1] == next_col:
		trace(i, j - 1, S, next_col, num_color)
	if S[i + 1][j] == next_col:
		trace(i + 1, j, S, next_col, num_color)
	if S[i][j + 1] == next_col:
		trace(i, j + 1, S, next_col, num_color)
	return num_color[0] * num_color[1]

def main():
	(H, W) = map(int, input().split())
	S = [[2] * (W + 2)]
	for _ in range(H):
		S.append([2] + [0 if s == '#' else 1 for s in input()] + [2])
	S.append([2] * (W + 2))
	num_comb = 0
	for i in range(1, H + 1):
		for j in range(1, W + 1):
			if S[i][j] == 0:
				num_color = [0, 0]
				num_comb += trace(i, j, S, 0, num_color)
	print(num_comb)
main()


import sys
sys.setrecursionlimit(10 ** 7)
(H, W) = map(int, input().split())
F = [list(input()) for _ in range(H)]
move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
seen = [[0] * W for _ in range(H)]

def dfs(sy, sx):
	seen[sy][sx] = 1
	(b, w) = (1, 0)
	for (dy, dx) in move:
		ny = sy + dy
		nx = sx + dx
		if 0 <= ny < H and 0 <= nx < W and (F[ny][nx] != F[sy][sx]) and (not seen[ny][nx]):
			p = dfs(ny, nx)
			b += p[1]
			w += p[0]
	return (b, w)
count = 0
for i in range(H):
	for j in range(W):
		if not seen[i][j]:
			(b, w) = dfs(i, j)
			count += b * w
print(count)


(h, w) = map(int, input().split())
s = [input() for i in range(h)]
visited = [[0] * w for i in range(h)]
ans = 0
for i in range(h):
	for j in range(w):
		black = 0
		white = 0
		stack = [[i, j]]
		while stack:
			(a, b) = stack.pop()
			if visited[a][b] != 1:
				visited[a][b] += 1
				if s[a][b] == '#':
					black += 1
				else:
					white += 1
				for (x, y) in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
					c = a + y
					d = b + x
					if 0 <= c < h and 0 <= d < w:
						if s[a][b] != s[c][d]:
							stack.append([c, d])
		ans += black * white
print(ans)


import sys
sys.setrecursionlimit(10 ** 7)
(H, W) = map(int, input().split())
M = [list(input()) for _ in range(H)]
seen = [[False for _ in range(W)] for _ in range(H)]

def dfs(h, w, ph, pw):
	if M[h][w] == '.':
		(bc, wc) = (0, 1)
	else:
		(bc, wc) = (1, 0)
	for (dh, dw) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
		(nh, nw) = (h + dh, w + dw)
		if nh < 0 or H <= nh or nw < 0 or (W <= nw):
			continue
		if nh == ph and nw == pw:
			continue
		if seen[nh][nw]:
			continue
		if M[nh][nw] == M[h][w]:
			continue
		seen[nh][nw] = True
		(b_add, w_add) = dfs(nh, nw, h, w)
		bc += b_add
		wc += w_add
	return (bc, wc)
ans = 0
for h in range(H):
	for w in range(W):
		if seen[h][w] == False:
			seen[h][w] = True
			(b, w) = dfs(h, w, -1, -1)
			ans += b * w
print(ans)


from itertools import product
import sys
sys.setrecursionlimit(200000)
(H, W) = map(int, input().split())
S = [input() for _ in range(H)]
color = [[None] * W for _ in range(H)]
memo = [[0, 0] for _ in range(H * W + 1)]
cnt = 1

def dfs(p, c):
	(x, y) = p
	color[x][y] = c
	memo[cnt][c] += 1
	for (dx, dy) in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
		nx = x + dx
		ny = y + dy
		if 0 <= nx < H and 0 <= ny < W and (color[nx][ny] is None) and (c != (S[nx][ny] == '#')):
			dfs([nx, ny], not c)
for (i, j) in product(range(H), range(W)):
	if color[i][j] is None:
		dfs([i, j], S[i][j] == '#')
		cnt += 1
ans = 0
for i in range(H * W):
	ans += memo[i][0] * memo[i][1]
print(ans)


from collections import deque

def BFS():
	color = [['white' for _ in range(w)] for _ in range(h)]
	queue = deque([])
	ans = 0
	for i in range(h):
		for j in range(w):
			if color[i][j] == 'white' and S[i][j] == '#':
				queue.append([i, j])
				color[i][j] = 'gray'
				(black, white) = (0, 0)
				while len(queue) > 0:
					(c, d) = queue.popleft()
					if S[c][d] == '#':
						black += 1
					else:
						white += 1
					sign = '.' if S[c][d] == '#' else '#'
					for (a, b) in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
						(X, Y) = (c + a, d + b)
						if 0 <= X < h and 0 <= Y < w:
							if S[X][Y] == sign and color[X][Y] == 'white':
								color[X][Y] = 'gray'
								queue.append([X, Y])
					color[c][d] = 'black'
				ans += black * white
	return ans
(h, w) = map(int, input().split())
S = [list(input()) for _ in range(h)]
print(BFS())


import sys
sys.setrecursionlimit(200000)
(H, W) = map(int, input().split())
S = []
for i in range(H):
	S.append(input())
ans = 0
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
was = [[0 for i in range(W)] for j in range(H)]

def dfs(x, y):
	global cc
	global was
	was[x][y] = 1
	if S[x][y] == '#':
		cc[1] += 1
	else:
		cc[0] += 1
	for i in range(4):
		nx = x + dx[i]
		ny = y + dy[i]
		if nx >= 0 and ny >= 0 and (nx < H) and (ny < W) and (S[nx][ny] != S[x][y]) and (not was[nx][ny]):
			dfs(nx, ny)
for i in range(H):
	for j in range(W):
		if not was[i][j]:
			cc = [0] * 2
			dfs(i, j)
			ans += cc[1] * cc[0]
print(ans)


import sys
sys.setrecursionlimit(180000)

def dfs(i, j):
	for m in move:
		ni = i + m[0]
		nj = j + m[1]
		if ni < 0 or ni >= H or nj < 0 or (nj >= W):
			continue
		if ch[ni][nj]:
			continue
		if X[i][j] == X[ni][nj]:
			continue
		ch[ni][nj] = 1
		K[(ni + nj) % 2] += 1
		dfs(ni, nj)
(H, W) = map(int, input().split())
X = [[[0, 1][a == '#'] for a in input()] for i in range(H)]
ch = [[0] * W for _ in range(H)]
move = [[0, 1], [0, -1], [1, 0], [-1, 0]]
K = [0, 0]
ans = 0
for i in range(H):
	for j in range(W):
		if ch[i][j] > 0:
			continue
		ch[i][j] = 1
		K = [0, 0]
		K[(i + j) % 2] = 1
		dfs(i, j)
		ans += K[0] * K[1]
print(ans)


import sys
sys.setrecursionlimit(10 ** 9)
(h, w) = map(int, input().split())
board = [[int(j == '#') for j in input()] for i in range(h)]
dxdy = ((0, 1), (0, -1), (1, 0), (-1, 0))

def dfs(i, j, k, prev):
	if used[i][j] or board[i][j] == prev:
		return
	used[i][j] = 1
	k[board[i][j]] += 1
	for (dx, dy) in dxdy:
		(nx, ny) = (i + dx, j + dy)
		if 0 <= nx < h and 0 <= ny < w and (not used[nx][ny]) and (board[nx][ny] != board[i][j]):
			dfs(nx, ny, k, board[i][j])
used = [[0] * w for i in range(h)]
ans = 0
for i in range(h):
	for j in range(w):
		if used[i][j]:
			continue
		k = [0] * 2
		dfs(i, j, k, -1)
		ans += k[0] * k[1]
print(ans)


import sys
sys.setrecursionlimit(500 * 500)
(h, w) = list(map(int, input().split()))
s = [[1 if c == '#' else 0 for c in input()] for _ in range(h)]
g = [[] for _ in range(h * w)]
for i in range(w):
	for j in range(h):
		for di in [-1, 0, 1]:
			for dj in [-1, 0, 1]:
				if abs(di) + abs(dj) != 1:
					continue
				if 0 <= i + di < w and 0 <= j + dj < h:
					if s[j][i] != s[j + dj][i + di]:
						g[j * w + i].append(i + di + (j + dj) * w)
visit = [0] * (h * w)
black = [0] * (h * w)
white = [0] * (h * w)

def rec(j, i, rj, ri):
	if s[j][i]:
		black[rj * w + ri] += 1
	else:
		white[rj * w + ri] += 1
	for n in g[j * w + i]:
		if visit[n]:
			continue
		visit[n] = 1
		rec(n // w, n % w, rj, ri)
ans = 0
for i in range(w):
	for j in range(h):
		if visit[w * j + i]:
			continue
		visit[w * j + i] = 1
		rec(j, i, j, i)
		ans += black[w * j + i] * white[w * j + i]
print(ans)


import sys
sys.setrecursionlimit(200000)
(H, W) = [int(_) for _ in input().split()]
S = [input() for _ in range(H)]
move = ((1, 0), (-1, 0), (0, 1), (0, -1))
visited = [[False] * W for _ in range(H)]
(b, w) = (0, 0)

def dfs(i, j):
	global b, w
	visited[i][j] = True
	if S[i][j] == '#':
		b += 1
	else:
		w += 1
	for (di, dj) in move:
		(ni, nj) = (i + di, j + dj)
		if 0 <= ni < H and 0 <= nj < W:
			if S[i][j] != S[ni][nj] and (not visited[ni][nj]):
				dfs(ni, nj)
result = 0
for i in range(H):
	for j in range(W):
		if visited[i][j]:
			continue
		(b, w) = (0, 0)
		dfs(i, j)
		result += b * w
print(result)


from collections import deque
import sys
input = sys.stdin.readline

def C(i, j):
	p = [1, 0]
	q = deque([(i, j, '.')])
	while q:
		(x, y, c) = q.popleft()
		for (u, v) in d:
			(dx, dy) = (x + u, y + v)
			if 0 <= dx < h and 0 <= dy < w and (s[dx][dy] != c) and use[dx][dy]:
				use[dx][dy] = False
				p[s[dx][dy] == '#'] += 1
				q.append((dx, dy, s[dx][dy]))
	return p[0] * p[1]
(h, w) = map(int, input().split())
s = [input() for i in range(h)]
use = [[1] * w for i in range(h)]
d = [(0, 1), (1, 0), (0, -1), (-1, 0)]
ans = 0
for i in range(h):
	for j in range(w):
		if use[i][j] and s[i][j] == '.':
			use[i][j] = False
			ans += C(i, j)
print(ans)


(H, W) = map(int, input().split())
S = [[int(c == '#') for c in input()] for i in range(H)]
v = [[0] * W for i in range(H)]
r = 0

def bfs(p, x, y, c, b):
	while 1:
		c ^= 1
		q = set()
		for (h, w) in p:
			v[h][w] = 1
			if h > 0 and (not v[h - 1][w]) and (S[h - 1][w] == c):
				q.add((h - 1, w))
			if w > 0 and (not v[h][w - 1]) and (S[h][w - 1] == c):
				q.add((h, w - 1))
			if h < H - 1 and (not v[h + 1][w]) and (S[h + 1][w] == c):
				q.add((h + 1, w))
			if w < W - 1 and (not v[h][w + 1]) and (S[h][w + 1] == c):
				q.add((h, w + 1))
		if not q:
			return x * y
		if b:
			x += len(q)
		else:
			y += len(q)
		b ^= 1
		p = q
for h in range(H):
	for w in range(W):
		if v[h][w] == 0:
			r += bfs([(h, w)], 1, 0, S[h][w], 0)
print(r)


import sys
sys.setrecursionlimit(10 ** 9)
(H, W) = map(int, input().split())
G = [list(input()) for i in range(H)]
C = [[0] * W for i in range(H)]

def dfs(nh, nw, color):
	direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]
	C[nh][nw] = color
	for (dh, dw) in direction:
		if not (0 <= nh + dh < H and 0 <= nw + dw < W):
			continue
		if C[nh + dh][nw + dw] != 0:
			continue
		if G[nh][nw] == G[nh + dh][nw + dw]:
			continue
		C[nh + dh][nw + dw] = color
		dfs(nh + dh, nw + dw, -color)
Color = 1
for h in range(H):
	for w in range(W):
		if C[h][w] == 0:
			dfs(h, w, Color)
			Color += 1
Count = {}
for h in range(H):
	for w in range(W):
		Count[C[h][w]] = 0
		Count[-C[h][w]] = 0
for h in range(H):
	for w in range(W):
		Count[C[h][w]] += 1
ans = 0
for key in Count.keys():
	ans += Count[key] * Count[-key]
print(ans // 2)


from collections import deque
(H, W) = map(int, input().split())
X = [[[0, 1][a == '#'] for a in input()] for i in range(H)]
ch = [[0] * W for _ in range(H)]
move = [[-1, 0], [1, 0], [0, -1], [0, 1]]
ans = 0
for i in range(H):
	for j in range(W):
		if ch[i][j]:
			continue
		ch[i][j] = 1
		q = deque([[i, j]])
		a = [0, 0]
		while q:
			t = q.popleft()
			x = t[0]
			y = t[1]
			ch[x][y] = 1
			a[(x + y) % 2] += 1
			for m in move:
				nx = x + m[0]
				ny = y + m[1]
				if nx >= 0 and nx < H and (ny >= 0) and (ny < W) and (X[x][y] != X[nx][ny]):
					if ch[nx][ny] == 0:
						q.append([nx, ny])
						ch[nx][ny] = 1
		ans += a[0] * a[1]
print(ans)


import sys
sys.setrecursionlimit(1000000)
(h, w) = [int(i) for i in input().split()]
board = [input() for _ in range(h)]
used = [[0] * w for _ in range(h)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

def dfs(x, y):
	global numb, numw
	used[x][y] = 1
	if board[x][y] == '#':
		numb += 1
	else:
		numw += 1
	for i in range(4):
		nx = x + dx[i]
		ny = y + dy[i]
		if nx < 0 or nx >= h or ny < 0 or (ny >= w) or (used[nx][ny] == 1):
			continue
		if board[x][y] != board[nx][ny]:
			dfs(nx, ny)
	return
ans = 0
for i in range(h):
	for j in range(w):
		numw = 0
		numb = 0
		if used[i][j] == 1:
			continue
		dfs(i, j)
		ans += numw * numb
print(ans)


from collections import deque
(H, W) = map(int, input().split())
S = ['*' * (W + 2) for _ in range(H + 2)]
for i in range(1, H + 1):
	S[i] = '*' + input() + '*'
K = 0
T = [[0] * (W + 2) for _ in range(H + 2)]
Neighborhood = [(0, 1), (0, -1), (1, 0), (-1, 0)]
p = 0
for y in range(1, H + 1):
	for x in range(1, W + 1):
		if T[y][x] == 0:
			p += 1
			if S[y][x] == '#':
				(Black, White) = (1, 0)
			elif S[y][x] == '.':
				(Black, White) = (0, 1)
			Q = deque([(x, y)])
			T[y][x] = p
			while Q:
				(u, v) = Q.popleft()
				for (a, b) in Neighborhood:
					if S[v][u] == '#' and S[v + b][u + a] == '.' and (T[v + b][u + a] == 0):
						Q.append((u + a, v + b))
						White += 1
						T[v + b][u + a] = p
					elif S[v][u] == '.' and S[v + b][u + a] == '#' and (T[v + b][u + a] == 0):
						Q.append((u + a, v + b))
						Black += 1
						T[v + b][u + a] = p
			K += Black * White
print(K)


import sys
sys.setrecursionlimit(1000000)
(H, W) = map(int, input().split())
board = []
check = [[None] * W for i in range(H)]
answer = 0
for i in range(H):
	S = list(input())
	board.append(S)

def dfs(i, j, color):
	if not (0 <= i < H and 0 <= j < W):
		return (0, 0)
	if board[i][j] == color:
		return (0, 0)
	if check[i][j]:
		return (0, 0)
	check[i][j] = True
	(black, white) = (0, 0)
	if board[i][j] == '#':
		black += 1
	else:
		white += 1
	(tempblack, tempwhite) = dfs(i + 1, j, board[i][j])
	black += tempblack
	white += tempwhite
	(tempblack, tempwhite) = dfs(i - 1, j, board[i][j])
	black += tempblack
	white += tempwhite
	(tempblack, tempwhite) = dfs(i, j + 1, board[i][j])
	black += tempblack
	white += tempwhite
	(tempblack, tempwhite) = dfs(i, j - 1, board[i][j])
	black += tempblack
	white += tempwhite
	return (black, white)
for i in range(H):
	for j in range(W):
		(black, white) = dfs(i, j, '!')
		answer += black * white
print(answer)


import sys
sys.setrecursionlimit(10 ** 9)
(h, w) = map(int, input().split())
b = [[0] * (w + 1)]
for i in range(h):
	b.append([0])
	for j in input():
		if j == '.':
			b[-1].append(1)
		else:
			b[-1].append(2)
	b[-1].append(0)
b.append([0] * (w + 1))
d = [[0, 1], [0, -1], [1, 0], [-1, 0]]
a = 0

def bfs(i, j):
	global br, wh
	if b[i][j] == 0:
		return
	if b[i][j] == 1:
		wh += 1
	elif b[i][j] == 2:
		br += 1
	v = b[i][j]
	b[i][j] = 0
	for k in d:
		if v ^ 3 != b[i + k[0]][j + k[1]]:
			continue
		bfs(i + k[0], j + k[1])
for i in range(1, h + 1):
	for j in range(1, w + 1):
		br = wh = 0
		bfs(i, j)
		a += br * wh
print(a)


from collections import deque
(h, w) = map(int, input().split())
s = [input() for _ in range(h)]
visited = [[True] * w for _ in range(h)]

def bfs(sx, sy):
	q = deque([(sx, sy)])
	visited[sx][sy] = False
	black = 1
	white = 0
	while q:
		(x, y) = q.popleft()
		for (dx, dy) in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
			(nx, ny) = (x + dx, y + dy)
			if 0 <= nx < h and 0 <= ny < w:
				if visited[nx][ny]:
					if s[x][y] == '#' and s[nx][ny] == '.':
						visited[nx][ny] = False
						q.append((nx, ny))
						white += 1
					elif s[x][y] == '.' and s[nx][ny] == '#':
						visited[nx][ny] = False
						q.append((nx, ny))
						black += 1
	return (black, white)
ans = 0
for sx in range(h):
	for sy in range(w):
		if s[sx][sy] == '#' and visited[sx][sy]:
			(black, white) = bfs(sx, sy)
			ans += black * white
print(ans)


from collections import deque
(h, w) = map(int, input().split())
s = []
for _ in range(h):
	s.append(input())
dxdy = [(-1, 0), (0, -1), (0, 1), (1, 0)]
seen = [[False] * w for _ in range(h)]
ans = 0
for i in range(h):
	for j in range(w):
		if seen[i][j]:
			continue
		q = deque([(j, i)])
		cnt = [0, 0]
		cnt[int(s[i][j] == '#')] += 1
		seen[i][j] = True
		while q:
			(x, y) = q.popleft()
			for (dx, dy) in dxdy:
				if not (0 <= x + dx < w and 0 <= y + dy < h):
					continue
				if seen[y + dy][x + dx] or s[y][x] == s[y + dy][x + dx]:
					continue
				cnt[int(s[y + dy][x + dx] == '#')] += 1
				seen[y + dy][x + dx] = True
				q.append((x + dx, y + dy))
		ans += cnt[0] * cnt[1]
print(ans)


(h, w) = map(int, input().split())
field = [['@'] * (w + 2)] + [list('@' + input() + '@') for _ in range(h)] + [['@'] * (w + 2)]
direction = [(0, -1), (0, 1), (1, 0), (-1, 0)]
flip = {'.': '#', '#': '.'}

def count_up(i, j):
	que = [(i, j)]
	cnt = {'.': 0, '#': 0}
	while que:
		(i, j) = que.pop()
		now = field[i][j]
		field[i][j] = '@'
		fliped_chip = flip.get(now)
		if fliped_chip is not None:
			cnt[now] += 1
		for d in direction:
			(dx, dy) = d
			(nx, ny) = (j + dx, i + dy)
			next_chip = field[ny][nx]
			if next_chip == fliped_chip:
				que.append((ny, nx))
	return cnt
cnt = [[0] * w for _ in range(h)]
result = 0
for i in range(1, h + 1):
	for j in range(1, w + 1):
		dot_sharp = count_up(i, j)
		result += dot_sharp['.'] * dot_sharp['#']
print(result)


(h, w) = map(int, input().split())
s = []
for i in range(h):
	s.append(input())
import sys
sys.setrecursionlimit(200000)
dy = [0, 0, 1, -1]
dx = [1, -1, 0, 0]

def dfs(y, x):
	global check
	global was
	was[y][x] = 1
	if s[y][x] == '#':
		check[0] += 1
	else:
		check[1] += 1
	for k in range(4):
		nx = x + dx[k]
		ny = y + dy[k]
		if nx >= 0 and ny >= 0 and (nx < w) and (ny < h) and (s[ny][nx] != s[y][x]) and (not was[ny][nx]):
			dfs(ny, nx)
ans = 0
was = [[0 for i in range(w)] for j in range(h)]
for i in range(w):
	for j in range(h):
		if not was[j][i]:
			check = [0, 0]
			dfs(j, i)
			ans += check[0] * check[1]
print(ans)


from collections import deque
(H, W) = map(int, input().split())
Ss = []
for _ in range(H):
	Ss.append(input())
mp = [[0] * W for _ in range(H)]
dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]
lst = []
q = deque([])
num = 1
for i in range(H):
	for j in range(W):
		if mp[i][j] == 0:
			q.append((i, j))
			mp[i][j] = num
			dic = {'#': 0, '.': 0}
			while q:
				t = q.popleft()
				dic[Ss[t[0]][t[1]]] += 1
				for k in range(4):
					if t[0] + dxy[k][0] >= 0 and t[0] + dxy[k][0] < H and (t[1] + dxy[k][1] >= 0) and (t[1] + dxy[k][1] < W) and (Ss[t[0]][t[1]] != Ss[t[0] + dxy[k][0]][t[1] + dxy[k][1]]) and (mp[t[0] + dxy[k][0]][t[1] + dxy[k][1]] == 0):
						mp[t[0] + dxy[k][0]][t[1] + dxy[k][1]] = num
						q.append((t[0] + dxy[k][0], t[1] + dxy[k][1]))
			lst.append(dic)
			num += 1
rlt = 0
for d in lst:
	rlt += d['#'] * d['.']
print(rlt)


from collections import defaultdict

def find(tab, a):
	if tab[a] == -1:
		return a
	tab[a] = find(tab, tab[a])
	return tab[a]

def union(tab, a, b):
	(pa, pb) = (find(tab, a), find(tab, b))
	if pa != pb:
		tab[pb] = pa
(H, W) = map(int, input().split())
S = [input() for _ in range(H)]
N = H * W
tab = [-1] * N
for y in range(H):
	for x in range(W):
		for (dx, dy) in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
			xx = x + dx
			yy = y + dy
			if xx < 0 or xx >= W or yy < 0 or (yy >= H):
				continue
			src = W * y + x
			dst = W * yy + xx
			if S[y][x] != S[yy][xx]:
				union(tab, src, dst)
dic = defaultdict(lambda : {'#': 0, '.': 0})
for i in range(N):
	p = find(tab, i)
	t = S[i // W][i % W]
	dic[p][t] += 1
ans = 0
for d in dic.values():
	ans += d['#'] * d['.']
print(ans)


import sys
sys.setrecursionlimit(10 ** 6)
(h, w) = map(int, input().split())
s = [input() for _ in range(h)]
is_used = [[False] * w for _ in range(h)]
di = [+1, 0, -1, 0]
dj = [0, +1, 0, -1]

def dfs(i, j):
	if s[i][j] == '#':
		(cnt_w, cnt_b) = (0, 1)
	else:
		(cnt_w, cnt_b) = (1, 0)
	for k in range(4):
		ni = i + di[k]
		nj = j + dj[k]
		if ni < 0 or ni >= h or nj < 0 or (nj >= w):
			continue
		if is_used[ni][nj]:
			continue
		if s[i][j] == s[ni][nj]:
			continue
		is_used[ni][nj] = True
		(cw, cb) = dfs(ni, nj)
		cnt_w += cw
		cnt_b += cb
	return (cnt_w, cnt_b)
ans = 0
for i in range(h):
	for j in range(w):
		if not is_used[i][j]:
			is_used[i][j] = True
			(cnt_w, cnt_b) = dfs(i, j)
			ans += cnt_w * cnt_b
print(ans)


from itertools import chain, product
(H, W) = map(int, input().split())
grid = list(chain(([None] * (W + 2),), (list(chain((None,), map(lambda x: x == '#', input()), (None,))) for _ in range(H)), ([None] * (W + 2),)))
neighbors = ((1, 0), (0, 1), (-1, 0), (0, -1))
res = 0
stack = []
for (y, x) in product(range(1, H + 1), range(1, W + 1)):
	if grid[y][x] is None:
		continue
	stack.append((y, x))
	(black, white) = (0, 0)
	while stack:
		(y, x) = stack.pop()
		v = grid[y][x]
		if v is None:
			continue
		grid[y][x] = None
		if v:
			black += 1
		else:
			white += 1
		v = not v
		for (dy, dx) in neighbors:
			w = grid[y + dy][x + dx]
			if w == v:
				stack.append((y + dy, x + dx))
	res += black * white
print(res)


import sys
sys.setrecursionlimit(10 ** 7)
dct = {'#': 0, '.': 1, '-': 2}

def f(c):
	return dct[c]
(h, w) = map(int, input().split())
s = [[2] * (w + 2)]
for _ in range(h):
	s.append([2] + list(map(f, input())) + [2])
s.append([2] * (w + 2))
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def dfs(col, hh, ww):
	if s[hh][ww] != col:
		return
	cnt[col] += 1
	s[hh][ww] = 2
	for (dh, dw) in d:
		nh = hh + dh
		nw = ww + dw
		dfs(1 - col, nh, nw)
ans = 0
for hi in range(1, h + 1):
	for wi in range(1, w + 1):
		cnt = [0, 0]
		if s[hi][wi] != 2:
			dfs(s[hi][wi], hi, wi)
		ans += cnt[0] * cnt[1]
print(ans)


from collections import deque

def bfs(S, H, W, sh, sw):
	(black, white) = (0, 0)
	d = deque()
	d.append([sh, sw])
	if S[sh][sw] == '#':
		black += 1
	elif S[sh][sw] == '.':
		white += 1
	seen[sh][sw] = 1
	dx = [1, 0, -1, 0]
	dy = [0, 1, 0, -1]
	while len(d) != 0:
		h = d[0][0]
		w = d[0][1]
		d.popleft()
		for dir in range(4):
			nh = h + dx[dir]
			nw = w + dy[dir]
			if nh > H - 1 or nh < 0 or nw > W - 1 or (nw < 0):
				continue
			if seen[nh][nw] or S[nh][nw] == S[h][w]:
				continue
			if S[nh][nw] == '#':
				black += 1
			else:
				white += 1
			seen[nh][nw] = 1
			d.append([nh, nw])
	return (white, black)
(H, W) = map(int, input().split())
G = [list(input()) for i in range(H)]
seen = [[0] * W for i in range(H)]
ans = 0
for i in range(H):
	for j in range(W):
		if not seen[i][j]:
			(w, b) = bfs(G, H, W, i, j)
			ans += w * b
print(ans)


import sys
sys.setrecursionlimit(10 ** 9)
(H, W) = map(int, input().split())
inputs = [input() for _ in range(H)]
visited = [[False for _ in range(W)] for _ in range(H)]
vectors = [[0, -1], [-1, 0], [0, 1], [1, 0]]
ans = 0

def dfs(h, w):
	if visited[h][w]:
		return (0, 0)
	visited[h][w] = True
	if inputs[h][w] == '#':
		(black, white) = (1, 0)
	else:
		(black, white) = (0, 1)
	for vector in vectors:
		next_h = h + vector[0]
		next_w = w + vector[1]
		if not (0 <= next_h < H and 0 <= next_w < W):
			continue
		next_color = inputs[next_h][next_w]
		if inputs[h][w] != next_color:
			(p_black, p_white) = dfs(next_h, next_w)
			black += p_black
			white += p_white
	return (black, white)
for h in range(H):
	for w in range(W):
		(black, white) = dfs(h, w)
		ans += black * white
print(ans)


from sys import stdin
nii = lambda : map(int, stdin.readline().split())
lnii = lambda : list(map(int, stdin.readline().split()))
from collections import deque
(h, w) = nii()
s = [list(input()) for i in range(h)]

def BFS(sy, sx, ans):
	s[sy][sx] = 'B'
	que = deque()
	que.append((sy, sx))
	b_cnt = 1
	w_cnt = 0
	while que:
		(y, x) = que.popleft()
		for (dy, dx) in [[-1, 0], [0, -1], [1, 0], [0, 1]]:
			ny = y + dy
			nx = x + dx
			if 0 <= ny < h and 0 <= nx < w:
				if s[y][x] == 'B' and s[ny][nx] == '.':
					w_cnt += 1
					s[ny][nx] = 'W'
					que.append((ny, nx))
				if s[y][x] == 'W' and s[ny][nx] == '#':
					b_cnt += 1
					s[ny][nx] = 'B'
					que.append((ny, nx))
	ans += b_cnt * w_cnt
	return ans
ans = 0
for i in range(h):
	for j in range(w):
		if s[i][j] == '#':
			ans = BFS(i, j, ans)
print(ans)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from collections import defaultdict
(H, W) = map(int, input().split())
grid = '*' * (W + 2)
for _ in range(H):
	grid += '*' + input().rstrip() + '*'
grid += '*' * (W + 2)
move = [1, -1, W + 2, -(W + 2)]
root = [None if x == '*' else -1 for x in grid]
answer = 0
for i in range((H + 2) * (W + 2)):
	if root[i] != -1:
		continue
	q = [i]
	root[i] = i
	counter = defaultdict(int)
	while q:
		x = q.pop()
		counter[grid[x]] += 1
		for dx in move:
			y = x + dx
			if root[y] != -1:
				continue
			if grid[x] == grid[y]:
				continue
			root[y] = i
			q.append(y)
	answer += counter['.'] * counter['#']
print(answer)


(h, w) = map(int, input().split())
s = [str(input()) for i in range(h)]
dxdy = {(-1, 0), (1, 0), (0, -1), (0, 1)}
ch = [[0] * w for i in range(h)]
ans = 0
for i in range(h):
	for j in range(w):
		if ch[i][j] == 0:
			(black, white) = (0, 0)
			q = [(i, j)]
			while q:
				(y, x) = q.pop()
				if ch[y][x] == 0:
					if s[y][x] == '#':
						black += 1
					else:
						white += 1
					ch[y][x] = 1
					for (dx, dy) in dxdy:
						if 0 <= x + dx < w and 0 <= y + dy < h and (ch[y + dy][x + dx] == 0) and (s[y + dy][x + dx] != s[y][x]):
							q.append((y + dy, x + dx))
			ans += black * white
print(ans)


import sys
sys.setrecursionlimit(500 * 500)
(h, w) = map(int, input().split())
grid = []
seen = [[False for y in range(w)] for x in range(h)]
for x in range(h):
	grid.append(input())
blackSeen = 0
whiteSeen = 0

def countFrom(a, b, lastColor):
	global blackSeen, whiteSeen
	if not (0 <= a < h and 0 <= b < w):
		return
	if seen[a][b]:
		return
	thisColor = 1 if grid[a][b] == '.' else -1
	if grid[a][b] == '#' and lastColor != -1:
		blackSeen += 1
	elif grid[a][b] == '.' and lastColor != 1:
		whiteSeen += 1
	else:
		return
	seen[a][b] = True
	countFrom(a + 1, b, thisColor)
	countFrom(a - 1, b, thisColor)
	countFrom(a, b + 1, thisColor)
	countFrom(a, b - 1, thisColor)
tot = 0
for x in range(h):
	for y in range(w):
		blackSeen = 0
		whiteSeen = 0
		countFrom(x, y, 0)
		tot += blackSeen * whiteSeen
print(tot)


import sys
sys.setrecursionlimit(200000)

def dfs(x, y):
	vis[x][y] = 1
	now = s[x][y]
	b = now == '#'
	w = now == '.'
	for i in range(4):
		nx = x + dx[i]
		ny = y + dy[i]
		if not (0 <= nx < r and 0 <= ny < c) or vis[nx][ny] or s[nx][ny] == now:
			continue
		(black, white) = dfs(nx, ny)
		b += black
		w += white
	return (b, w)
(r, c) = map(int, input().split())
s = [input() for _ in range(r)]
vis = [[0] * c for _ in range(r)]
ans = 0
dx = (-1, 0, 1, 0)
dy = (0, -1, 0, 1)
for i in range(r):
	for j in range(c):
		if vis[i][j]:
			continue
		(b, w) = dfs(i, j)
		ans += b * w
print(ans)


from itertools import *
import math
from collections import *
from heapq import *
from bisect import bisect_left, bisect_right
from copy import deepcopy
inf = 10 ** 18
mod = 10 ** 9 + 7
from functools import reduce
import sys
sys.setrecursionlimit(10 ** 7)
(H, W) = map(int, input().split())
S = [input() for i in range(H)]
dirc = [(0, 1), (1, 0), (0, -1), (-1, 0)]
visited = [[False] * W for _ in range(H)]

def bfs(i, j):
	(b, w) = (0, 0)
	visited[i][j] = True
	que = deque([(i, j)])
	while que:
		(ci, cj) = que.popleft()
		if S[ci][cj] == '#':
			b += 1
		else:
			w += 1
		for (di, dj) in dirc:
			(ni, nj) = (ci + di, cj + dj)
			if not (0 <= ni < H and 0 <= nj < W) or visited[ni][nj]:
				continue
			if S[ci][cj] != S[ni][nj]:
				visited[ni][nj] = True
				que.append((ni, nj))
	return b * w
res = 0
for i in range(H):
	for j in range(W):
		if visited[i][j]:
			continue
		res += bfs(i, j)
print(res)


import sys
sys.setrecursionlimit(200000)
(H, W) = map(int, input().split())
S = []
for i in range(H):
	S.append(input())
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
used = [[False for _ in range(W)] for _ in range(H)]

def dfs(x, y):
	global nb, nw
	if S[y][x] == '#':
		nb += 1
	if S[y][x] == '.':
		nw += 1
	for i in range(4):
		nx = x + dx[i]
		ny = y + dy[i]
		if nx < 0 or nx >= W or ny < 0 or (ny >= H):
			continue
		if used[ny][nx]:
			continue
		if S[y][x] == '#' and S[ny][nx] == '#':
			continue
		if S[y][x] == '.' and S[ny][nx] == '.':
			continue
		used[ny][nx] = True
		dfs(nx, ny)
ans = 0
for i in range(H):
	for j in range(W):
		if not used[i][j]:
			used[i][j] = True
			nb = 0
			nw = 0
			dfs(j, i)
			ans += nb * nw
print(ans)


(h, w) = map(int, input().split())
a = [list('*' * (w + 2))]
for i in range(h):
	a.append(['*'] + list(input()) + ['*'])
a.append(list('*' * (w + 2)))
b = [[0] * (w + 2) for _ in range(h + 2)]
direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]
ans = 0
for i in range(1, h + 1):
	for j in range(1, w + 1):
		if a[i][j] == '#' and b[i][j] == 0:
			countw = countb = 0
			stackb = [(i, j)]
			stackw = []
			while stackb:
				(xb, yb) = stackb.pop(-1)
				if b[xb][yb] != 0:
					continue
				countb += 1
				b[xb][yb] = 1
				for d in direction:
					(p, q) = (xb + d[0], yb + d[1])
					if a[p][q] == '.' and b[p][q] == 0:
						stackw.append((p, q))
				while stackw:
					(xw, yw) = stackw.pop(-1)
					if b[xw][yw] != 0:
						continue
					countw += 1
					b[xw][yw] = 1
					for d in direction:
						(p, q) = (xw + d[0], yw + d[1])
						if a[p][q] == '#' and b[p][q] == 0:
							stackb.append((p, q))
			ans += countb * countw
print(ans)


from collections import deque
(H, W) = map(int, input().split())
s = [input() for _ in range(H)]
visited = [[False] * W for _ in range(H)]
ans = 0
for i in range(H):
	for j in range(W):
		stk = deque([(i, j)])
		visited[i][j] = True
		(black, white) = (0, 0)
		while stk:
			(y, x) = stk.popleft()
			from_ = s[y][x]
			if from_ == '.':
				white += 1
			else:
				black += 1
			for (dy, dx) in ([1, 0], [0, 1], [-1, 0], [0, -1]):
				if not (0 <= y + dy < H and 0 <= x + dx < W):
					continue
				to_ = s[y + dy][x + dx]
				if from_ == '.' and to_ == '#' or (from_ == '#' and to_ == '.'):
					if visited[y + dy][x + dx]:
						continue
					stk.append([y + dy, x + dx])
					visited[y + dy][x + dx] = True
		ans += black * white
print(ans)


(H, W) = map(int, input().split())
s = [input() for _ in range(H)]

def dfs(startx: int, starty: int) -> set:
	dxdy = [[1, 0], [-1, 0], [0, 1], [0, -1]]
	stack = [(startx, starty, s[starty][startx] == '#')]
	reached = set()
	reached.add((startx, starty))
	(b, w) = (0, 0)
	while stack:
		d = stack.pop()
		if d[2]:
			b += 1
		else:
			w += 1
		for a in dxdy:
			x = d[0] + a[0]
			y = d[1] + a[1]
			if (x, y) not in reached and 0 <= x < W and (0 <= y < H) and d[2] ^ (s[y][x] == '#'):
				stack.append((x, y, s[y][x] == '#'))
				reached.add((x, y))
	return (reached, b, w)
reach = set()
ans = 0
for i in range(H):
	for j in range(W):
		if (j, i) not in reach:
			res = dfs(j, i)
			reach |= res[0]
			ans += res[1] * res[2]
print(ans)


from collections import deque
(H, W) = map(int, input().split())
S = [input() for _ in range(H)]
flag = [[-1 for _ in range(W)] for _ in range(H)]
now = 0
for i in range(H):
	for j in range(W):
		if flag[i][j] == -1:
			stack = deque([])
			stack.append([i, j])
			flag[i][j] = now
			while len(stack) > 0:
				(y, x) = stack.popleft()
				for (nx, ny) in ([1, 0], [0, 1], [-1, 0], [0, -1]):
					if 0 <= x + nx < W and 0 <= y + ny < H:
						if S[y][x] != S[y + ny][x + nx] and flag[y + ny][x + nx] == -1:
							stack.append([y + ny, x + nx])
							flag[y + ny][x + nx] = now
			now += 1
Black = [0 for _ in range(now + 1)]
White = [0 for _ in range(now + 1)]
for i in range(H):
	for j in range(W):
		if S[i][j] == '#':
			Black[flag[i][j]] += 1
		else:
			White[flag[i][j]] += 1
res = 0
for i in range(now + 1):
	res += Black[i] * White[i]
print(res)


import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
(h, w) = map(int, readline().split())
s = read().split()
color = [[0] * w for _ in range(h)]
for i in range(h):
	for j in range(w):
		if s[i][j] == '#':
			color[i][j] = 1
ans = 0
done = [[0] * w for _ in range(h)]
for i in range(h):
	for j in range(w):
		if done[i][j] == 1:
			continue
		cnt = [0] * 2
		cnt[(i + j) % 2] += 1
		done[i][j] = 1
		stack = [(i, j)]
		while stack:
			(x, y) = stack.pop()
			for (dx, dy) in zip([-1, 1, 0, 0], [0, 0, -1, 1]):
				dx += x
				dy += y
				if (0 <= dx < h) & (0 <= dy < w):
					if done[dx][dy] == 1:
						continue
					if color[x][y] != color[dx][dy]:
						done[dx][dy] = 1
						stack.append((dx, dy))
						cnt[(dx + dy) % 2] += 1
		ans += cnt[0] * cnt[1]
print(ans)


import sys
sys.setrecursionlimit(10 ** 9)
(H, W) = map(int, input().split())
S = [input() for i in range(H)]
visited = set()

def dfs(x, y, c, white, black):
	global visited
	for (dx, dy) in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
		xx = x + dx
		yy = y + dy
		if 0 <= xx < H and 0 <= yy < W and ((xx, yy) not in visited) and (S[xx][yy] != c):
			cc = S[xx][yy]
			if cc == '.':
				white.add((xx, yy))
			else:
				black.add((xx, yy))
			visited.add((xx, yy))
			(white, black) = dfs(xx, yy, cc, white, black)
	return (white, black)
ans = 0
for x in range(H):
	for y in range(W):
		if (x, y) not in visited:
			visited.add((x, y))
			c = S[x][y]
			if c == '.':
				white = set(((x, y),))
				black = set()
			else:
				white = set()
				black = set(((x, y),))
			(white, black) = dfs(x, y, c, white, black)
			ans += len(white) * len(black)
print(ans)


import sys
sys.setrecursionlimit(10 ** 6)
(h, w) = map(int, input().split())
s = [list(input()) for _ in range(h)]
dx = (0, 0, 1, -1)
dy = (1, -1, 0, 0)
seen = [[False] * w for _ in range(h)]
numb = 0
numw = 0

def dfs(x, y):
	global numb, numw
	seen[x][y] = True
	if s[x][y] == '#':
		numb += 1
	else:
		numw += 1
	for di in range(4):
		nx = x + dx[di]
		ny = y + dy[di]
		if nx < 0 or nx >= h or ny < 0 or (ny >= w):
			continue
		if s[x][y] == s[nx][ny]:
			continue
		if seen[nx][ny]:
			continue
		dfs(nx, ny)
ans = 0
for x in range(h):
	for y in range(w):
		if seen[x][y]:
			continue
		if s[x][y] == '.':
			continue
		numb = 0
		numw = 0
		dfs(x, y)
		ans += numb * numw
print(ans)


from collections import deque
(h, w, *s) = open(0).read().split()
h = int(h)
w = int(w)
q = deque()
used = [False] * (h * w)
ans = 0
for i in range(h):
	for j in range(w):
		if not used[i * w + j]:
			bcnt = 0
			cnt = 0
			q.append((i, j))
			used[i * w + j] = True
			cnt += 1
			bcnt += s[i][j] == '#'
			while len(q):
				(y, x) = q.popleft()
				for (dy, dx) in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
					ny = y + dy
					nx = x + dx
					if 0 <= nx < w and 0 <= ny < h and (s[y][x] != s[ny][nx]) and (not used[ny * w + nx]):
						q.append((ny, nx))
						used[ny * w + nx] = True
						cnt += 1
						bcnt += s[ny][nx] == '#'
			ans += bcnt * (cnt - bcnt)
print(ans)


from collections import deque
import sys
sys.setrecursionlimit(200000)
(h, w) = map(int, input().split())
a = [[j for j in input()] for i in range(h)]
used = [[0] * w for i in range(h)]

def dfs(x, y):
	if used[x][y]:
		return 0
	global go
	used[x][y] = 1
	if x - 1 >= 0 and a[x - 1][y] != a[x][y]:
		go.add((x - 1, y))
		dfs(x - 1, y)
	if y - 1 >= 0 and a[x][y - 1] != a[x][y]:
		go.add((x, y - 1))
		dfs(x, y - 1)
	if x + 1 < h and a[x + 1][y] != a[x][y]:
		go.add((x + 1, y))
		dfs(x + 1, y)
	if y + 1 < w and a[x][y + 1] != a[x][y]:
		go.add((x, y + 1))
		dfs(x, y + 1)
ans = 0
for i in range(h):
	for j in range(w):
		go = set()
		if used[i][j]:
			continue
		dfs(i, j)
		kuro = 0
		siro = 0
		for (k, l) in go:
			if a[k][l] == '#':
				kuro += 1
			else:
				siro += 1
		ans += kuro * siro
print(ans)


(h, w) = (int(i) for i in input().split())
s = [input() for i in range(h)]
(x, v, ans) = ([[] for i in range(h * w)], [1] * (h * w), 0)
for i in range(h):
	for j in range(w):
		if i != h - 1 and s[i][j] != s[i + 1][j]:
			x[i * w + j].append((i + 1) * w + j)
			x[(i + 1) * w + j].append(i * w + j)
		if j != w - 1 and s[i][j] != s[i][j + 1]:
			x[i * w + j].append(i * w + j + 1)
			x[i * w + j + 1].append(i * w + j)
for i in range(h * w):
	if v[i]:
		(q, a, b, v[i]) = ([i], 0, 0, 0)
		while q:
			p = q.pop()
			if s[p // w][p % w] == '#':
				a += 1
			else:
				b += 1
			for j in x[p]:
				if v[j]:
					q.append(j)
					v[j] = 0
		ans += a * b
print(ans)


import sys
from sys import stdin
sys.setrecursionlimit(10 ** 7)
dx = (1, 0, -1, 0)
dy = (0, 1, 0, -1)
(H, W) = [int(_) for _ in stdin.readline().rstrip().split()]
field = [list(stdin.readline().rstrip()) for _ in range(H)]
seen = [[False for i in range(400)] for j in range(400)]
(num_b, num_w) = (0, 0)
ans = 0

def dfs(h, w):
	seen[h][w] = True
	if field[h][w] == '#':
		global num_b
		num_b += 1
	else:
		global num_w
		num_w += 1
	for direction in range(4):
		nh = h + dx[direction]
		nw = w + dy[direction]
		if nh < 0 or nh >= H or nw < 0 or (nw >= W):
			continue
		if field[nh][nw] == field[h][w]:
			continue
		if seen[nh][nw]:
			continue
		dfs(nh, nw)
for i in range(H):
	for j in range(W):
		if field[i][j] == '.':
			continue
		if seen[i][j]:
			continue
		(num_b, num_w) = (0, 0)
		dfs(i, j)
		ans += num_b * num_w
print(ans)


from collections import deque
(h, w) = map(int, input().split())
s = [input() for i in range(h)]
root = [[0, 1], [1, 0], [0, -1], [-1, 0]]

def bfs(x, y):
	v[x][y] = 1
	cnt = 1
	cnt1 = 0
	d = deque([[x, y]])
	while len(d):
		(e, f) = d.popleft()
		c = s[e][f]
		for (a, b) in root:
			x1 = e + a
			y1 = f + b
			if x1 >= 0 and x1 < h and (y1 >= 0) and (y1 < w) and (v[x1][y1] == 0):
				if c == '.' and s[x1][y1] == '#':
					v[x1][y1] = 1
					d.append([x1, y1])
					cnt += 1
				if c == '#' and s[x1][y1] == '.':
					v[x1][y1] = 1
					d.append([x1, y1])
					cnt1 += 1
	return cnt * cnt1
v = [[0 for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
	for j in range(w):
		if v[i][j]:
			continue
		if s[i][j] == '#':
			ans += bfs(i, j)
print(ans)


def root(x):
	if data[x] < 0:
		return x
	else:
		data[x] = root(data[x])
		return data[x]

def unite(x, y):
	(x, y) = (root(x), root(y))
	if x != y:
		if data[x] > data[y]:
			(x, y) = (y, x)
		data[x] += data[y]
		data[y] = x
from collections import *
r = range
(h, *s) = open(0)
(h, w) = map(int, h.split())
data = [-1] * h * w
for i in r(h):
	for j in r(w):
		if i + 1 < h and s[i][j] != s[i + 1][j]:
			unite(i * w + j, -~i * w + j)
		if j + 1 < w and s[i][j] != s[i][j + 1]:
			unite(i * w + j, i * w + j + 1)
d = defaultdict(lambda : [0, 0])
for i in r(h * w):
	d[root(i)][s[i // w][i % w] < '.'] += 1
print(sum((i * j for (i, j) in d.values())))


import sys
from collections import deque as dq
input = sys.stdin.readline
(H, W) = map(int, input().split())
S = [list(input()) for _ in range(H)]
d = [-1, 0, 1, 0]
vis = [[0] * W for _ in range(H)]
Q = dq([])
res = 0
for i in range(H):
	for j in range(W):
		if vis[i][j] == 1:
			continue
		Q.append((i, j))
		w = 0
		b = 0
		while len(Q):
			p = Q.popleft()
			if S[p[0]][p[1]] == '#':
				b += 1
			elif S[p[0]][p[1]] == '.':
				w += 1
			vis[p[0]][p[1]] = 1
			for way in range(4):
				x = p[1] + d[way]
				y = p[0] + d[-1 - way]
				if 0 <= y < H and 0 <= x < W:
					if S[p[0]][p[1]] == S[y][x]:
						continue
					if vis[y][x] == 1:
						continue
					Q.append((y, x))
					vis[y][x] = 1
		res += b * w
print(res)


from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)
(H, W) = map(int, input().split())
Map = [input() for i in range(H)]
G = [[[] for i in range(W)] for i in range(H)]
for i in range(H):
	for j in range(W):
		if i >= 1:
			if Map[i - 1][j] != Map[i][j]:
				G[i][j].append((i - 1, j))
		if j >= 1:
			if Map[i][j - 1] != Map[i][j]:
				G[i][j].append((i, j - 1))
		if i <= H - 2:
			if Map[i + 1][j] != Map[i][j]:
				G[i][j].append((i + 1, j))
		if j <= W - 2:
			if Map[i][j + 1] != Map[i][j]:
				G[i][j].append((i, j + 1))
Visited = [[False] * W for i in range(H)]

def dfs(x, y):
	(w, b) = (0, 0)
	if Visited[x][y]:
		return (0, 0)
	Visited[x][y] = True
	if Map[x][y] == '.':
		w += 1
	else:
		b += 1
	for (p, q) in G[x][y]:
		if not Visited[p][q]:
			(w_, b_) = dfs(p, q)
			w += w_
			b += b_
	return (w, b)
ans = 0
for i in range(H):
	for j in range(W):
		(p, q) = dfs(i, j)
		ans += p * q
print(ans)


from collections import defaultdict
import sys
sys.setrecursionlimit(1000000)
d = defaultdict(int)
dw = defaultdict(int)
(n, m) = map(int, input().split())
l = []
for i in range(n):
	l.append(list(input()))
lb = [[0 for i in range(m)] for j in range(n)]
move = [[1, 0], [-1, 0], [0, 1], [0, -1]]

def dfs(n1, n2, w, n3):
	if lb[n1][n2] != 0:
		return None
	else:
		lb[n1][n2] = n3
		if w == '.':
			w1 = '#'
		else:
			w1 = '.'
		for j in move:
			dx = j[0]
			dy = j[1]
			x = dx + n1
			y = dy + n2
			if 0 > x or x > n - 1 or y < 0 or (y > m - 1):
				pass
			elif w1 != l[x][y]:
				pass
			else:
				dfs(x, y, w1, n3)
		return None
dfs(0, 0, l[0][0], 1)
num = 1
for i in range(n):
	for j in range(m):
		dfs(i, j, l[i][j], num)
		num += 1
for i in range(n):
	for j in range(m):
		d[lb[i][j]] += 1
		if l[i][j] == '#':
			dw[lb[i][j]] += 1
ans = 0
for i in d:
	ans += dw[i] * (d[i] - dw[i])
print(ans)


from collections import deque
(h, w) = map(int, input().split())
s = [input() for _ in range(h)]
d_i = [-1, 0, 1, 0]
d_j = [0, -1, 0, 1]
ans = 0
visited = [[False] * w for _ in range(h)]
for i in range(h):
	for j in range(w):
		if visited[i][j]:
			continue
		b = 0
		wh = 0
		q = deque()
		q.append((i, j))
		visited[i][j] = True
		while len(q) > 0:
			(c_h, c_w) = q.pop()
			if s[c_h][c_w] == '#':
				b += 1
			else:
				wh += 1
			for dir in range(4):
				n_h = c_h + d_i[dir]
				n_w = c_w + d_j[dir]
				if n_h < 0 or h - 1 < n_h or n_w < 0 or (w - 1 < n_w):
					continue
				if visited[n_h][n_w]:
					continue
				if s[c_h][c_w] == s[n_h][n_w]:
					continue
				q.append((n_h, n_w))
				visited[n_h][n_w] = True
		ans += b * wh
print(ans)


import sys
sys.setrecursionlimit(10 ** 6)
around = [(0, 1), (1, 0), (0, -1), (-1, 0)]
(H, W) = map(int, input().split())
grid = [list(input()) for _ in range(H)]
checked = [[0] * W for _ in range(H)]

def dfs(i, j):
	checked[i][j] = 1
	for (di, dj) in around:
		ni = i + di
		nj = j + dj
		if not (0 <= ni <= H - 1 and 0 <= nj <= W - 1):
			continue
		if checked[ni][nj]:
			continue
		p = grid[i][j]
		np = grid[ni][nj]
		if (p, np) == ('.', '#'):
			global b
			b += 1
			dfs(ni, nj)
		if (p, np) == ('#', '.'):
			global w
			w += 1
			dfs(ni, nj)
ans = 0
for i in range(H):
	for j in range(W):
		b = 0
		w = 1
		if not checked[i][j] and grid[i][j] == '.':
			dfs(i, j)
		ans += b * w
print(ans)


from sys import setrecursionlimit
setrecursionlimit(200000)
(H, W) = map(int, input().split())
S = [list(input()) for _ in range(H)]
isVisited = [[False] * W for _ in range(H)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def dfs(x, y):
	isVisited[x][y] = True
	(numBlack, numWhite) = (0, 0)
	if S[x][y] == '#':
		numBlack = 1
	else:
		numWhite = 1
	for i in range(4):
		nx = x + dx[i]
		ny = y + dy[i]
		if 0 <= nx and nx < H and (0 <= ny) and (ny < W) and (not isVisited[nx][ny]):
			if S[x][y] != S[nx][ny]:
				(tmpB, tmpW) = dfs(nx, ny)
				numBlack += tmpB
				numWhite += tmpW
	return (numBlack, numWhite)
ans = 0
for i in range(H):
	for j in range(W):
		if not isVisited[i][j]:
			(numBlack, numWhite) = dfs(i, j)
			ans += numBlack * numWhite
print(ans)


def getminLT(i):
	if LT[i] == i:
		return i
	else:
		return getminLT(LT[i])
(H, W) = list(map(int, input().split()))
D = []
for i in range(H):
	D.append(input())
M = [[0] * W for i in range(H)]
LT = [0]
for i in range(H):
	for j in range(W):
		if i == 0 and j == 0:
			continue
		flag = False
		if i != 0:
			if D[i][j] != D[i - 1][j]:
				M[i][j] = M[i - 1][j]
				flag = True
		if j != 0:
			if D[i][j] != D[i][j - 1]:
				M[i][j] = M[i][j - 1]
				if flag == True:
					LT[max(getminLT(M[i - 1][j]), getminLT(M[i][j - 1]))] = LT[min(getminLT(M[i][j - 1]), getminLT(M[i - 1][j]))]
				flag = True
		if flag == False:
			M[i][j] = len(LT)
			LT.append(len(LT))
for i in range(len(LT)):
	LT[i] = getminLT(LT[i])
L = [[] for i in range(len(LT))]
for i in range(H):
	for j in range(W):
		L[LT[M[i][j]]].append((i, j))
cnt = 0
for i in L:
	E = 0
	A = 0
	for j in i:
		if (j[0] + j[1]) % 2 == 0:
			E += 1
		else:
			A += 1
	cnt += E * A
print(cnt)


import sys
sys.setrecursionlimit(10 ** 9)
(H, W) = map(int, input().split())
S = [list(input()) for _ in range(H)]
(cntblack, cntwhite) = (0, 0)
visited = [[False] * W for _ in range(H)]

def count(h, w):
	global cntblack, cntwhite
	if visited[h][w]:
		return
	visited[h][w] = True
	if S[h][w] == '.':
		cntwhite += 1
	else:
		cntblack += 1
	for (ny, nx) in ((1, 0), (0, 1), (-1, 0), (0, -1)):
		ny += h
		nx += w
		if not (0 <= ny < H and 0 <= nx < W):
			continue
		if S[ny][nx] == S[h][w]:
			continue
		count(ny, nx)
ans = 0
for h in range(H):
	for w in range(W):
		(cntblack, cntwhite) = (0, 0)
		count(h, w)
		ans += cntblack * cntwhite
print(ans)


(h, w) = map(int, input().split())
s = [input() for _i in range(h)]
visit = [[-1 for _i in range(w)] for _j in range(h)]
r = 0
from collections import deque
for i in range(h):
	for j in range(w):
		if s[i][j] == '#' and visit[i][j] < 0:
			q = deque([[i, j]])
			black = 1
			white = 0
			visit[i][j] = 1
			while q:
				(x, y) = q.popleft()
				for (n, m) in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
					if 0 <= x + n and 0 <= y + m and (x + n < h) and (y + m < w):
						if visit[x + n][y + m] < 0 and s[x][y] != s[x + n][y + m]:
							visit[x + n][y + m] = 1
							if s[x][y] == '#':
								white += 1
							else:
								black += 1
							q.append([x + n, y + m])
			r += black * white
print(r)


import sys
sys.setrecursionlimit(10 ** 7)
(h, w) = map(int, input().split())
s = [list(input()) for _ in range(h)]
seen = [[0] * w for _ in range(h)]
dxdy = [(-1, 0), (1, 0), (0, -1), (0, 1)]
global ans

def dfs(x, y):
	seen[y][x] = 1
	(a, b) = (1, 0)
	for (dx, dy) in dxdy:
		nx = x + dx
		ny = y + dy
		if 0 <= nx < w and 0 <= ny < h and (not seen[ny][nx]) and (s[y][x] != s[ny][nx]):
			p = dfs(nx, ny)
			a += p[1]
			b += p[0]
	return (a, b)
ans = 0
for i in range(h):
	for j in range(w):
		if not seen[i][j]:
			p = dfs(j, i)
			ans += p[0] * p[1]
print(ans)


from itertools import product
direction = []
for i in range(4):
	dx = 5 % (i + 1) - 1
	dy = 5 % (i + 2) - 1
	direction.append((dx, dy))
(H, W) = map(int, input().split())
grid = [input() for _ in range(H)]
visited = [[False for _ in range(W)] for _ in range(H)]
ans = 0
for (i, j) in product(range(H), range(W)):
	if visited[i][j]:
		continue
	stack = [(i, j)]
	black = 0
	white = 0
	while stack:
		(x, y) = stack.pop()
		if visited[x][y]:
			continue
		visited[x][y] = True
		if grid[x][y] == '#':
			black += 1
		else:
			white += 1
		for (dx, dy) in direction:
			(temp_x, temp_y) = (min(max(x + dx, 0), H - 1), min(max(y + dy, 0), W - 1))
			if visited[temp_x][temp_y]:
				continue
			if grid[x][y] != grid[temp_x][temp_y]:
				stack.append((temp_x, temp_y))
	ans += black * white
print(ans)


(H, W) = map(int, input().split())
S = [list(input()) for _ in range(H)]
visited = [[False] * W for _ in range(H)]

def search(sx, sy):
	q = [(sx, sy)]
	visited[sy][sx] = True
	(b, w) = (0, 0)
	if S[sy][sx] == '#':
		b += 1
	else:
		w += 1
	while q:
		(cx, cy) = q.pop()
		for (dx, dy) in ((1, 0), (-1, 0), (0, 1), (0, -1)):
			(nx, ny) = (cx + dx, cy + dy)
			if 0 <= nx < W and 0 <= ny < H and (not visited[ny][nx]) and (S[cy][cx] != S[ny][nx]):
				visited[ny][nx] = True
				q.append((nx, ny))
				if S[ny][nx] == '#':
					b += 1
				else:
					w += 1
	return b * w
ret = 0
for y in range(H):
	for x in range(W):
		if not visited[y][x]:
			ret += search(x, y)
print(ret)


from collections import deque

def bfs(sl, visited, sy, sx, h, w):
	q = deque([(sy, sx, sl[sy][sx])])
	visited[sy][sx] = 0
	bh_cnt = {'#': 0, '.': 0}
	bh_cnt[sl[sy][sx]] += 1
	while q:
		(y, x, bh) = q.popleft()
		for (j, k) in ([1, 0], [-1, 0], [0, 1], [0, -1]):
			(ny, nx) = (y + j, x + k)
			if ny >= h or nx >= w or ny < 0 or (nx < 0):
				continue
			if sl[ny][nx] != bh and visited[ny][nx] == -1:
				visited[ny][nx] = visited[y][x] + 1
				bh_cnt[sl[ny][nx]] += 1
				q.append((ny, nx, sl[ny][nx]))
	return bh_cnt['#'] * bh_cnt['.']
(h, w) = map(int, input().split())
sl = []
for _ in range(h):
	row = list(input())
	sl.append(row)
visited = [[-1] * w for i in range(h)]
ans = 0
for hi in range(h):
	for wi in range(w):
		if visited[hi][wi] != -1:
			continue
		ans += bfs(sl, visited, hi, wi, h, w)
print(ans)


def inpl():
	return list(map(int, input().split()))
(H, W) = inpl()
S = ''
for i in range(H):
	S += input()
N = H * W
parent = [-1] * N
white = [0] * N
black = [0] * N

def group(n):
	if parent[n] < 0:
		return n
	else:
		g = group(parent[n])
		parent[n] = g
		return g

def merge(m, n):
	gm = group(m)
	gn = group(n)
	if gm != gn:
		parent[gn] = gm
		white[gm] += white[gn]
		black[gm] += black[gn]
	return gm

def groupsize(n):
	g = group(n)
	return white[g] * black[g]

def place(n):
	return divmod(n, W)

def index(h, w):
	return h * W + w
for n in range(N):
	if S[n] == '.':
		white[n] = 1
	else:
		black[n] = 1
	(h, w) = place(n)
	if h > 0 and S[n] != S[n - W]:
		merge(n - W, n)
	if w > 0 and S[n] != S[n - 1]:
		merge(n - 1, n)
groupset = set()
for n in range(N):
	groupset.add(group(n))
sizes = [groupsize(p) for p in groupset]
ans = sum(sizes)
print(ans)


(h, w) = map(int, input().split())
grid = [list(input()) for i in range(h)]
visited = [[False] * w for i in range(h)]
ans = 0
for i in range(h):
	for j in range(w):
		if visited[i][j]:
			continue
		q = [(i, j)]
		d = {'#': 0, '.': 0}
		while q:
			(cy, cx) = q.pop(0)
			for (ny, nx) in ((cy + 1, cx), (cy - 1, cx), (cy, cx + 1), (cy, cx - 1)):
				if not (0 <= ny < h and 0 <= nx < w) or grid[cy][cx] == grid[ny][nx] or visited[ny][nx]:
					continue
				d[grid[ny][nx]] += 1
				visited[ny][nx] = True
				q.append((ny, nx))
		ans += d['.'] * d['#']
print(ans)