Problem:
 Score : 300 points    Problem Statement 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.        Sample Input 1 3 3
.#.
..#
#..      Sample Output 1 10  Some of the pairs satisfying the condition are ((1, 2), (3, 3)) and ((3, 1), (3, 2)) , where (i, j) denotes the square at the i -th row from the top and the j -th column from the left.       Sample Input 2 2 4
....
....      Sample Output 2 0       Sample Input 3 4 3
###
###
...
###      Sample Output 3 6

Solution (Python):
from collections import defaultdict
class UnionFind:
    def __init__(self, n):
        class KeyDict(dict):
            
            def __missing__(self,key):
                self[key] = key
                return key
        self.parent = KeyDict()
        self.rank = defaultdict(int)
        self.weight = defaultdict(int)

    
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            
            
            y = self.find(self.parent[x])           
            self.weight[x] += self.weight[self.parent[x]]   
            self.parent[x] = y      
            return self.parent[x]

    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
        
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

    
    def weighted_union(self, x, y, w):
        
        px = self.find(x)
        py = self.find(y)
        
        
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
            self.weight[px] = - w - self.weight[x] + self.weight[y]
        else:
            self.parent[py] = px
            self.weight[py] =  w + self.weight[x] - self.weight[y]
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return 0

    
    def judge(self, x, y):
        return self.find(x) == self.find(y)


H,W = map(int, input().split())
fields = [list(input()) for i in range(H)]
uf = UnionFind(H*W)
for i in range(H):
    for j in range(W):
        if i-1 >= 0 and fields[i][j] != fields[i-1][j]:
            uf.union(i*W+j,(i-1)*W+j)
        if j-1 >= 0 and fields[i][j] != fields[i][j-1]:
            uf.union(i*W+j,i*W+j-1)
        if i+1 < H and fields[i][j] != fields[i+1][j]:
            uf.union(i*W+j,(i+1)*W+j)
        if j+1 < W and fields[i][j] != fields[i][j+1]:
            uf.union(i*W+j,i*W+j+1)


cnt_w = defaultdict(int)
cnt_b = defaultdict(int)
ps = set()
for i in range(H):
    for j in range(W):
        p = uf.find(i*W+j)
        ps.add(p)
        if fields[i][j] == ".":
            cnt_w[p] += 1
        else:
            cnt_b[p] += 1
ans = 0
for p in ps:
    ans += cnt_w[p] * cnt_b[p]
print(ans)

Solution (Python):
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["

print(ans)

Solution (Python):
from collections import deque

h, w = map(int, input().split())
S = []
for _ in range(h):
    s = str(input())
    S.append(s)

dq = deque([])
if S[0][0] == '.':
    dq.append([0,0,'.'])
else:
    dq.append([0,0,'

Visited = [[False for _ in range(w)] for _ in range(h)]
Visited[0][0] = True

All_grid = deque([])
for i in range(h):
    for j in range(w):
        if i == 0 and j == 0:
            pass
        else:
            All_grid.append([i,j])

ans = 0
black = 0
white = 0
while dq:
    now = dq.popleft()

    y = now[0]
    x = now[1]
    color = now[2]

    if color == '.':
        white += 1
    else:
        black += 1

    Nexts = [[y,x-1], [y,x+1], [y-1,x], [y+1,x]]
    for nex in Nexts:
        if nex[0] >= h or nex[0] < 0 or nex[1] >= w or nex[1] < 0:
            continue
        if Visited[nex[0]][nex[1]] == True:
            continue

        if color == '.' and S[nex[0]][nex[1]] == '.':
            continue
        elif color == '
            continue
        elif color == '.' and S[nex[0]][nex[1]] == '
            dq.append([nex[0], nex[1], '
            Visited[nex[0]][nex[1]] = True
        else:
            dq.append([nex[0], nex[1], '.'])
            Visited[nex[0]][nex[1]] = True

    if len(dq) == 0:
        ans += black * white
        black = 0
        white = 0

        while All_grid:
            cand = All_grid.popleft()
            i = cand[0]
            j = cand[1]
            if Visited[i][j] == False:
                c = S[i][j]
                dq.append([i,j,c])
                Visited[i][j] = True
                break

print(ans)

Solution (Python):
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)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
S = [input() for _ in range(H)]

ans = 0
searched = [[0]*W for _ in range(H)]
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

for i in range(H):
	for j in range(W):
		if searched[i][j] or S[i][j] == ".":
			continue
		num_b = 0
		num_w = 0
		q = deque()
		q.append((i, j))
		num_b += 1
		searched[i][j] = 1
		while q:
			y, x = q.popleft()
			for k in range(4):
				ny = y + dy[k]
				nx = x + dx[k]
				if 0 <= ny <= H-1 and 0 <= nx <= W-1 and not searched[ny][nx] and S[ny][nx] != S[y][x]:
					searched[ny][nx] = 1
					if S[ny][nx] == "
						num_b += 1
					else:
						num_w += 1
					q.append((ny, nx))
		ans += num_b*num_w

print(ans)

Solution (Python):
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, "
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)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    from collections import deque
    H, W = (int(i) for i in input().split())
    c = [input() for i in range(H)]
    seen = [[False]*W for _ in range(H)]
    que = deque()
    for h in range(H):
        for w in range(W):
            if c[h][w] == "
                que.append((h, w))

    def bfs(sy, sx):
        que = deque()
        que.append((sy, sx))
        d = ((1, 0), (0, 1), (-1, 0), (0, -1))
        flag = True  
        bla = 0
        whi = 0
        while que:
            uh, uw = que.popleft()
            if seen[uh][uw]:
                continue
            if c[uh][uw] == "
                flag = True
                bla += 1
                seen[uh][uw] = True
            else:
                flag = False
                whi += 1
                seen[uh][uw] = True
            for dy, dx in d:
                next_h = uh + dy
                next_w = uw + dx
                if not(0 <= next_h < H and 0 <= next_w < W):
                    continue
                if seen[next_h][next_w]:
                    continue
                if flag and c[next_h][next_w] == '
                    continue
                if not(flag) and c[next_h][next_w] == '.':
                    continue
                que.append((next_h, next_w))
        return whi*bla

    ans = 0
    for q in que:
        if seen[q[0]][q[1]]:
            continue
        ans += bfs(q[0], q[1])
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import queue
def main():
    h, w = map(int, input().split())
    s = [input().rstrip() for _ in range(h)]
    g = [[0 for j in range(w)] for i in range(h)]
    num = 1
    q = queue.Queue()
    for i in range(h):
        for j in range(w):
            if g[i][j] != 0:
                continue
            q.put([i, j])
            g[i][j] = num
            while not q.empty():
                y, x = q.get()
                if 0 < y and g[y-1][x] == 0 and s[y][x] != s[y-1][x]:
                    g[y-1][x] = num
                    q.put([y-1, x])
                if y < h-1 and g[y+1][x] == 0 and s[y][x] != s[y+1][x]:
                    g[y+1][x] = num
                    q.put([y+1, x])
                if 0 < x and g[y][x-1] == 0 and s[y][x] != s[y][x-1]:
                    g[y][x-1] = num
                    q.put([y, x-1])
                if x < w-1 and g[y][x+1] == 0 and s[y][x] != s[y][x+1]:
                    g[y][x+1] = num
                    q.put([y, x+1])
            num += 1
    blk, wht = [0]*(num+1), [0]*(num+1)
    for i in range(h):
        for j in range(w):
            if s[i][j] == "
                blk[g[i][j]] += 1
            else:
                wht[g[i][j]] += 1
    ans = 0
    for i in range(num+1):
        ans += blk[i] * wht[i]
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
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)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
black = 0
white = 0

def check(s,t):
    if (0 <=  s <= h - 1) and (0 <= t <= w - 1):
        return True
    else:
        return False
def bfs(que):
    finished = set()
    while que:
        x , y, color = que.popleft()
        if x+y*w not in finished:
            finished.add(x+y*w)
            for i, j in ((1, 0), (0, 1)):
                if abs(i) + abs(j) < 2 and check(y+j,x+i):
                    if (x+i)+(y+j)*w not in finished:
                        que.append([x+i,y+j,grid[y+j][x+i]])
                    if color != grid[y+j][x+i]:
                        adjacent_list[x+w*y].append((x + i)+w*(y + j))
                        adjacent_list[(x + i)+w*(y + j)].append(x+w*y)
def dfs(node):
    global white
    global black
    finished.add(node)
    y,x = divmod(node,w)
    if grid[y][x] == '
        black += 1
    else:
        white += 1
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i)
from collections import deque
h,w = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
ans = 0
adjacent_list = [[] for i in range(h*w)]
que = deque()
que.append([0,0,grid[0][0]])
bfs(que)

finished = set()
for i in range(h*w):
    
    black = 0
    white = 0
    if i not in finished:
        dfs(i)
        ans += black * white
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
black = 0
white = 0

def check(s,t):
    if (0 <=  s <= h - 1) and (0 <= t <= w - 1):
        return True
    else:
        return False
def bfs(que):
    finished = set()
    while que:
        x , y, color = que.popleft()
        if x+y*w not in finished:
            finished.add(x+y*w)
            for i in range(-1,2,1):
                for j in range(-1,2,1):
                    if abs(i) + abs(j) < 2 and check(y+j,x+i):
                        if (x+i)+(y+j)*w not in finished:
                            que.append([x+i,y+j,grid[y+j][x+i]])
                        if color != grid[y+j][x+i]:
                            adjacent_list[x+w*y].append((x + i)+w*(y + j))
def dfs(node):
    global white
    global black
    finished.add(node)
    y,x = divmod(node,w)
    if grid[y][x] == '
        black += 1
    else:
        white += 1
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i)
from collections import deque
h,w = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
ans = 0
adjacent_list = [[] for i in range(h*w)]
"""
que = deque()
que.append([0,0,grid[0][0]])
bfs(que)
"""
for y in range(h):
    for x in range(w):
        for i in range(-1,2,1):
            for j in range(-1,2,1):
                if abs(i) + abs(j) < 2 and check(y+j,x+i):
                    if grid[y][x] != grid[y+j][x+i]:
                        adjacent_list[x+w*y].append((x + i)+w*(y + j))

finished = set()
for i in range(h*w):
    
    black = 0
    white = 0
    if i not in finished:
        dfs(i)
        ans += black * white
print(ans)

Solution (Python):



h, w = list(map(int, input().split()))
masu = [input() for _ in range(h)]
visited = [[False for _ in range(w)] for _ in range(h)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]




import sys
sys.setrecursionlimit(400*400 + 10)

def dfs(hi, wi, white, black):
    global colors
    global dx, dy
    global visited

    

    visited[hi][wi] = True
    if masu[hi][wi] == '.':
        white += 1
    if masu[hi][wi] == '
        black += 1

    for neighbor in zip(dx, dy):
        h_new = hi + neighbor[0]
        w_new = wi + neighbor[1]
        
        if 0 <= h_new <= h-1 and 0 <= w_new <= w-1:
            if not visited[h_new][w_new]:
                if masu[hi][wi] != masu[h_new][w_new]:
                    white, black = dfs(h_new, w_new, white, black)
    
    return white, black

ans = 0
for hi in range(h):
    for wi in range(w):
        if not visited[hi][wi]:
            white, black = dfs(hi, wi, 0, 0)
            ans += white * black

print(ans)

Solution (Python):
from collections import deque
H,W = map(int,input().split())
S = [list(input()) for i in range(H)]
blacklist = []
for h in range(H):
    for w in range(W):
        if S[h][w] == '
            blacklist.append((h,w))
ans = 0
alr = [[0 for i in range(W)] for j in range(H)]
h1 = [0,0,1,-1]
w1 = [1,-1,0,0]
for h,w in blacklist:
    if alr[h][w] == 0:
        bcount = 1
        wcount = 0
        que = deque()
        que.append((h,w,True))
        alr[h][w] = 1
        while que:
            hn,wn,black = que.popleft()
            black = not black
            for i in range(4):
                if 0 <= hn+h1[i] <= H-1 and 0 <= wn+w1[i] <= W-1 and not alr[hn+h1[i]][wn+w1[i]]:
                    if (not black) and S[hn+h1[i]][wn+w1[i]] == '.':
                        wcount += 1
                        que.append((hn+h1[i],wn+w1[i],black))
                        alr[hn+h1[i]][wn+w1[i]] = 1
                    elif black and S[hn+h1[i]][wn+w1[i]] == '
                        bcount += 1
                        que.append((hn+h1[i],wn+w1[i],black))
                        alr[hn+h1[i]][wn+w1[i]] = 1
        ans += wcount*bcount
print(ans)

Solution (Python):


import sys

sys.setrecursionlimit(10**9)

def dfs(h,w,start):
    if S[h][w]=="
        black[start[0]][start[1]]+=1
    else:
        white[start[0]][start[1]]+=1
    
    visited[h][w]=1
    if h!=0:
        if visited[h-1][w]==-1 and S[h-1][w]!=S[h][w]:
            dfs(h-1,w,start)
    if w!=0:
        if visited[h][w-1]==-1 and S[h][w-1]!=S[h][w]:
            dfs(h,w-1,start)        
    if h!=H-1:
        if visited[h+1][w]==-1 and S[h+1][w]!=S[h][w]:
            dfs(h+1,w,start)        
    if w!=W-1:
        if visited[h][w+1]==-1 and S[h][w+1]!=S[h][w]:
            dfs(h,w+1,start)    
    return 

H,W=map(int,input().split())

S=[]

for _ in range(H):
    S.append(list(input()))

visited=[[-1 for j in range(W)] for i in range(H)]
black=[[0 for j in range(W)] for i in range(H)]
white=[[0 for j in range(W)] for i in range(H)]

for i in range(H):
    for j in range(W):
        if visited[i][j]==-1:
            dfs(i,j,[i,j])
        

ans=0
for i in range(H):
    for j in range(W):
        ans+=black[i][j]*white[i][j]
"""
print(S)
print(black)
print(white)
"""
print(ans)

Solution (Python):
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

h,w = inm()
s = []
for i in range(h):
    s.append(ins())
a = [[0]*w for i in range(h)]
dir = [(0,1),(0,-1),(1,0),(-1,0)]
id = 0
for i in range(h):
    for j in range(w):
        if a[i][j]!=0:
            continue
        id += 1
        a[i][j] = id
        q = [(i,j)]
        while len(q)>0:
            x,y = q.pop()
            c = s[x][y]
            for d in dir:
                u = x+d[0]
                v = y+d[1]
                if 0<=u<h and 0<=v<w and \
                   a[u][v]==0 and s[u][v]!=c:
                    a[u][v] = id
                    q.append((u,v))
bk = [0]*(id+1)
wh = [0]*(id+1)
for i in range(h):
    for j in range(w):
        if s[i][j]=='
            bk[a[i][j]] += 1
        else:
            wh[a[i][j]] += 1
print(sum([bk[i]*wh[i] for i in range(1,id+1)]))

Solution (Python):
class UnionFind:
    def __init__(self, N):
        self.N = N
        self.parents = [-1] * N

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def all_group_members(self):
        dic = {}
        for x in range(self.N):
            r = self.find(x)
            dic.setdefault(r, [])
            dic[r].append(x)
        return dic

H,W=map(int, input().split())
S=[input() for _ in range(H)]
D=[1,0,-1,0,1]
UF=UnionFind(H*W)
for i in range(H):
    for j in range(W):
        for k in range(4):
            x=i+D[k]
            y=j+D[k+1]
            if 0<=x<H and 0<=y<W:
                if S[i][j]!=S[x][y]:
                    UF.union(x*W+y,i*W+j)
ans=0
for g in UF.all_group_members().values():
    w=0
    b=0
    for v in g:
        x,y=divmod(v,W)
        if S[x][y]=="
            b+=1
        else:
            w+=1
    ans+=w*b
print(ans)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
S = []
for i in range(H):
  S.append(list(input()))

V = {}
for i in range(H):
  for j in range(W):
    V[str(i) + "_" + str(j)] = []
    
for i in range(H):
  for j in range(W):
    
    for dy,dx in [(-1,0), (1,0), (0,-1), (0,1)]:
      y,x = i+dy, j+dx
      if y < 0 or H <= y or x < 0 or W <= x:
        continue
      if S[i][j] == S[y][x]:
        continue
      V[str(i) + "_" + str(j)].append([y,x])
      
ans = 0
visited = [[False for i in range(W)] for j in range(H)]
willsearch = [[False for i in range(W)] for j in range(H)]
Q = deque()

def dfs(y,x):
  wc, bc = 0, 0
  Q.append([y,x])
  while len(Q) > 0:
    b,a = Q.pop()
    
    visited[b][a] = True
    if S[b][a] == '.':
      wc += 1
    else:
      bc += 1
    for q,p in V[str(b) + "_" + str(a)]:
      
      if visited[q][p] or willsearch[q][p]:
        continue
      Q.append([q,p])
      willsearch[q][p] = True
    
  
  return wc*bc

for i in range(H):
  for j in range(W):
    ans += dfs(i,j)
    
print(ans)

Solution (Python):
from collections import defaultdict


class UnionFind():
    
    def __init__(self, n):
        self.n = n
        self.parents = [-1]*n  

    
    def find(self, x):  
        if self.parents[x] < 0:  
            return x
        else:
            
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    
    def union(self, x, y):
        x = self.find(x)  
        y = self.find(y)  
        if x == y:
            return  

        
        if self.parents[x] > self.parents[y]:
            
            
            x, y = y, x

        self.parents[x] += self.parents[y]  
        self.parents[y] = x  

    
    def size(self, x):
        
        return -self.parents[self.find(x)]

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

    
    def members(self, x):
        root = self.find(x)  
        
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_counts(self):
        
        return len(self.roots())

    def all_group_members(self):
        
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


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


uf = UnionFind(H*W)

for i in range(H):
    for j in range(W):
        if 0 <= i < H-1:  
            if gridgraph[i][j] != gridgraph[i+1][j]:
                uf.union(W*i+j, W*(i+1)+j)  

        if 0 <= j < W-1:  
            if gridgraph[i][j] != gridgraph[i][j+1]:
                uf.union(W*i+j, W*i+j+1)  


black = defaultdict(int)
white = defaultdict(int)
for i in range(H):
    for j in range(W):
        if gridgraph[i][j] == "
            black[uf.find(W*i+j)] += 1
        else:
            white[uf.find(W*i+j)] += 1
ans = 0
for u in uf.roots():
    ans += black[u] * white[u]
print(ans)

Solution (Python):
from collections import defaultdict

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

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

uf = UnionFind(H*W)

for i in range(H):
    for j in range(W):
        if 0 <= i < H-1:
            if S[i][j] != S[i+1][j]:
                uf.unite(W*i+j, W*(i+1)+j)
 
        if 0 <= j < W-1:
            if S[i][j] != S[i][j+1]:
                uf.unite(W*i+j, W*i+j+1)


black = defaultdict(int)
white = defaultdict(int)
unions = set(uf.parent)
for i in range(H):
    for j in range(W):
        if S[i][j] == "
            black[uf.root(W*i+j)] += 1
        else:
            white[uf.root(W*i+j)] += 1
ans = 0
for u in unions:
    ans += black[u] * white[u]

print(ans)

Solution (Python):
from collections import defaultdict

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

es = defaultdict(list)

for i in range(H):
    for j in range(W):
        if 0 <= i < H-1:
            if S[i][j] != S[i+1][j]:
                es[(i,j)].append((i+1, j))
                es[(i+1,j)].append((i, j))

        if 0 <= j < W-1:
            if S[i][j] != S[i][j+1]:
                es[(i,j)].append((i, j+1))
                es[(i,j+1)].append((i, j))

checked = [[False for _ in range(W)] for _ in range(H)]

ans = 0
for i in range(H):
    for j in range(W):
        b,w = 0,0
        if not checked[i][j]:
            checked[i][j] = True
            if S[i][j] == "
                b += 1
            else:
                w += 1
            q = es[(i,j)]
            while q:
                y,x = q.pop()
                if not checked[y][x]:
                    checked[y][x] = True
                    if S[y][x] == "
                        b += 1
                    else:
                        w += 1
                    q.extend(es[(y,x)])
            ans += b * w

print(ans)

Solution (Python):
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)

Solution (Python):
h,w = map(int, input().split())
l = [None]*h
for i in range(h):
    l[i] = list(input())

from collections import deque
b_Q = deque()
for i in range(h):
    for j in range(w):
      if l[i][j]=="
          b_Q.append([i,j])

ans=0
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
visited=[[0 for i in range(w)] for j in range(h)]
while b_Q:
    p = b_Q.popleft()
    now = l[p[0]][p[1]]

    if visited[p[0]][p[1]] == 1:
        continue
    visited[p[0]][p[1]] = 1
    b_cnt=1
    w_cnt=0

    search_Q = deque()
    search_Q.append([p[0],p[1]])

    while search_Q:
        sch = search_Q.popleft()
        current = l[sch[0]][sch[1]]
        for i in range(4):
            nx = sch[1] + dx[i]
            ny = sch[0] + dy[i]
            if 0 <= nx < w and 0 <= ny < h:
                if current != l[ny][nx] and visited[ny][nx] == 0: 
                    if current=="
                        w_cnt+=1
                    else:
                        b_cnt+=1
                    search_Q.append([ny,nx])
                    visited[ny][nx]=1
    ans+= b_cnt*w_cnt
print(ans)

Solution (Python):
import sys

from collections import deque

def main():
    H,W = map(int,input().split())
    s = [list(map(str,input())) for _ in range(H)]
    
    dist =[[] for _ in range(H*W)]
    for i in range(H*W):
        x,y = i//W,i%W
        dx,dy = [1,0,-1,0],[0,1,0,-1]
        for j in range(4):
            nx,ny = x+dx[j],y+dy[j]
            if (0<=nx<H and 0<=ny<W and s[x][y]!=s[nx][ny]):
                dist[x*W+y].append(nx*W+ny)

    ans = 0
    go = [False for _ in range(H*W)]
    for i in range(H*W):
        if go[i]:
            continue
        else:
            cc = [0,0]
            queue = deque([i])
            while queue:
                go[i] = True
                now = queue.pop()
                x,y = now//W,now%W
                if s[x][y] == "
                    cc[0] += 1
                else:
                    cc[1] += 1
                for fol in dist[now]:
                    if go[fol]:
                        continue
                    else:
                        queue.append(fol)
                        go[fol] = True
        ans += cc[0]*cc[1]
                        
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
H, W = map(int, input().split())
m = [input() for i in range(H)]
ans = 0

import sys
sys.setrecursionlimit(10**6)

class UnionFind():
  def __init__(self, n):
    self.par = [i for i in range(n)]

  def root(self, x):
    if self.par[x] == x:
      return x
    else:
      self.par[x] = self.root(self.par[x])
      return self.par[x]
  
  def unite(self, x, y):
    x = self.root(x)
    y = self.root(y)
    self.par[y] = x

  def same(self, x, y):
    return self.root(x) == self.root(y)

uf = UnionFind(H*W)

for i in range(H*W):
  h, w = divmod(i, W)
  if 0 <= h-1 and m[h-1][w] != m[h][w]: uf.unite(h*W + w, (h-1)*W + w)
  if h+1 < H  and m[h+1][w] != m[h][w]: uf.unite(h*W + w, (h+1)*W + w)
  if 0 <= w-1 and m[h][w-1] != m[h][w]: uf.unite(h*W + w, h*W + (w-1))
  if w+1 < W  and m[h][w+1] != m[h][w]: uf.unite(h*W + w, h*W + (w+1))

ansb = {}
answ = {}
for i in range(H*W):
  ir = uf.root(i)
  h, w = divmod(i, W)
  if m[h][w] == "
    ansb[ir] = ansb.get(ir, 0) + 1
  else:
    answ[ir] = answ.get(ir, 0) + 1


ans = 0
for k, vb in ansb.items():
  vw = answ.get(k, 0)
  ans += vb * vw

print(ans)

Solution (Python):
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={'
    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)