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
from networkx.utils import UnionFind
def input(): return sys.stdin.readline().rstrip()
def main():
    h, w = map(int, input().split())
    s = [list(input()) for i in range(h)]
    uf = UnionFind()
    for i in range(h):
        for j in range(w):
            if i != h-1:
                if s[i][j] != s[i+1][j]:
                    uf.union((i*w)+j, (i*w)+j+w)
            if j != w-1:
                if s[i][j] != s[i][j+1]:
                    uf.union((i*w)+j, (i*w)+j+1)
    ans=0
    for item in uf.to_sets():
        A=0
        B=0
        for grid in item:
            i,j=divmod(grid,w)
            if s[i][j]=='.':
                A+=1
            else:
                B+=1
        ans+=A*B
    print(ans)
 
 
if __name__ == '__main__':
    main()

Solution (Python):

import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7


def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    ans = 0
    checked = [[0]*W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if S[i][j] == '.' or checked[i][j]:
                continue
            queue = deque()
            queue.append((i, j))
            dx = [1, -1, 0, 0]
            dy = [0, 0, 1, -1]
            black = 1  
            white = 0
            checked[i][j] = 1

            while queue:
                nowy, nowx = queue.popleft()
                for k in range(4):
                    y = nowy + dy[k]
                    x = nowx + dx[k]
                    if 0 <= y < H and 0 <= x < W:
                        if checked[y][x]:
                            continue
                        if S[y][x] != S[nowy][nowx]:
                            if S[y][x] == '.':
                                white += 1
                            else:
                                black += 1
                            queue.append((y, x))
                            checked[y][x] = 1
            
            ans += black * white
            
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque

def main():
    h, w = map(int, input().split())
    tizu = [input().strip() for _ in range(h)]
    directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    used = [[False for _ in range(w)] for _ in range(h)]
    
    ans = 0
    for i in range(h):
        for j in range(w):
            if used[i][j]:
                continue
            used[i][j] = True
            queue = deque()
            queue.append([i, j])
            queue.append(tizu[i][j])
            b_cnt = 0
            w_cnt = 0
            while queue:
                pos = queue.popleft()
                bw = queue.popleft()
                if bw == "
                    b_cnt += 1
                else:
                    w_cnt += 1
                for dy, dx in directions:
                    ny = dy + pos[0]
                    nx = dx + pos[1]
                    if ny == -1 or ny == h or nx == -1 or nx == w:
                        continue
                    if used[ny][nx]:
                        continue
                    bw2 = tizu[ny][nx]
                    if bw == bw2:
                        continue
                    used[ny][nx] = True
                    queue.append([ny, nx])
                    queue.append(bw2)
            ans += b_cnt * w_cnt
    print(ans)

main()

Solution (Python):
h,w=map(int,input().split())
A=[list(input()) for i  in range(h)]
black=[] ;seen=[[0]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if A[i][j]=="
            black.append((i,j))
            
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict 
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal as D  
  
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
from fractions import Fraction as F  





dx=[1,0,-1,0]
dy=[0,1,0,-1]
ans=0



for i,j in black:
    
    if seen[i][j]:continue
    seen[i][j]=1
    color=[0,1]
    queue= deque([(i,j,1)])
    while queue:
        x,y,c= queue.pop()
        
        for xx,yy in zip(dx,dy):
            if 0<=x+xx<h and 0<=y+yy<w and seen[x+xx][y+yy]==0 and A[x+xx][y+yy]==".
                color[1-c]+=1
                seen[x+xx][y+yy]=1 
                queue.appendleft((x+xx,y+yy,1-c))
    ans+= color[0] * color[1]
print(ans)

Solution (Python):


import math

import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd


h,w=map(int,input().split())
s=[list(input()) for _ in range(h)]
seen={}
check=[[0]*w for _ in range(h)]

for i in range(h):
    for j in range(w):
        if s[i][j]=="
            seen[i*w+j]=0
if not seen:
    print(0)
    exit()
d=deque()
p=[[1,0],[-1,0],[0,1],[0,-1]]
ans=0

for j in seen:
    if seen[j]==0:
        d.append(j)
        blue=1
        white=0
        seen[j]=1    
        while d:
            i=d.pop()
            if i==0:
                f=True if s[0][0]=="
            else:
                f=True if i>0 else False
            ih=abs(i)//w
            iw=abs(i)%w
            check[ih][iw]=1
            for v in p:
                x,y=v
                if f==True and 0<=x+iw<w and 0<=y+ih<h and s[y+ih][x+iw]=="." and check[y+ih][x+iw]==0:
                    d.append(((ih+y)*w+(iw+x))*(-1))
                    white+=1
                    check[y+ih][x+iw]=1
                elif f==False and 0<=x+iw<w and 0<=y+ih<h and s[y+ih][x+iw]=="
                    d.append(((ih+y)*w+(iw+x)))
                    seen[((ih+y)*w+(iw+x))]=1
                    check[y+ih][x+iw]=1
                    blue+=1
        ans+=blue*white
print(ans)

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

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

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self._size = [1] * 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._size[ra] < self._size[rb]: ra,rb = rb,ra
        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        self.count += 1
    def size(self,a):
        return self._size[self.root(a)]

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

from collections import defaultdict
bl = defaultdict(lambda: 0)
wh = defaultdict(lambda: 0)
for i in range(H):
    for j in range(W):
        v = i*W+j
        r = uf.root(v)
        if S[i][j]=='
            bl[r] += 1
        else:
            wh[r] += 1

ans = 0
for k in bl.keys():
    ans += bl[k] * wh[k]
print(ans)

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

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

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

Solution (Python):
from collections import deque
H,W=map(int, input().split())

S=[]
for i in range(H):
    s=list(input())
    S.append(s)



dones=[[0]*W for _ in range(H)]
dh=[1,0,-1,0]
dw=[0,1,0,-1]

def judge(h,w):
    if 0<=h<H and 0<=w<W:
        if dones[h][w]==0:
            return True
    return False
ans=0
for h in range(H):
    for w in range(W):
        now=S[h][w]
        if now=="
            que=deque([])
            que.append((h, w, "
            dones[h][w]=1
            blacks=0
            whites=0
            while que:
                nowh, noww, color = que.popleft()
                if color=="
                    blacks+=1
                    
                else:
                    whites+=1
                for i in range(4):
                    nh=nowh+dh[i]
                    nw=noww+dw[i]
                    if judge(nh, nw):
                        if color=="
                            que.append((nh,nw,"."))
                            dones[nh][nw]=1
                        if color=="." and S[nh][nw]=="
                            dones[nh][nw]=1
                            que.append((nh,nw,"
            ans+=blacks*whites
            

print(ans)

Solution (Python):
def aising19_c():
    from collections import deque

    h, w = (int(x) for x in input().split())
    color = [[s == '
    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)

if __name__ == '__main__':
    aising19_c()

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

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_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}



h,w = inpl()
s = [input() for _ in range(h)]
d = [(1,0),(-1,0),(0,1),(0,-1)]
uf = UnionFind(h*w+5)
def ind(i,j): return i*w+j
for y in range(h):
    for x in range(w):
        for dy,dx in d:
            ny = y+dy
            nx = x+dx
            if 0 <= ny < h and 0 <= nx < w and s[ny][nx] != s[y][x]:
                uf.union(ind(y,x), ind(ny,nx))

res = 0
cnt = [[0,0] for _ in range(h*w)]
for i in range(h*w):
    ind = uf.find(i)
    color = 0 if s[i//w][i%w] == '.' else 1
    cnt[ind][color] += 1
for i in range(h*w):
    res += cnt[i][0] * cnt[i][1]
print(res)

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

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

Solution (Python):
from collections import deque
H,W = map(int,input().split())
S = [input().strip() for _ in range(H)]
hist = [[0 for _ in range(W)] for _ in range(H)]
col = 1
for i in range(H):
    for j in range(W):
        if hist[i][j]==0:
            hist[i][j]=col
            que = deque([(i,j,S[i][j])])
            while que:
                y,x,c = que.popleft()
                if x+1<W and S[y][x+1]!=c and hist[y][x+1]==0:
                    hist[y][x+1]=col
                    que.append((y,x+1,S[y][x+1]))
                if y-1>=0 and S[y-1][x]!=c and hist[y-1][x]==0:
                    hist[y-1][x]=col
                    que.append((y-1,x,S[y-1][x]))
                if x-1>=0 and S[y][x-1]!=c and hist[y][x-1]==0:
                    hist[y][x-1]=col
                    que.append((y,x-1,S[y][x-1]))
                if y+1<H and S[y+1][x]!=c and hist[y+1][x]==0:
                    hist[y+1][x]=col
                    que.append((y+1,x,S[y+1][x]))
            col += 1
C = {}
for i in range(H):
    for j in range(W):
        col = hist[i][j]
        if col not in C:
            C[col] = [0,0]
        C[col][0] += 1
        if S[i][j]=="
            C[col][1] += 1
cnt = 0
for col in C:
    if col!=0:
        tot = C[col][0]
        x = C[col][1]
        cnt += x*(tot-x)
print(cnt)

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

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)

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

H, W = map(int, input().split())
S = [list(map(lambda x: 1 if x == '
for i, ss in enumerate(S):
    for j, s in enumerate(ss):
        if (i ^ j) & 1:
            ss[j] ^= 1

visited = [0]*(H*W)

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


def dfs(i, j, cnt):
    c = S[i][j]
    for di, dj in dirs:
        ni, nj = i+di, j+dj
        if not 0 <= ni < H or not 0 <= nj < W:
            continue
        if visited[ni*W+nj]:
            continue
        if c == S[ni][nj]:
            visited[ni*W+nj] = 1
            cnt[(ni ^ nj) & 1] += 1
            dfs(ni, nj, cnt)


ans = 0
for i in range(H):
    for j in range(W):
        if visited[i*W+j]:
            continue
        visited[i*W+j] = 1
        cnt = [0, 0]
        cnt[(i ^ j) & 1] += 1
        dfs(i, j, cnt)
        ans += cnt[0] * cnt[1]
print(ans)

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

Solution (Python):
class UnionFind():
    def __init__(self, n=0):
        self.d = [-1]*n
    
    def find(self, x):
        if self.d[x] < 0: return x
        self.d[x] = self.find(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x,y=self.find(x),self.find(y)
        if x==y:return False
        if self.d[x] > self.d[y]: x,y=y,x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

    def same(self, x,y): return self.find(x)==self.find(y)
    def size(self,x): return -self.d[self.find(x)]

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

def index(i,j):
  return i*W+j

dx,dy = (1,-1,0,0),(0,0,1,-1)
uf = UnionFind(H*W)
for i in range(H):
  for j in range(W):
    x1,y1 = i,j
    for k in range(4):
      x2,y2 = i+dx[k],j+dy[k]
      if 0<=x2<H and 0<=y2<W:
        if S[x1][y1] != S[x2][y2]:
          uf.unite(index(x1,y1),index(x2,y2))
  
data = {}
for k in range(H*W):
  if uf.d[k]==-1:continue
  g = uf.find(k)
  if not data.get(g):
    data[g] = [0,0]
  i,j = divmod(k,W)
  if S[i][j] == '
    data[g][0] += 1
  else:
    data[g][1] += 1
    
ans = 0
for k in data.keys():
  ans += data[k][0]*data[k][1]

print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
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_count(self):
        return len(self.roots())

    def all_group_members(self):
        self.all_group_member=defaultdict(list)
        for i in range(self.n):
            self.all_group_member[self.find(i)].append(i)
        return self.all_group_member

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


def main():
    h, w = map(int, input().split())
    s = [list(input()) for i in range(h)]
    uf = UnionFind(h*w)
    for i in range(h):
        for j in range(w):
            if i != h-1:
                if s[i][j] != s[i+1][j]:
                    uf.union((i*w)+j, (i*w)+j+w)
            if j != w-1:
                if s[i][j] != s[i][j+1]:
                    uf.union((i*w)+j, (i*w)+j+1)
    ans=0
    for item in uf.all_group_members().values():
        A=0
        B=0
        for grid in item:
            i,j=divmod(grid,w)
            if s[i][j]=='.':
                A+=1
            else:
                B+=1
        ans+=A*B
    print(ans)
 
 
if __name__ == '__main__':
    main()

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1 for _ in range(n)]  

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

    def merge(self, x, y):  
        x_root = self.root(x)  
        y_root = self.root(y)  

        if x_root == y_root:  
            return

        if self.parents[x_root] > self.parents[y_root]:  
            x_root, y_root = y_root, x_root

        self.parents[x_root] += self.parents[y_root] 
        self.parents[y_root] = x_root


def main():
    h, w = map(int, input().split())
    grid = [list(input()) for _ in range(h)]
    black_list = []
    uf = UnionFind(h * w)

    for r in range(h):
        for c in range(w):
            if grid[r][c] == "
                black_list.append([r, c])
            for dr, dc in [[0, 1], [1, 0]]:
                nr = r + dr
                nc = c + dc
                if not (0 <= nr < h and 0 <= nc < w):
                    continue
                if grid[r][c] != grid[nr][nc]:
                    
                    uf.merge(r * w + c, nr * w + nc)

    ans = 0
    black_dict = dict()
    for r, c in black_list:  
        z = uf.root(r * w + c)  
        if z in black_dict:  
            black_dict[z] += 1
        else:
            black_dict[z] = 1

    for index, size in enumerate(uf.parents):
        if size < 0:  
            if index not in black_dict:  
                continue
            ans += black_dict[index] * (- size - black_dict[index])  

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1 for _ in range(n)]  

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

    def merge(self, x, y):  
        x_root = self.root(x)  
        y_root = self.root(y)  

        if x_root == y_root:  
            return

        if self.parents[x_root] > self.parents[y_root]:  
            x_root, y_root = y_root, x_root

        self.parents[x_root] += self.parents[y_root] 
        self.parents[y_root] = x_root


def main():
    h, w = map(int, input().split())
    grid = [list(input()) for _ in range(h)]
    black_list = []
    uf = UnionFind(h * w)

    for r in range(h):
        for c in range(w):
            if grid[r][c] == "
                black_list.append([r, c])
            for dr, dc in [[0, 1], [1, 0]]:
                nr = r + dr
                nc = c + dc
                if not (0 <= nr < h and 0 <= nc < w):
                    continue
                if grid[r][c] != grid[nr][nc]:
                    
                    uf.merge(r * w + c, nr * w + nc)

    ans = 0
    black_dict = dict()
    for r, c in black_list:  
        z = uf.root(r * w + c)  
        if z in black_dict:  
            black_dict[z] += 1
        else:
            black_dict[z] = 1

    for index, size in enumerate(uf.parents):
        if size < 0:  
            if index not in black_dict:  
                continue
            ans += black_dict[index] * (- size - black_dict[index])  

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1 for _ in range(n)]  

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

    def merge(self, x, y):  
        x_root = self.root(x)  
        y_root = self.root(y)  

        if x_root == y_root:  
            return

        if self.parents[x_root] > self.parents[y_root]:  
            x_root, y_root = y_root, x_root

        self.parents[x_root] += self.parents[y_root]
        self.parents[y_root] = x_root


def main():
    h, w = map(int, input().split())
    grid = [list(input()) for _ in range(h)]
    black_list = []
    uf = UnionFind(h * w)

    for r in range(h):
        for c in range(w):
            if grid[r][c] == "
                black_list.append([r, c])
            for dr, dc in [[0, 1], [1, 0]]:
                nr = r + dr
                nc = c + dc
                if not (0 <= nr < h and 0 <= nc < w):
                    continue
                if grid[r][c] != grid[nr][nc]:
                    uf.merge(r * w + c, nr * w + nc)

    ans = 0
    black_dict = dict()
    for r, c in black_list:
        z = uf.root(r * w + c)
        if z in black_dict:
            black_dict[z] += 1
        else:
            black_dict[z] = 1

    for index, num in enumerate(uf.parents):
        if num < 0:
            if index not in black_dict:
                continue
            ans += black_dict[index] * (- num - black_dict[index])

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
MOD = 10**9+7

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

S = [list(input()) for i in range(H)]

dx = [1,-1,0,0]
dy = [0,0,1,-1]

start = []
for i in range(H):
    for j in range(W):
        if S[i][j] == "
            start.append((i,j))

not_visited = [[-1]*W for i in range(H)]
def distance(i,j):
    not_visited[i][j] = 0
    stack = deque()
    stack.append((i,j,"

    b,w = 1,0

    while stack != deque([]):
        y,x,mark = stack.popleft()
        for i in range(4):
            if 0<= x+dx[i] <W and 0<= y+dy[i] <H and mark != S[y+dy[i]][x+dx[i]]  and not_visited[y+dy[i]][x+dx[i]] == -1:
                not_visited[y+dy[i]][x+dx[i]] =  not_visited[y][x] + 1
                if mark == "
                    stack.append((y+dy[i],x+dx[i],"."))
                    w += 1
                else:
                    stack.append((y+dy[i],x+dx[i],"
                    b += 1
    
    return b*w

ans = 0
for i in range(H):
    for j in range(W):
        if not_visited[i][j] == -1 and S[i][j] == "
            ans += distance(i,j)
print(ans)