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):
def solve(H, W, grid):
    from collections import deque
    groups = [[0] * W for h in range(H)]
    v = 0 
    def search(M, h0, w0):
        nonlocal v
        count = [0, 0]
        Q = [(h0, w0)]
        groups[h0][w0] = M
        v+=1
        while Q:
            (h, w) = Q.pop()
            c = 1 - grid[h][w]
            count[1-c] += 1
            if h < H-1:
                if groups[h+1][w] == 0:
                    if grid[h+1][w] == c:
                        groups[h+1][w] = M
                        v += 1
                        Q.append((h+1, w))
                    else:
                        q.append((h+1, w))
            if h > 0:
                if groups[h-1][w] == 0:
                    if grid[h-1][w] == c:
                        groups[h-1][w] = M
                        v += 1
                        Q.append((h-1, w))
                    else:
                        q.append((h-1, w))
            if w > 0:
                if groups[h][w-1] == 0:
                    if grid[h][w-1] == c:
                        groups[h][w-1] = M
                        v += 1
                        Q.append((h, w-1))
                    else:
                        q.append((h, w-1))
            if w < W-1:
                if groups[h][w+1] == 0:
                    if grid[h][w+1] == c:
                        groups[h][w+1] = M
                        v += 1
                        Q.append((h, w+1))
                    else:
                        q.append((h, w+1))
        
        return count

    answer = 0
    m = 0
    q = deque()
    q.append((0,0))
    while q:
        h, w = q.pop()
        if groups[h][w] == 0:
            m+=1
            b, w = search(m, h, w)
            answer += b * w
    
    return answer

def main():
    import sys
    input = sys.stdin.readline
    H, W = map(int, input().split())

    grid = [[0]]*H
    for i in range(H):
        grid[i] = [1 if c == '
    print(solve(H, W, grid))

main()

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

h,w = map(int, input().split())
board = [[int(j=="
dxdy = [(0,1), (0,-1), (1,0), (-1,0)]

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

used = [[0]*w for i in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if used[i][j]:
            continue
        k = [0]*2
        dfs(i,j,k, -1)
        ans += k[0]*k[1]
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

h,w = map(int, input().split())
board = [[int(j=="
dxdy = ((0,1), (0,-1), (1,0), (-1,0))

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

used = [[0]*w for i in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if used[i][j]:
            continue
        k = [0]*2
        dfs(i,j,k, -1)
        ans += k[0]*k[1]
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

h,w = map(int, input().split())
board = [[int(j=="
dxdy = [[0,1], [0,-1], [1,0], [-1,0]]

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

used = [[0]*w for i in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if used[i][j]:
            continue
        k = [0]*2
        dfs(i,j,k, -1)
        ans += k[0]*k[1]
print(ans)

Solution (Python):
import sys,bisect,heapq

mod = 10**9+7

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return(list(sys.stdin.readline())[:-1])

def GCD(a,b):
    while(a%b != 0):
        a,b = b,a%b
    return b

def LCM(a,b):
    return a*b//GCD(a,b)

def main():
    H,W = LI()
    a = [[c=="
    b = [[True for _ in range(W)] for _ in range(H)]

    r = 0
    for h in range(H):
        for w in range(W):
            if b[h][w]:
                q = []
                T = 0
                F = 0
                q.append([a[h][w],h,w])
                while(q):
                    flag,h_s,w_s = q.pop()
                    if b[h_s][w_s] and a[h_s][w_s] == flag:
                        if flag:
                            T += 1
                        else:
                            F += 1
                        b[h_s][w_s] = False
                        for i in [[-1,0],[1,0],[0,-1],[0,1]]:
                            if 0<=h_s+i[0]<=H-1 and 0<=w_s+i[1]<=W-1 and b[h_s+i[0]][w_s+i[1]]:
                                q.append([not(flag),h_s+i[0],w_s+i[1]])
                r += T*F
    return r




if __name__ == "__main__":
    print(main())

Solution (Python):
H, W = map(int, input().split())
S = []
for i in range(H):
  ss = input()
  S.append(ss)
UF = list(range(H*W))
def par(m):
  if UF[m] == m:
    return m
  r = par(UF[m])
  UF[m] = r
  return r
def unite(m, n):
  i = par(m)
  j = par(n)
  UF[i] = j
for i in range(H):
  for j in range(W):
    if i+1 < H and S[i][j] != S[i+1][j]:
      unite(i*W+j, (i+1)*W+j)
    if j+1 < W and S[i][j] != S[i][j+1]:
      unite(i*W+j, i*W+j+1)
nsb = [0]*(H*W)
nsw = [0]*(H*W)
for i in range(H):
  for j in range(W):
    p = par(i*W+j)
    if S[i][j] == "
      nsb[p] += 1
    if S[i][j] == ".":
      nsw[p] += 1
r = 0
for p in range(H*W):
  r += nsb[p]*nsw[p]
print(r)

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
import collections
import itertools
import operator


class UnionFind:
    def __init__(self, x):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)
        self.size = collections.defaultdict(lambda: 1)
        if x is not None:
            for elem in range(x+1):
                _, _, _ = self.parent[elem], self.rank[elem],self.size[elem]

    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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if not self.are_same(x,y):
            xx = self.size[x]
            yy = self.size[y]
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += xx
            else:
                self.parent[y] = x
                self.size[x] += yy
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

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

    def are_same(self, x, y):
        '''print(x,y,self.find(x),self.find(y),self.find(x) == self.find(y))'''
        return self.find(x) == self.find(y)

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield [x for x, _ in group]


h,w = m()
uf = UnionFind(h*w-1)
s = [list(input()) for i in range(h)]


for i in range(h):
    for j in range(w):
        if i == h - 1 and j == w - 1:
            continue
        elif i == h - 1:
            if s[i][j] != s[i][j+1]:
                uf.unite(i*w + j,i*w + j+1)
        elif j == w - 1:
            if s[i][j] != s[i+1][j]:
                uf.unite(i*w + j,(i+1)*w + j)
        else:
            if s[i][j] != s[i+1][j]:
                uf.unite(i*w + j,(i+1)*w + j)
            if s[i][j] != s[i][j+1]:
                uf.unite(i*w + j,i*w + j+1)
kkk = list(uf.grouper())
ans = 0

for i in range(len(kkk)):
    black = 0
    white = 0
    for j in kkk[i]:
        if s[j//w][j%w] == ".":
            white += 1
        else:
            black += 1
    ans += black*white
print(ans)

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

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

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

ans = 0
for i in range(H):
    for j in range(W):
        if checked[i][j]:
            continue
        checked[i][j] =  True
        cnt_b = 0
        cnt_w = 0
        if S[i][j] == "
            cnt_b += 1
        else:
            cnt_w += 1
        stack = es[(i,j)]

        while True:
            ns = []
            for p,q in stack:
                
                if checked[p][q] == False:
                    checked[p][q] = True
                    if S[p][q] == "
                        cnt_b += 1
                    else:
                        cnt_w += 1
                    ns.extend(es[(p,q)])

                
            if len(ns) == 0:
                break
            else:
                stack = ns
        ans += cnt_b * cnt_w

print(ans)

Solution (Python):
"""
prd_xxxさんの解答に自分向けにコメントを付けただけ
https://atcoder.jp/contests/aising2019/submissions/3986546
"""

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

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


uf = UnionFind(H*W)


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


for i in range(H*W):
    uf.root(i)

c1 = Counter()
c2 = Counter()

for i in range(H):
    for j in range(W):
        k = i*W + j
        
        if S[i][j] == ".":
            c1[uf.root(k)] += 1
        else:
            c2[uf.root(k)] += 1

ans = 0
for k in c1.keys():
    
    ans += c1[k] * c2[k]

print(ans)

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

def unite(node_a, node_b):
    root_a, depth_a = node_a.root()
    root_b, depth_b = node_b.root()
    if root_a == root_b:
        return
    elif depth_a >= depth_b:
        root_b.is_root = False
        root_b.parent = root_a
        root_a.white += root_b.white
        root_a.black += root_b.black
    else:
        root_a.is_root = False
        root_a.parent = root_b
        root_b.white += root_a.white
        root_b.black += root_a.black

class Node:
    def __init__(self, color):
        self.parent = None
        self.is_root = True
        self.white = 1 if color == 0 else 0
        self.black = 1 if color == 1 else 0
    
    def root(self):
        node = self
        depth = 0
        while not node.is_root:
            node = node.parent
            depth += 1
        return node, depth

def main():
    H, W = map(int, input().split())
    s = [input().strip() for i in range(H)]
    
    nodes = [[Node(0 if s[j][i] == "." else 1) for i in range(W)] for j in range(H)]

    for y in range(H):
        for x in range(W):
            now = s[y][x]
            for nx, ny in [(x, y-1), (x+1, y), (x, y+1), (x-1, y)]:
                if 0 <= nx and nx < W and 0 <= ny and ny < H:
                    if s[ny][nx] != now:
                        unite(nodes[y][x], nodes[ny][nx])
    
    ans = 0
    
    for y in range(H):
        for x in range(W):
            if nodes[y][x].is_root:
                
                node = nodes[y][x]
                ans += node.white * node.black
    print(ans)
    


if __name__ == "__main__":
    main()

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

def unite(node_a, node_b):
    root_a, depth_a = node_a.root()
    root_b, depth_b = node_b.root()
    if root_a == root_b:
        return
    elif depth_a >= depth_b:
        root_b.is_root = False
        root_b.parent = root_a
        root_a.white += root_b.white
        root_a.black += root_b.black
    else:
        root_a.is_root = False
        root_a.parent = root_b
        root_b.white += root_a.white
        root_b.black += root_a.black

class Node:
    def __init__(self, color):
        self.parent = None
        self.is_root = True
        self.white = 1 if color == 0 else 0
        self.black = 1 if color == 1 else 0
    
    def root(self):
        node = self
        depth = 0
        while not node.is_root:
            node = node.parent
            depth += 1
        return node, depth

def main():
    H, W = map(int, input().split())
    s = [input().strip() for i in range(H)]
    
    nodes = [[Node(0 if s[j][i] == "." else 1) for i in range(W)] for j in range(H)]

    for y in range(H):
        for x in range(W):
            now = s[y][x]
            for nx, ny in [(x, y-1), (x+1, y), (x, y+1), (x-1, y)]:
                if 0 <= nx and nx < W and 0 <= ny and ny < H:
                    if s[ny][nx] != now:
                        unite(nodes[y][x], nodes[ny][nx])
    
    ans = 0
    
    for y in range(H):
        for x in range(W):
            if nodes[y][x].is_root:
                
                node = nodes[y][x]
                ans += node.white * node.black
    print(ans)
    


if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict

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

def union(tab, a, b):
    pa, pb = (find(tab, a), find(tab, b))
    if pa!=pb:
        tab[pb] = pa

H,W=map(int,input().split())
S=[input() for _ in range(H)]
N=H*W
tab = [-1]*N

for y in range(H):
    for x in range(W):
        for dx,dy in [(-1,0),(1,0),(0,1),(0,-1)]:
            xx=x+dx
            yy=y+dy
            if xx < 0 or xx>=W or yy<0 or yy>=H:
                continue
            src = W*y+x
            dst = W*yy+xx
            if S[y][x]!=S[yy][xx]:
                union(tab, src, dst)
dic = defaultdict(lambda: {"
for i in range(N):
    p = find(tab, i)
    t = S[i//W][i%W]
    dic[p][t]+=1

ans = 0
for d in dic.values():
    ans += (d["
print(ans)

Solution (Python):
from collections import deque
from collections import defaultdict

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

class UnionFind :
    def __init__(self, size) :
        """
        Parameters
        ---
        size : int
            頂点数
        """
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        """
        親のインデックスの取得

        Parameters
        ---
        index : int
            取得する頂点のインデックス

        Returns
        ---
        rootIndex : int
            指定した頂点の根のインデックス
        """
        if self.parent[index] == index :  
            return index
        rootIndex = self.root(self.parent[index])  
        self.parent[index] = rootIndex  
        return rootIndex

    def union(self, index1, index2) :  
        """
        木の結合

        Parameters
        ---
        index1 : int
        index2 : int
            結合する頂点のインデックス
        """
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  
            return

        self.component -= 1  

        if self.height[root1] < self.height[root2] :
            self.parent[root1] = root2  
            self.size[root2] += self.size[root1]
        else :
            self.parent[root2] = root1  
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2] :
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2) :
        """
        同じ木に属するかを判定する

        Parameters
        ---
        index1 : int
        index2 : int

        Returns
        ---
        boolean
        """
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        """
        指定した頂点の属する木の大きさを取得する
        """
        return self.size[self.root(index)]

    def getComponent(self) :
        """
        連結成分数を取得する
        """
        return self.component

tree = UnionFind(H * W)
visited = [[False] * W for _ in range(H)]

def f(h, w):
    return h * W + w

def search(h, w):
    que = deque([(h, w)])

    while que:
        nh, nw = que.popleft()
        if visited[nh][nw]:
            continue
        visited[nh][nw] = True
        tree.union(f(h, w), f(nh, nw))
        if nh > 0 and chart[nh][nw] != chart[nh - 1][nw]:
            que.append((nh - 1, nw))
        if nh < H - 1 and chart[nh][nw] != chart[nh + 1][nw]:
            que.append((nh + 1, nw))
        if nw > 0 and chart[nh][nw] != chart[nh][nw - 1]:
            que.append((nh, nw - 1))
        if nw < W - 1 and chart[nh][nw] != chart[nh][nw + 1]:
            que.append((nh, nw + 1))

cntBW = defaultdict(lambda : [0, 0])

for h in range(H):
    for w in range(W):
        if tree.root(f(h, w)) == f(h, w) and chart[h][w] == '
            search(h, w)

for h in range(H):
    for w in range(W):
        if chart[h][w] == '
            cntBW[tree.root(f(h, w))][0] += 1
        else:
            cntBW[tree.root(f(h, w))][1] += 1

ans = 0

for black, white in cntBW.values():
    ans += black * white

print(ans)

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


avail = [[True]*w for _ in range(h)]


def search(i,j,data):
    if S[i][j] == "
        data[0] += 1
    else:
        data[1] += 1
    avail[i][j] = False

    if i+1 < h and S[i+1][j] != S[i][j] and avail[i+1][j]:
        search(i+1,j,data)
    if j+1 < w and S[i][j+1] != S[i][j] and avail[i][j+1]:
        search(i,j+1,data)
    if i > 0 and S[i][j] != S[i-1][j] and avail[i-1][j]:
        search(i-1,j,data)
    if j > 0 and S[i][j] != S[i][j-1] and avail[i][j-1]:
        search(i,j-1,data)

ans = 0
for i in range(h):
    for j in range(w):
        if avail[i][j]:
            data = [0,0]
            search(i,j,data)
            ans+= data[0]*data[1]
            

print(ans)

Solution (Python):

from collections import deque, defaultdict
import copy
import bisect

import math
import heapq


import sys
def input():
	return sys.stdin.readline().strip()

H, W = list(map(int, input().split()))
S = []
for i in range(H):
	S.append(list(input()))
for i in range(H):
	for j in range(W):
		if S[i][j] == '
			S[i][j] = 0
		else:
			S[i][j] = 1

judge = [[0]*W for i in range(H)]
dxy = [[0,1],[1,0],[-1,0],[0,-1]]

total = 0
for i in range(H):
	for j in range(W):
		if judge[i][j] == 0:
			black = 0
			white = 0
			que = deque()
			que.append([i, j])
			judge[i][j] = 1
			black += S[i][j] ^ 1
			white += S[i][j]
			
			while len(que) > 0:
				loc = que.popleft()
				for n in range(4):
					loc_new = [loc[0] + dxy[n][0], loc[1] + dxy[n][1]]
					if loc_new[0] >= 0 and loc_new[0] < H and loc_new[1] >= 0 and loc_new[1] < W:
						if judge[loc_new[0]][loc_new[1]] == 0 and S[loc[0]][loc[1]] ^ S[loc_new[0]][loc_new[1]] == 1:
							judge[loc_new[0]][loc_new[1]] = 1
							black += S[loc_new[0]][loc_new[1]] ^ 1
							white += S[loc_new[0]][loc_new[1]]
							que.append(loc_new)
			total += black * white
			

print(total)

Solution (Python):



import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


dx,dy = [1,0,-1,0],[0,1,0,-1]
h,w = LI()
s = [input() for _ in range(h)]
que = deque()
ch = [[-1]*w for _ in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '
            if ch[i][j] < 0:
                ch[i][j] = 0
                que = deque()
                que.append((i,j))
                
                
                a,b = 1,0
                while que:
                    y,x = que.popleft()
                    for k in range(4):
                        nx,ny = x + dx[k], y + dy[k]
                        if 0 <= nx < w and 0 <= ny < h and ch[ny][nx] < 0:
                            if s[y][x] != s[ny][nx]:
                                if s[ny][nx] == '
                                    a += 1
                                else:
                                    b += 1
                                ch[ny][nx] = 0
                                que.append((ny,nx))
                ans += a*b
print(ans)

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

from collections import defaultdict

H,W = map(int,input().split())
grid = '*' * (W+2)
for _ in range(H):
    grid += '*' + input().rstrip() + '*'
grid += '*' * (W+2)

move = [1,-1,W+2,-(W+2)]

root = [None if x == '*' else -1 for x in grid]

answer = 0
for i in range((H+2)*(W+2)):
    if root[i] != -1:
        continue
    q = [i]
    root[i] = i
    counter = defaultdict(int)
    while q:
        x = q.pop()
        counter[grid[x]] += 1 
        for dx in move:
            y = x + dx
            if root[y] != -1:
                continue
            if grid[x] == grid[y]:
                continue
            root[y] = i
            q.append(y)
    answer += counter['.'] * counter['

print(answer)

Solution (Python):
from collections import deque

H, W = map(int, input().split())
S = []
for i in range(H):
    s = input()
    temp = []
    for j in range(W):
        temp.append(s[j])
    S.append(temp)

ret = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != '?':
            q = deque()
            q.appendleft((i, j))
            white = 0
            black = 0
            while q:
                h, w= q.pop()
                color = S[h][w]
                if color == '?':
                    continue
                elif color == '
                    black += 1
                else:
                    white += 1
                S[h][w] = '?'
                cand = [(h+1, w), (h-1, w), (h, w+1), (h, w-1)]
                for hc, wc in cand:
                    if 0 <= hc < H and 0 <= wc < W and (S[hc][wc] not in [color, '?']):
                        q.appendleft((hc, wc))

            ret += black * white

print(ret)

Solution (Python):
import itertools
import itertools
import os
import sys
from collections import deque

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

H, W = list(map(int, sys.stdin.readline().split()))
S = [list(sys.stdin.readline().rstrip()) for _ in range(H)]
seen = np.zeros((H, W), dtype=bool)

ans = 0
for h, w in itertools.product(range(H), range(W)):
    if seen[h][w]:
        continue
    que = deque()
    que.append((h, w))
    black = white = 0
    while que:
        h, w = que.popleft()
        if seen[h][w]:
            continue
        seen[h][w] = True
        if S[h][w] == '
            black += 1
        else:
            white += 1
        for dh, dw in zip((h + 1, h - 1, h, h), (w, w, w + 1, w - 1)):
            if 0 <= dh < H and 0 <= dw < W and not seen[dh][dw]:
                if S[h][w] != S[dh][dw]:
                    que.append((dh, dw))
    ans += black * white
print(ans)

Solution (Python):
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np
from scipy.misc import comb

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

H, W = list(map(int, sys.stdin.readline().split()))
S = [list(sys.stdin.readline().rstrip()) for _ in range(H)]
seen = np.zeros((H, W), dtype=bool)


def dfs(h, w):
    if seen[h][w]:
        return 0, 0
    seen[h][w] = True
    black = int(S[h][w] == '
    white = int(S[h][w] == '.')
    for dh, dw in zip([h, h, h + 1, h - 1], [w + 1, w - 1, w, w]):
        if 0 <= dh < H and 0 <= dw < W:
            if S[h][w] != S[dh][dw]:
                counts = dfs(dh, dw)
                black += counts[0]
                white += counts[1]
    return black, white


ans = 0
for h, w in itertools.product(range(H), range(W)):
    black, white = dfs(h, w)
    ans += black * white
print(ans)

Solution (Python):
import sys;sys.setrecursionlimit(9**9);h,w=map(int,input().split());b=[[0]*(w+1)]
for i in range(h):
  b.append([0])
  for j in input():b[-1].append(1+(j=="
  b[-1].append(0)
b.append([0]*(w+1));d=[[0,1],[0,-1],[1,0],[-1,0]];a=0
def s(i,j):
  global B;B[b[i][j]-1]+=1;v=b[i][j];b[i][j]=0
  for k in d:
    if v^3==b[i+k[0]][j+k[1]]:s(i+k[0],j+k[1])
for i in range(1,h+1):
  for j in range(1,w+1):B=[0,0];s(i,j);a+=B[0]*B[1]
print(a)

Solution (Python):
import sys;sys.setrecursionlimit(10**9);h,w=map(int,input().split());b=[[0]*(w+1)]
for i in range(h):
  b.append([0])
  for j in input():
    if j==".":b[-1].append(1)
    else:b[-1].append(2)
  b[-1].append(0)
b.append([0]*(w+1));d=[[0,1],[0,-1],[1,0],[-1,0]];a=0
def s(i,j):
  global B;B[b[i][j]-1]+=1;v=b[i][j];b[i][j]=0
  for k in d:
    if v^3!=b[i+k[0]][j+k[1]]:continue
    s(i+k[0],j+k[1])
for i in range(1,h+1):
  for j in range(1,w+1):B=[0,0];s(i,j);a+=B[0]*B[1]
print(a)

Solution (Python):
import sys;sys.setrecursionlimit(10**9)
h,w=map(int,input().split())
b=[[0]*(w+1)]
for i in range(h):
  b.append([0])
  for j in input():
    if j==".":b[-1].append(1)
    else:b[-1].append(2)
  b[-1].append(0)
b.append([0]*(w+1))
d=[[0,1],[0,-1],[1,0],[-1,0]]
a=0
def bfs(i,j):
  global br,wh
  if b[i][j]==0:return
  if b[i][j]==1:wh+=1
  elif b[i][j]==2:br+=1
  v=b[i][j]
  b[i][j]=0
  for k in d:
    if v^3!=b[i+k[0]][j+k[1]]:continue
    bfs(i+k[0],j+k[1])
for i in range(1,h+1):
  for j in range(1,w+1):
    br=wh=0
    bfs(i,j)
    a+=br*wh
print(a)

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

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

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

Solution (Python):
import collections
import sys
sys.setrecursionlimit(1000000)


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


seen = [[False] * W for i in range(H)]
move = ((-1, 0), (1, 0), (0, -1), (0, 1))

q = collections.deque()


def bfs(i, j):
    b, w = 0, 0
    seen[i][j] = True
    q.append((i, j))

    while q:
        ci, cj = q.popleft()

        if S[ci][cj] == '
            b += 1
        else:
            w += 1

        for di, dj in move:
            ni = ci+di
            nj = cj+dj
            if 0 <= ni < H and 0 <= nj < W:
                if seen[ni][nj] is False and S[ci][cj] != S[ni][nj]:
                    seen[ni][nj] = True
                    q.append((ni, nj))

    return b*w


ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '
            ans += bfs(i, j)

print(ans)