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
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

h,w = map(int,readline().split())
s = read().split()
color = [[0] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if(s[i][j] =='
            color[i][j] = 1

ans = 0
done = [[0] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if(done[i][j]==1):
            continue

        cnt = [0]*2
        cnt[(i+j)%2] += 1
        done[i][j] = 1
        stack = [(i,j)]
        while(stack):
            x,y = stack.pop()
            for dx,dy in zip([-1,1,0,0],[0,0,-1,1]):
                dx += x
                dy += y
                if(0 <= dx < h)&(0 <= dy < w):
                    if(done[dx][dy] == 1):
                        continue
                    if(color[x][y] != color[dx][dy]):
                        done[dx][dy] = 1
                        stack.append((dx,dy))
                        cnt[(dx+dy)%2] += 1
        ans += cnt[0] * cnt[1]
        

print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)


def dfs(x, y, matrix, visited, isWhite):
    global black, white
    dxy = [[1, 0], [-1, 0], [0, -1], [0, 1]]
    visited[y][x] = True
    w = len(matrix[0])
    h = len(matrix)

    for dx, dy in dxy:
        nx = x + dx
        ny = y + dy

        if nx < 0 or w <= nx or ny < 0 or h <= ny:
            continue

        if visited[ny][nx] is True:
            continue

        if (matrix[ny][nx] == "
            matrix[ny][nx] == "." and isWhite is True
        ):
            continue

        if matrix[ny][nx] == "
            black += 1
        else:
            white += 1

        isWhite = not isWhite
        dfs(nx, ny, matrix, visited, isWhite)
        isWhite = not isWhite

    return


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

ans = 0
visited = [[False] * w for _ in range(h)]

for i in range(h):
    for j in range(w):
        if matrix[i][j] == "
            black = 1
            white = 0
            dfs(j, i, matrix, visited, False)
            ans += black * white

print(ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    H, W = [int(x) for x in input().strip().split()]
    M = [0] * (H+2)
    M[0] = ['x'] * (W+2)
    M[-1] = ['x'] * (W+2)
    for h in range(H):
        M[h+1] = ['x'] + list(input().strip()) + ['x']

    dhdw = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    ans = 0
    for i in range(1, H+1):
        for j in range(1, W+1):
            if M[i][j] == 'x':
                continue
            cnt = {'.':0, '
            q = [(i, j, M[i][j])]
            cnt[M[i][j]] = 1
            M[i][j] = 'x'
            while q:
                h, w, m = q.pop()
                
                
                
                for dh, dw in dhdw:
                    if M[h+dh][w+dw] != 'x' and m != M[h+dh][w+dw]:
                        cnt[M[h+dh][w+dw]] += 1
                        q.append((h+dh, w+dw, M[h+dh][w+dw]))
                        M[h+dh][w+dw] = 'x'
            
            
            
            ans += cnt['.']*cnt['
    
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
h, w = map(int, input().split())
s = [input() for i in range(h)]
t = [[None] * w for i in range(h)]
d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
def dfs(i, j, bw):
    global h, w
    if not (0 <= i < h and 0 <= j < w) or s[i][j] == bw or t[i][j]:
        return 0, 0
    t[i][j] = True
    W, b = 0, 0
    if s[i][j] == "
        b += 1
    else:
        W += 1
    for k in d:
        n, m = dfs(i + k[0], j + k[1], s[i][j])
        W += n
        b += m
    return W, b
ans = 0
for i in range(h):
    for j in range(w):
        X, Y = dfs(i, j, "u shi ta pu ni chi a ku n wara")
        ans += X * Y
print(ans)

Solution (Python):
from collections import deque
H,W=map(int,input().split())
S=["*"*(W+2) for _ in range(H+2)]
for i in range(1,H+1):
    S[i]="*"+input()+"*"

K=0
T=[[0]*(W+2) for _ in range(H+2)]
Neighborhood=[(0,1),(0,-1),(1,0),(-1,0)]
p=0

for y in range(1,H+1):
    for x in range(1,W+1):
        if T[y][x]==0:
            p+=1

            if S[y][x]=="
                Black,White=1,0
            elif S[y][x]==".":
                Black,White=0,1

            Q=deque([(x,y)])
            T[y][x]=p

            while Q:
                (u,v)=Q.popleft()
                for (a,b) in Neighborhood:
                    if S[v][u]=="
                        Q.append((u+a,v+b))
                        White+=1
                        T[v+b][u+a]=p
                    elif S[v][u]=="." and S[v+b][u+a]=="
                        Q.append((u+a,v+b))
                        Black+=1
                        T[v+b][u+a]=p

            K+=Black*White
print(K)

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

ans = 0

done = [[0]*W for _ in range(H)]
for sy in range(H):
    for sx in range(W):
        if done[sy][sx]:
            continue
        
        q = deque()
        q.append([sy,sx])
        done[sy][sx] = 1
        n_white = 0
        n_black = 0
        if grid[sy][sx] == '.':
            n_white += 1
        else:
            n_black += 1

        while q:
            y,x = q.popleft()
            for new_y, new_x in [[y+1,x],[y,x+1],[y-1,x],[y,x-1]]:
                if 0<= new_y < H and 0<= new_x < W and not done[new_y][new_x]:
                    if grid[y][x] != grid[new_y][new_x]:
                        
                        if grid[new_y][new_x] == '.':
                            n_white += 1
                        else:
                            n_black += 1
                        
                        done[new_y][new_x] = 1
                        q.append([new_y,new_x])
        ans += n_black*n_white
print(ans)

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

Solution (Python):
import sys,math,collections,itertools
input = sys.stdin.readline

H,W=list(map(int,input().split()))
s = [ input().rstrip() for _ in range(H)]
dp = [[0]*W for _ in range(H)]

def isOK(start):
    q =  collections.deque([start])
    dp[start[0]][start[1]] = 1
    black,white=0,0
    while q:
        nowh,noww = q.popleft()
        if s[nowh][noww] == '.':
            target_mark = '
            white +=1
        else:
            target_mark = '.'
            black +=1
        if nowh >0 and s[nowh-1][noww] == target_mark and dp[nowh-1][noww]==0:
            q.append((nowh-1,noww))
            dp[nowh-1][noww]=1
        if nowh <H-1 and s[nowh+1][noww] == target_mark and dp[nowh+1][noww]==0:
            q.append((nowh+1,noww))
            dp[nowh+1][noww]=1
        if noww > 0 and s[nowh][noww-1] == target_mark and dp[nowh][noww-1]==0:
            q.append((nowh,noww-1))
            dp[nowh][noww-1]=1
        if noww < W-1 and s[nowh][noww+1] == target_mark and dp[nowh][noww+1]==0:
            q.append((nowh,noww+1))
            dp[nowh][noww+1]=1
            
    return black*white

cnt = 0

start_candi = []
end_candi = []
for ih in range(H):
    for iw in range(W):
        if s[ih][iw] == '
            start_candi.append((ih,iw))
        else:
            end_candi.append((ih,iw))

for ih in range(H):
    for iw in range(W):
        if dp[ih][iw] == 0:
            start = (ih,iw)
            cnt += isOK(start)
        else:
            continue

print(cnt)

Solution (Python):
def root(x):
    i,j = x[0],x[1]
    if (i,j) == p[i][j]:
        return (i,j)
    y = root(p[i][j])
    p[i][j]=y
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    pxi,pxj= px[0],px[1];pyi,pyj= py[0],py[1];
    rx = rank[pxi][pxj]; ry = rank[pyi][pyj]
    if ry < rx:
        p[pyi][pyj] = px
    elif rx < ry:
        p[pxi][pxj] = py
    else:
        p[pyi][pyj] = px
        rank[pxi][pxj] += 1
    return 1

h,w = map(int, input().split( ))
s = ["x"*(w+2)]+["x"+input()+"x" for _ in range(h)]+["x"*(w+2)]
p = [[(i,j) for j in range(w+2)] for i in range(h+2)]
rank = [[1]*(w+2) for _ in range(h+2)]

tonari = [(-1,0),(1,0),(0,1),(0,-1)]
for i in range(1,h+1):
    for j in range(1,w+1):
        for di,dj in tonari:
            i2 = i+di;j2 = j+dj
            if (s[i][j],s[i2][j2])==("
                unite((i,j),(i2,j2))
c = [[p[i][j] for j in range(1,w+1)] for i in range(1,h+1)]
ans = 0

for i in range(h+2):
    for j in range(w+2):
        root((i,j))
pb = {}
pw = {}

for i in range(h):
    for j in range(w):
        k = c[i][j]
        if s[i+1][j+1] =="
            if root(k) in pb:
                pb[root(k)]+=1
            else:
                pb[root(k)]=1
        elif s[i+1][j+1]==".":
            if root(k) in pw:
                pw[root(k)]+=1
            else:
                pw[root(k)]=1
ans = 0
c2 =  set([p[i][j] for j in range(w+2) for i in range(h+2)])

for k in c2:
    if k in pb and k in pw:
        ans += pb[k]*pw[k]
print(ans)

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]

def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0
  visited=[[False]*w for _ in range(h)]
  for i in range(h):
    for j in range(w):
      if visited[i][j]:
        continue
      if field[i][j]!='
        continue
      q=collections.deque()
      q.append((i,j))
      b=0
      wh=0
      while q:
        y,x=q.popleft()
        if visited[y][x]:
          continue
        if field[y][x]=='
          b+=1
        else:
          wh+=1
        visited[y][x]=True
        for dy,dx in dd:
          ny=y+dy
          nx=x+dx
          if not (0<=ny<h and 0<=nx<w):
            continue
          if field[y][x]==field[ny][nx]:
            continue
          if visited[ny][nx]:
            continue
          q.append((ny,nx))
      ans+=b*wh
      
  return ans


print(main())

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    H, W = LI()
    S = [SS() for _ in range(H)]

    d = ((1, 0), (0, 1), (-1, 0), (0, -1))

    def dfs(cy, cx, cnt):
        visited[cy][cx] = True
        if S[cy][cx] == '
            cnt[0] += 1
        else:
            cnt[1] += 1
        for dy, dx in d:
            ny = cy + dy
            nx = cx + dx
            if 0 <= ny < H and 0 <= nx < W and not visited[ny][nx] and S[ny][nx] != S[cy][cx]:
                dfs(ny, nx, cnt)

    
    c = []
    visited = [[False] * W for _ in range(H)]
    for i, j in itertools.product(range(H), range(W)):
        if not visited[i][j]:
            cnt = [0, 0]
            dfs(i, j, cnt)
            c.append(cnt)

    ans = sum([b * w for b, w in c])
    print(ans)

if __name__ == '__main__':
    resolve()

Solution (Python):
import networkx as nx

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

G = nx.Graph()
G.add_nodes_from([(h, w) for h in range(H) for w in range(W)])
for h in range(H - 1):
    for w in range(W):
        if S[h][w] != S[h + 1][w]:
            G.add_edge((h, w), (h + 1, w))
for h in range(H):
    for w in range(W - 1):
        if S[h][w] != S[h][w + 1]:
            G.add_edge((h, w), (h, w + 1))

ans = 0
for component in nx.connected_components(G):
    black, white = 0, 0
    for h, w in component:
        if S[h][w] == '
            black += 1
        else:
            white += 1
    ans += black * white
print(ans)

Solution (Python):
def I(): return int(input())
def MI(): return map(int, input().split())
def SI(): return input().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):
        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=MI()
uf=UnionFind(h*w)
lis=[[0]*w for i in range(h)]
for i in range(h):
    s=SI()
    for j in range(w):
        if s[j]=="
            lis[i][j]=1
step=[[0,1],[0,-1],[-1,0],[1,0]]
for i in range(h):
    for j in range(w):
        for x,y in step:
            if not (0<=i+x<h and 0<=j+y<w):
                continue
            if lis[i][j]!=lis[i+x][j+y]:
                uf.union(w*i+j,w*(i+x)+(j+y))
ans=0
dic=defaultdict(lambda:[0,0])
for i in range(h):
    for j in range(w):
        dic[uf.find(w*i+j)][lis[i][j]==1]+=1
for p in dic.keys():
    ans+=dic[p][0]*dic[p][1]
print(ans)

Solution (Python):
def I(): return int(input())
def MI(): return map(int, input().split())
def SI(): return input().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):
        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=MI()
uf=UnionFind(h*w)
lis=[[0]*w for i in range(h)]
for i in range(h):
    s=SI()
    for j in range(w):
        if s[j]=="
            lis[i][j]=1
step=[[0,1],[0,-1],[-1,0],[1,0]]
for i in range(h):
    for j in range(w):
        for x,y in step:
            if not (0<=i+x<h and 0<=j+y<w):
                continue
            if lis[i][j]!=lis[i+x][j+y]:
                uf.union(w*i+j,w*(i+x)+(j+y))
ans=0
dic=defaultdict(lambda:[0,0])
for i in range(h):
    for j in range(w):
        dic[uf.find(w*i+j)][lis[i][j]==1]+=1
for p in dic.keys():
    ans+=dic[p][0]*dic[p][1]
print(ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input().rstrip())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7
    
    
    
    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()}
    
        def __str__(self):
            return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    
    h,w=MI()
    uf=UnionFind(h*w)
    lis=[[0]*w for i in range(h)]
    for i in range(h):
        s=SI()
        for j in range(w):
            if s[j]=="
                lis[i][j]=1
    step=[[0,1],[0,-1],[-1,0],[1,0]]
    for i in range(h):
        for j in range(w):
            for x,y in step:
                if not (0<=i+x<h and 0<=j+y<w):
                    continue
                if lis[i][j]!=lis[i+x][j+y]:
                    uf.union(w*i+j,w*(i+x)+(j+y))
    ans=0
    dic=defaultdict(lambda:[0,0])
    for i in range(h):
        for j in range(w):
            dic[uf.find(w*i+j)][lis[i][j]==1]+=1
    for p in dic.keys():
        ans+=dic[p][0]*dic[p][1]
    print(ans)
if __name__=="__main__":
    main()

Solution (Python):
from collections import defaultdict


class UnionFind:
    def __init__(self, node):
        self.parent = [-1 for _ in range(node)]
        self.node = node

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

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

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

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

    def get_root(self):
        return [i for i, root in enumerate(self.parent) if root < 0]

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

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


def main():
    h, w = map(int, input().split())
    grid = [["*" for _ in range(w + 2)]]
    for _ in range(h):
        grid.append(["*"] + list(input()) + ["*"])
    grid.append(grid[0])
    uf = UnionFind(h * w)
    all_black = []

    def grid_num(i, j):
        return w * (i - 1) + j - 1

    for i in range(1, h + 1):
        for j in range(1, w + 1):
            for di, dj in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
                ni = i + di
                nj = j + dj
                if grid[ni][nj] == "*":
                    continue
                elif grid[i][j] != grid[ni][nj]:
                    uf.union(grid_num(i, j), grid_num(ni, nj))
            if grid[i][j] == "
                all_black.append([i, j])
    ans = 0

    black = defaultdict(int)
    for i, j in all_black:
        black[uf.find(grid_num(i, j))] += 1
    for i, r in enumerate(uf.parent):
        if r < 0:
            ans += black[i] * (-r - black[i])
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
'''
自宅用PCでの解答
'''
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
alp = "abcdefghijklmnopqrstuvwxyz"
dir = [(-1,0),(0,-1),(1,0),(0,1)]


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()}
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    h,w = map(int,ipt().split())
    brd = [input()+"-" for i in range(h)]
    brd.append("-"*(w+1))
    d = {"
    al = [True]*(h*w)
    ans = 0

    for i in range(h):
        for j in range(w):
            if al[i*w+j]:
                q = [(i,j)]
                al[i*w+j] = False
                nm = [0,0]
                nm[d[brd[i][j]]] += 1
                while q:
                    qi,qj = q.pop()
                    qs = d[brd[qi][qj]]
                    for di,dj in dir:
                         ni = qi+di
                         nj = qj+dj
                         if d[brd[ni][nj]] == 1-qs and al[ni*w+nj]:
                             al[ni*w+nj] = False
                             nm[1-qs] += 1
                             q.append((ni,nj))
                ans += nm[0]*nm[1]

    print(ans)





    return None

if __name__ == '__main__':
    main()

Solution (Python):
h,w=map(int,input().split())

maze=[list(input()) for _ in range(h)]

group=[[0]*w for _ in range(h)]

group_no=0
color_cnt=[]

for y in range(h):
    for x in range(w):
        if group[y][x]==0:
            stack=[(y,x)]
            group_no+=1

            color_cnt_tmp=[0,0]

            while len(stack)>0:
                tmp=stack.pop()
                group[tmp[0]][tmp[1]]=group_no
                
                if maze[tmp[0]][tmp[1]]=="
                    color_cnt_tmp[0]+=1
                else:
                    color_cnt_tmp[1]+=1

                for (ny,nx) in [(0,1),(1,0),(-1,0),(0,-1)]:
                    my=ny+tmp[0]
                    mx=nx+tmp[1]
                    if 0<=my<h and 0<=mx<w:
                        if group[my][mx]==0:
                            if maze[tmp[0]][tmp[1]]!=maze[my][mx]:
                                stack.append((my,mx))
                                group[my][mx]=group_no
            color_cnt.append(color_cnt_tmp)

ans=0
for (b,w) in color_cnt:
    ans+=b*w

print(ans)

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import deque

    h, w = map(int, readline().split())
    grid = [["!"] * (w + 2)]
    for _ in range(h):
        s = ["!"] + list(input()) + ["!"]
        grid.append(s)
    grid.append(["!"] * (w + 2))

    ans = 0
    for row in range(1, h + 1):
        for col in range(1, w + 1):
            if grid[row][col] != "!":
                black, white = 0, 0
                que = deque()
                que.append((row, col))
                while que:
                    cr, cc = que.popleft()
                    if grid[cr][cc] == "
                        black += 1
                        if grid[cr + 1][cc] == ".":
                            que.append((cr + 1, cc))
                        if grid[cr - 1][cc] == ".":
                            que.append((cr - 1, cc))
                        if grid[cr][cc + 1] == ".":
                            que.append((cr, cc + 1))
                        if grid[cr][cc - 1] == ".":
                            que.append((cr, cc - 1))
                    elif grid[cr][cc] == ".":
                        white += 1
                        if grid[cr + 1][cc] == "
                            que.append((cr + 1, cc))
                        if grid[cr - 1][cc] == "
                            que.append((cr - 1, cc))
                        if grid[cr][cc + 1] == "
                            que.append((cr, cc + 1))
                        if grid[cr][cc - 1] == "
                            que.append((cr, cc - 1))
                    grid[cr][cc] = "!"

                ans += white * black
    print(ans)


if __name__ == '__main__':
    main()

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



n = h*w

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

def Unite(x, y, par, rank):
    x = Find(x, par)
    y = Find(y, par)

    if x != y:
        if rank[x] < rank[y]:
            par[y] += par[x]
            par[x] = y
        else:
            par[x] += par[y]
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

def Same(x, y, par):
    return Find(x, par) == Find(y, par)

def Size(x, par):
    return -par[Find(x, par)]

par = [-1]* n
rank = [0]*n

for y in range(h):
    for x in range(w):
        idx1 = y*w+x
        for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
            ny, nx = y+dy, x+dx
            if 0 <= ny < h and 0 <= nx < w:
                idx2 = ny*w+nx
                if S[y][x] != S[ny][nx]:
                    Unite(idx1, idx2, par, rank)

ans = 0

X = [[0, 0] for _ in range(n)]
K = []

for i in range(n):
    y, x = divmod(i, w)
    if par[i] < 0:
        K.append(i)
        if S[y][x] == '
            X[i][0] += 1
        else:
            X[i][1] += 1
    else:
        if S[y][x] == '
            X[Find(i, par)][0] += 1
        else:
            X[Find(i, par)][1] += 1

ans = 0
for k in K:
    ans += X[k][0]*X[k][1]
print(ans)

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



n = h*w

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

def Unite(x, y, par, rank):
    x = Find(x, par)
    y = Find(y, par)

    if x != y:
        if rank[x] < rank[y]:
            par[y] += par[x]
            par[x] = y
        else:
            par[x] += par[y]
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

def Same(x, y, par):
    return Find(x, par) == Find(y, par)

def Size(x, par):
    return -par[Find(x, par)]

par = [-1]* n
rank = [0]*n

for y in range(h):
    for x in range(w):
        idx1 = y*w+x
        for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
            ny, nx = y+dy, x+dx
            if 0 <= ny < h and 0 <= nx < w:
                idx2 = ny*w+nx
                if S[y][x] != S[ny][nx]:
                    Unite(idx1, idx2, par, rank)

ans = 0

X = [[0, 0] for _ in range(n)]
K = []

for i in range(n):
    y, x = divmod(i, w)
    if par[i] < 0:
        K.append(i)
        if S[y][x] == '
            X[i][0] += 1
        else:
            X[i][1] += 1
    else:
        if S[y][x] == '
            X[Find(i, par)][0] += 1
        else:
            X[Find(i, par)][1] += 1

ans = 0
for k in K:
    ans += X[k][0]*X[k][1]
print(ans)