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):
import sys

sys.setrecursionlimit(10 ** 9)


class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n + 1)]
        self.rank = [0 for _ in range(n + 1)]
        self.size = [1] * (n + 1)

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

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

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

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


H, W = map(int, input().split())
s_list = []
for i in range(H):
    s_list.append(input())
check = [[0 for _ in range(W)] for _ in range(H)]

brack_list = []
union_find = UnionFind(H * W)
for i in range(H):
    for j in range(W):
        if s_list[i][j] == "
            brack_list.append(i * W + j)
            if i - 1 >= 0 and s_list[i - 1][j] == ".":
                union_find.union(i * W + j, (i - 1) * W + j)
            if i + 1 < H and s_list[i + 1][j] == ".":
                union_find.union(i * W + j, (i + 1) * W + j)
            if j - 1 >= 0 and s_list[i][j - 1] == ".":
                union_find.union(i * W + j, i * W + j - 1)
            if j + 1 < W and s_list[i][j + 1] == ".":
                union_find.union(i * W + j, i * W + j + 1)


black = {}
white = {}
for i in range(H):
    for j in range(W):
        p = union_find.find(i * W + j)
        if s_list[i][j] == "
            if p in black:
                black[p] += 1
            else:
                black[p] = 1
        else:
            if p in white:
                white[p] += 1
            else:
                white[p] = 1

p = set(union_find.parent[:-1])
count = 0
for i in p:
    if i in black and i in white:
        count += white[i] * black[i]
print(count)

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

Solution (Python):
import heapq

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

L = [["N" for j in range(W)] for i in range(H)]
c = 0

for i in range(H):
	for j in range(W):
		if L[i][j] == "N":
			L[i][j] = c
			Q = []
			heapq.heappush(Q, (i, j))
			while Q:
				x, y = heapq.heappop(Q)
				if x - 1 >= 0:
					if Sl[x][y] != Sl[x - 1][y] and L[x - 1][y] == "N":
						L[x - 1][y] = c
						heapq.heappush(Q, (x - 1, y))
				if x + 1 <= H - 1:
					if Sl[x][y] != Sl[x + 1][y] and L[x + 1][y] == "N":
						L[x + 1][y] = c
						heapq.heappush(Q, (x + 1, y))
				if y - 1 >= 0:
					if Sl[x][y] != Sl[x][y - 1] and L[x][y - 1] == "N":
						L[x][y - 1] = c
						heapq.heappush(Q, (x, y - 1))
				if y + 1 <= W - 1:
					if Sl[x][y] != Sl[x][y + 1] and L[x][y + 1] == "N":
						L[x][y + 1] = c
						heapq.heappush(Q, (x, y + 1))
			c += 1

xl = []
for i in range(c):
	xl.append([0, 0])

for i in range(H):
	for j in range(W):
		if Sl[i][j] == "
			xl[L[i][j]][0] += 1
		else:
			xl[L[i][j]][1] += 1

ans = 0
for i in range(c):
	ans += xl[i][0] * xl[i][1]

print(ans)

Solution (Python):


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)

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

Solution (Python):
import sys
sys.setrecursionlimit(200000)

H,W = map(int,input().split(' '))
S = []
for i in [0]*H:
	l = input()
	S.append([1 if x == '

bk = 0
wh = 0
def check(S,x,y):
	global bk
	global wh
	if S[y][x] == 0:
		return
	if S[y][x] == 1:
		bk += 1
		S[y][x]=0
		if 0 < y and S[y-1][x] == -1:
			check(S,x,y-1)
		if 0 < x and S[y][x-1] == -1:
			check(S,x-1,y)
		if y < H-1 and S[y+1][x] == -1:
			check(S,x,y+1)
		if x < W-1 and S[y][x+1] == -1:
			check(S,x+1,y)
		return
	if S[y][x] == -1:
		wh += 1
		S[y][x]=0
		if 0 < y and S[y-1][x] == 1:
			check(S,x,y-1)
		if 0 < x and S[y][x-1] == 1:
			check(S,x-1,y)
		if y < H-1 and S[y+1][x] == 1:
			check(S,x,y+1)
		if x < W-1 and S[y][x+1] == 1:
			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)

Solution (Python):
import collections
H,W=map(int,input().split())
S=[input() for i in [0]*H]
M=[[-1]*W for _ in [0]*H]
k=0
for y in range(H):
    for x in range(W):
        if M[y][x]!=-1:continue 
        M[y][x]=k
        Q=collections.deque()
        Q.append((y,x))
        while len(Q)>0:
            i,j=Q.popleft()
            s=S[i][j]
            if i+1<H and M[i+1][j]==-1 and s!=S[i+1][j]:
                M[i+1][j]=k
                Q.append((i+1,j))
            if i-1>=0 and M[i-1][j]==-1 and s!=S[i-1][j]:
                M[i-1][j]=k
                Q.append((i-1,j))
            if j+1<W and M[i][j+1]==-1 and s!=S[i][j+1]:
                M[i][j+1]=k
                Q.append((i,j+1))
            if j-1>=0 and M[i][j-1]==-1 and s!=S[i][j-1]:
                M[i][j-1]=k
                Q.append((i,j-1))
            
        k+=1
ds={}
dd={}
for i in range(H):
    for j in range(W):
        m=M[i][j]
        if S[i][j]=='
        else:dd[m]=dd.get(m,0)+1
r=0
for i in range(k):
    r += ds.get(i,0)*dd.get(i,0)
print(r)

Solution (Python):
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [H, W] = [long(input_raw[0]), long(input_raw[1])]
    S = []
    for i in range(H):
        input_raw = read_func().strip()
        S.append(input_raw)

    move_list = [(0,1),(1,0),(0,-1),(-1,0)]
    is_visited = set([])
    count = 0
    for i in range(H):
        for j in range(W):
            path_list = [(i, j)]
            if (i, j) not in is_visited:
                is_visited.add((i, j))

                q = deque([(i, j)])
                while len(q) > 0:
                    nd = q.popleft()
                    for move in move_list:
                        new_i = nd[0] + move[0]
                        new_j = nd[1] + move[1]
                        if new_i >= 0 and new_j >= 0 and new_i < H and new_j < W:
                            if (new_i, new_j) not in is_visited:
                                if S[nd[0]][nd[1]] != S[new_i][new_j]:
                                    path_list.append((new_i, new_j))
                                    is_visited.add((new_i, new_j))
                                    q.append((new_i, new_j))
            black_num = 0
            white_num = 0
            for path in path_list:
                if S[path[0]][path[1]] == "
                    black_num += 1
                else:
                    white_num += 1
            count +=black_num *white_num

    print count



if __name__ == '__main__':
    main()

Solution (Python):
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]=='
  else:d[m]=d.get(m,0)+1
print(sum(s.get(i,0)*d.get(i,0)for i in range(k)))

Solution (Python):
H,W=map(int,input().split())
h=range(H)
S=[input() for _ in h]
M=[[-1]*W for _ in h]
k=0
for y in h:
    for x in range(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 range(H):
    for j in range(W):
        m=M[i][j]
        if S[i][j]=='
        else:d[m]=d.get(m,0)+1
print(sum(s.get(i,0)*d.get(i,0)for i in range(k)))

Solution (Python):
from queue import Queue as Qe

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

D = [[-1 for j in range(W)] for i in range(H)]
S = [input() for i in range(H)]

D[0][0] = 1
q = Qe()
q.put((0,0))
White = 1 if S[0][0] == "." else 0
Black = 1 if S[0][0] == "
ans = 0

def_h = 0
def_w = 0
while not q.empty():
    h,w = q.get()
    
    if h-1>=0 and S[h][w]!=S[h-1][w] and D[h-1][w] == -1: 
        if S[h-1][w]=="
            ans += White
            Black += 1
        else:
            ans += Black
            White += 1
        D[h-1][w] = 1
        q.put((h-1,w))
    if h+1<H and S[h][w]!=S[h+1][w] and D[h+1][w] == -1: 
        if S[h+1][w]=="
            ans += White
            Black += 1
        else:
            ans += Black
            White += 1
        D[h+1][w] = 1
        q.put((h+1,w))
    if w-1>=0 and S[h][w]!=S[h][w-1] and D[h][w-1] == -1: 
        if S[h][w-1]=="
            ans += White
            Black += 1
        else:
            ans += Black
            White += 1
        D[h][w-1] = 1
        q.put((h,w-1))
    if w+1<W and S[h][w]!=S[h][w+1] and D[h][w+1] == -1: 
        if S[h][w+1]=="
            ans += White
            Black += 1
        else:
            ans += Black
            White += 1
        D[h][w+1] = 1
        q.put((h,w+1))
    if q.empty():
        okei = False
        for i in range(def_h,H):
            wara = def_w if i==def_h else 0
            for j in range(wara,W):
                if D[i][j] == -1:
                    D[i][j] = 1
                    q.put((i,j))
                    White = 1 if S[i][j] == "." else 0
                    Black = 1 if S[i][j] == "
                    def_h,def_w = i,j
                    okei = True
                    break
            if okei: break
                
print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.v = [-1 for _ in range(n)]  
        self.bk = [1 if s[r][c] == '
        self.wt = [1 if s[r][c] == '.' else 0 for r in range(H) for c in range(W)]

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

    def unite(self, x, y):  
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if -self.v[x] < -self.v[y]:  
            x, y = y, x  
        self.v[x] += self.v[y]  
        self.v[y] = x  

        self.bk[x % (H * W)] += self.bk[y % (H * W)]
        self.wt[x % (H * W)] += self.wt[y % (H * W)]

    def root(self, x):
        return self.v[x] < 0  

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

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

    def calc(self, x):
        return self.bk[x % (H * W)] * self.wt[x % (H * W)]

dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]

H, W = map(int, input().split())
s = [input() for _ in range(H)]
uf = UnionFind(2 * H * W)  
for r in range(H):
    for c in range(W):
        if s[r][c] == '
            for i in range(4):
                nr = r + dr[i]
                nc = c + dc[i]
                if 0 <= nr < H and 0 <= nc < W:
                    if s[nr][nc] == '.':
                        uf.unite(r * W + c, H * W + (nr * W + nc))  
        else:
            for i in range(4):
                nr = r + dr[i]
                nc = c + dc[i]
                if 0 <= nr < H and 0 <= nc < W:
                    if s[nr][nc] == '
                        uf.unite(H * W + (r * W + c), nr * W + nc)  

ans = 0
for r in range(H):
    for c in range(W):
        if uf.root(r * W + c):
            
            sz = uf.size(r * W + c)
            
            if sz > 1:
                ans += uf.calc(r * W + c)

        if uf.root(H * W + (r * W + c)):
            
            sz = uf.size(H * W + (r * W + c))
            
            if sz > 1:
                ans += uf.calc(H * W + (r * W + c))

print(ans)

Solution (Python):
h,w=map(int,input().split())
s=[[0]+list(input())+[0]for i in range(h)]
s.insert(0,[0]*(w+2))
s.append([0]*(w+2))
c=["
n=0
for i in range(1,h+1):
    for j in range(1,w+1):
        g=[0,0]
        if s[i][j]!=0:
            p=c.index(s[i][j])
            g[c.index(s[i][j])]+=1
            k=[[i,j]]
            s[i][j]=0
            while len(k)>0:
                b=[]
                for f in range(len(k)):
                    if s[k[f][0]+1][k[f][1]]==c[(p+1)%2]:
                        b.append([k[f][0]+1,k[f][1]])
                        s[k[f][0]+1][k[f][1]]=0
                    if s[k[f][0]-1][k[f][1]]==c[(p+1)%2]:
                        b.append([k[f][0]-1,k[f][1]])
                        s[k[f][0]-1][k[f][1]]=0
                    if s[k[f][0]][k[f][1]+1]==c[(p+1)%2]:
                        b.append([k[f][0],k[f][1]+1])
                        s[k[f][0]][k[f][1]+1]=0
                    if s[k[f][0]][k[f][1]-1]==c[(p+1)%2]:
                        b.append([k[f][0],k[f][1]-1])
                        s[k[f][0]][k[f][1]-1]=0
                else:
                    k=b
                    g[(p+1)%2]+=len(b)
                    p+=1
            else:
                n+=g[0]*g[1]
else:
    print(n)

Solution (Python):
h,w=map(int,input().split())
s=[[0]+list(input())+[0]for i in range(h)]
s.insert(0,[0]*(w+2))
s.append([0]*(w+2))
c=["
n=0
for i in range(1,h+1):
    for j in range(1,w+1):
        g=[0,0]
        if s[i][j]!=0:
            p=c.index(s[i][j])
            g[c.index(s[i][j])]+=1
            k=[[i,j]]
            s[i][j]=0
            while len(k)>0:
                b=[]
                for f in range(len(k)):
                    if s[k[f][0]+1][k[f][1]]==c[(p+1)%2]:
                        b.append([k[f][0]+1,k[f][1]])
                        s[k[f][0]+1][k[f][1]]=0
                    if s[k[f][0]-1][k[f][1]]==c[(p+1)%2]:
                        b.append([k[f][0]-1,k[f][1]])
                        s[k[f][0]-1][k[f][1]]=0
                    if s[k[f][0]][k[f][1]+1]==c[(p+1)%2]:
                        b.append([k[f][0],k[f][1]+1])
                        s[k[f][0]][k[f][1]+1]=0
                    if s[k[f][0]][k[f][1]-1]==c[(p+1)%2]:
                        b.append([k[f][0],k[f][1]-1])
                        s[k[f][0]][k[f][1]-1]=0
                else:
                    k=b
                    g[(p+1)%2]+=len(b)
                    p+=1
            else:
                n+=g[0]*g[1]
else:
    print(n)

Solution (Python):
def inpl(): return [int(i) for i in input().split()]
def ndir(noh, now):
    result = []
    if now != 0:
        result.append((noh, now-1))
    if now != W-1:
        result.append((noh, now+1))
    if noh != 0:
        result.append((noh-1, now))
    if noh != H-1:
        result.append((noh+1, now))
    return result

H, W = inpl()
S = [input() for _ in range(H)]
direc = [(1, 0), (-1, 0), (0, 1), (0, -1)]
Col = [[0]*W for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if Col[i][j] or S[i][j] == '
            continue
        gw, gb, kw, kb = 0, 0, 0, 0
        stack = [(i, j)]
        while stack:
            nh, nw = stack.pop()
            Col[nh][nw] = True
            if (nh+nw)%2:
                if S[nh][nw] == '
                    kb += 1
                else:
                    kw += 1
            else:
                if S[nh][nw] == '
                    gb += 1
                else:
                    gw += 1
            for ah, aw in ndir(nh, nw):
                if (S[nh][nw] == '.')^(S[ah][aw] == '.') and not Col[ah][aw]:
                    stack.append((ah, aw))
                    Col[ah][aw] = True
        ans += kb*gw + kw*gb
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
H,W=map(int,input().split())
series = [[] for h in range(H)]
for h in range(H):
	series[h] = list(input())

def Go(h,w):
	
	global c
	check[h][w]=1
	count = 0
	front = ""
	if series[h][w] == "
		front = "."
	else:
		front = "
	if h >= 1:
		if series[h-1][w] == front and check[h-1][w] == 0:
			if series[h-1][w] == ".":
				count += Go(h-1,w)+1
			else:
				count += Go(h-1,w)
				c += 1
				used[h-1][w] = 1
	if h < H-1:
		if series[h+1][w] == front and check[h+1][w] == 0:
			if series[h+1][w] == ".":
				count += Go(h+1,w)+1
			else:
				count += Go(h+1,w)
				c += 1
				used[h+1][w] = 1
	if w >= 1:
		if series[h][w-1] == front and check[h][w-1] == 0:
			if series[h][w-1] == ".":
				count += Go(h,w-1)+1
			else:
				count += Go(h,w-1)
				c += 1
				used[h][w-1] = 1
	if w < W-1:
		if series[h][w+1] == front and check[h][w+1] == 0:
			if series[h][w+1] == ".":
				count += Go(h,w+1)+1
			else:
				count += Go(h,w+1)
				c += 1
				used[h][w+1] = 1
	return count

ans=0
used =  [[0 for w in range(W)] for h in range(H)]
check = [[0 for w in range(W)] for h in range(H)]
for h in range(H):
	for w in range(W):
		if series[h][w] == "
			c=1
			ans += Go(h,w) * c
print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.v = [-1 for _ in range(n)]  
        self.bk = [1 if s[r][c] == '
        self.wt = [1 if s[r][c] == '.' else 0 for r in range(H) for c in range(W)]

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

    def unite(self, x, y):  
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if -self.v[x] < -self.v[y]:  
            x, y = y, x  
        self.v[x] += self.v[y]  
        self.v[y] = x  

        self.bk[x % (H * W)] += self.bk[y % (H * W)]
        self.wt[x % (H * W)] += self.wt[y % (H * W)]

    def root(self, x):
        return self.v[x] < 0  

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

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

    def calc(self, x):
        return self.bk[x % (H * W)] * self.wt[x % (H * W)]

dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]

H, W = map(int, input().split())
s = [input() for _ in range(H)]
uf = UnionFind(2 * H * W)  
for r in range(H):
    for c in range(W):
        if s[r][c] == '
            for i in range(4):
                nr = r + dr[i]
                nc = c + dc[i]
                if 0 <= nr < H and 0 <= nc < W:
                    if s[nr][nc] == '.':
                        uf.unite(r * W + c, H * W + (nr * W + nc))  
        else:
            for i in range(4):
                nr = r + dr[i]
                nc = c + dc[i]
                if 0 <= nr < H and 0 <= nc < W:
                    if s[nr][nc] == '
                        uf.unite(H * W + (r * W + c), nr * W + nc)  

ans = 0
for r in range(H):
    for c in range(W):
        if uf.root(r * W + c):
            
            sz = uf.size(r * W + c)
            
            if sz > 1:
                ans += uf.calc(r * W + c)

        if uf.root(H * W + (r * W + c)):
            
            sz = uf.size(H * W + (r * W + c))
            
            if sz > 1:
                ans += uf.calc(H * W + (r * W + c))

print(ans)

Solution (Python):
H, W = map(int, input().split())
board = []
black = "
white = "."
for _ in range(H):
    board.append(input())

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

deltas = [(1, 0), (-1, 0), (0, 1), (0, -1)]

for i in range(H):
    for j in range(W):
        for dx, dy in deltas:
            ni = i + dx
            nj = j + dy
            if \
            ni >= 0 \
            and ni < H \
            and nj >= 0 \
            and nj < W \
            and board[i][j] != board[ni][nj]:
                has_alternative_around[i][j] = True
                has_alternative_around[ni][nj] = True

ans = 0

for i in range(H):
    for j in range(W):
        if flags[i][j] is True \
        or has_alternative_around[i][j] is False:
            continue
        else:
            flags[i][j] = True
            reachable = 1
            n_black = 0
            n_white = 0
            if board[i][j] == black:
                n_black = 1
            else:
                n_white = 1
            visit = []
            for dx, dy in deltas:
                ni = i + dx
                nj = j + dy
                if \
                ni >= 0 \
                and ni < H \
                and nj >= 0 \
                and nj < W \
                and has_alternative_around[ni][nj] is True \
                and board[i][j] != board[ni][nj] \
                and flags[ni][nj] is False:
                    visit.append( (ni, nj) )
                    flags[ni][nj] = True
                    reachable += 1
                    if board[ni][nj] == black:
                        n_black += 1
                    else:
                        n_white += 1
            while len(visit) != 0:
                visit_info = visit.pop()
                prev_i = visit_info[0]
                prev_j = visit_info[1]
                for dx, dy in deltas:
                    ni = prev_i + dx
                    nj = prev_j + dy
                    if \
                    ni >= 0 \
                    and ni < H \
                    and nj >= 0 \
                    and nj < W \
                    and has_alternative_around[ni][nj] is True \
                    and board[prev_i][prev_j] != board[ni][nj] \
                    and flags[ni][nj] is False:
                        visit.append( (ni, nj) )
                        flags[ni][nj] = True
                        reachable += 1
                        if board[ni][nj] == black:
                            n_black += 1
                        else:
                            n_white += 1
            if reachable >= 2:
                ans += n_black * n_white

print(ans)

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


def search(x, y, color):
    global black
    global white
    if color == ".":
        for m in [1, -1]:
            if 0 <= x+m <= H-1:
                if S[x+m][y] == "
                    black += 1
                    dp[x+m][y] = True
                    color = "
                    search(x+m, y, color)
        for n in [1, -1]:
            if 0 <= y+n <= W-1:
                if S[x][y+n] == "
                    black += 1
                    dp[x][y+n] = True
                    color = "
                    search(x, y+n, color)

    else:
        for m in [1, -1]:
            if 0 <= x+m <= H-1:
                if S[x+m][y] == "." and not dp[x+m][y]:
                    white += 1
                    dp[x+m][y] = True
                    color = "."
                    search(x+m, y, color)

        for n in [1, -1]:
            if 0 <= y+n <= W-1:
                if S[x][y+n] == "." and not dp[x][y+n]:
                    white += 1
                    dp[x][y+n] = True
                    color = "."
                    search(x, y+n, color)


ans = 0
dp = [[False] * W for a in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j] == "
            black = 1
            white = 0
            dp[i][j] = True
            search(i, j, "
            ans += black * white

print(ans)

Solution (Python):
def getN():
    return int(input())

def getMN():
    a = input().split()
    b = [int(i) for i in a]
    return b[0],b[1]

def getlist():
    a = input().split()
    b = [int(i) for i in a]
    return b


h,w = getMN()
pos = ["."]*(w*h+5000)
cur = 1

class unionfind():
    def __init__(self,n):
        self.par = [i for i in range(n+1)]
        self.rank = [0]*(n+1)
        self.childnum = [1] * (n + 1)
        self.childb = [0 if pos[i] == "." else 1 for i in range(n+1)]

    def find(self,x):
        if self.par[x] == x:
            return x
        else:
            
            self.par[x] = self.find(self.par[x])
            return self.find(self.par[x])

    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.childnum[y] += self.childnum[x]
            self.childb[y] += self.childb[x]

        else:
            self.par[y] = x
            self.childnum[x] += self.childnum[y]
            self.childb[x] += self.childb[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same_check(self,x,y):
        return self.find(x) == self.find(y)


for i in range(h):
    posin = input()
    for j in range(w):
        if posin[j] == "
            pos[j+(i)*w] = "

uf = unionfind(h*w+1)

unionlog = []

for i in range(h):
    for j in range(w):
        nn = j+(i)*w
        now = pos[nn]

        if j != w-1:
            nr = j + (i) * w + 1
            right = pos[nr]
            if right != now:
                if not uf.same_check(nn,nr):
                    uf.union(nn,nr)
                    unionlog.append("union:{},{}".format(nn,nr))
        if i != h-1:
            nd = j + (i + 1) * w
            down = pos[nd]
            if down != now:
                if not uf.same_check(nn,nd):
                    uf.union(nn,nd)
                    unionlog.append("union:{},{}".format(nn,nd))


a = 0





ans = 0

for parnum in list(set([uf.find(i) for i in range(h*w)])):
    
    b = uf.childb[parnum]
    w = uf.childnum[parnum] - b
    
    ans +=  b*w

print(ans)

Solution (Python):
def search_from(i,j):
    
    if i>0:
        if visited[i-1][j] == 0:
            if map[i][j] != map [i-1][j]:
                to_visit.append((i-1,j))
                

    if i<h-1:
        if visited[i+1][j] == 0:
            if map[i][j] != map [i+1][j]:
                to_visit.append((i+1,j))
                
                
    if j>0:
        if visited[i][j-1] == 0:
            if map[i][j] != map [i][j-1]:
                to_visit.append((i,j-1))
                

    if j<w-1:
        if visited[i][j+1] == 0:
            if map[i][j] != map [i][j+1]:
                to_visit.append((i,j+1))
                

h, w = map(int, input().split())
map = []
for i in range(h):
    map.append(input())



visited = [[0 for i in range(w)] for j in range(h)]



to_visit = []

ans = 0
for i in range(h):
    for j in range(w):
        if visited[i][j] == 1:
            continue
        
        black = 0
        white = 0
        
        to_visit.append((i,j))
        while len(to_visit)>0:
            next = to_visit.pop()
            if visited[next[0]][next[1]] ==0:
                visited[next[0]][next[1]] = 1
                search_from(next[0],next[1])
                if map[next[0]][next[1]] =='
                    black += 1
                if map[next[0]][next[1]] =='.':
                    white += 1
        ans += black * white
        
        
print(ans)