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.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.color = [[0] * 2 for _ in range(n)]
        for i in range(n):
            y, x = divmod(i, w)
            if s[y][x] == '
                self.color[i][1] = 1
            else:
                self.color[i][0] = 1

    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
        self.color[x][0] += self.color[y][0]
        self.color[x][1] += self.color[y][1]

    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 = map(int, readline().split())
s = [readline().rstrip().decode() for _ in range(h)]
uf = UnionFind(h * w)
move = [(1, 0), (0, 1), (-1, 0), (0, -1)]
for y, ss in enumerate(s):
    for x, sss in enumerate(ss):
        for dy, dx in move:
            xx = x + dx
            yy = y + dy
            if 0 <= xx < w and 0 <= yy < h and sss != s[yy][xx]:
                uf.union(yy * w + xx, y * w + x)
print(sum(uf.color[root][0] * uf.color[root][1] for root in uf.roots()))

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
class UnionFind():
    def __init__(self, n):
        self.n=n
        self.parents=[-1]*n 
        self.member_color=[[0,0]for _ in range(n)] 
        for i in range(n):
            if S[i//w][i%w]=="
                self.member_color[i][1]=1
            else:
                self.member_color[i][0]=1
    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 unite(self,x,y):
        
        x,y=self.find(x),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 
        self.member_color[x][0]+=self.member_color[y][0]
        self.member_color[x][1]+=self.member_color[y][1] 
    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 all_group_members_list(self):
        
        
        return list(self.all_group_members().values())
    def __str__(self):
        
        return '\n'.join('{}: {}'.format(r,self.members(r)) for r in self.roots())
def main():
    global w,S
    h,w=map(int,input().split())
    S=[input() for _ in range(h)]
    uf=UnionFind(h*w)
    for i in range(h):
        for j in range(w):
            ss=S[i][j]
            for row,col in ((1,0),(-1,0),(0,1),(0,-1)):
                if i+row>=0 and i+row<h and j+col>=0 and j+col<w and ss!=S[i+row][j+col]:
                    uf.unite((i+row)*w+j+col,i*w+j) 
    ans=0
    for r in uf.roots():
        ans+=uf.member_color[r][0]*uf.member_color[r][1]
    print(ans)
if __name__=='__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
class UnionFind():
    def __init__(self, n):
        self.n=n
        self.parents=[-1]*n 
        self.member_color=[[0,0]for _ in range(n)] 
        for i in range(n):
            if S[i//w][i%w]=="
                self.member_color[i][1]=1
            else:
                self.member_color[i][0]=1
    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 unite(self,x,y):
        
        x,y=self.find(x),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 
        self.member_color[x][0]+=self.member_color[y][0]
        self.member_color[x][1]+=self.member_color[y][1] 
    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 all_group_members_list(self):
        
        
        return list(self.all_group_members().values())
    def __str__(self):
        
        return '\n'.join('{}: {}'.format(r,self.members(r)) for r in self.roots())
def main():
    global w,S
    h,w=map(int,input().split())
    S=[input() for _ in range(h)]
    uf=UnionFind(h*w)
    for i in range(h):
        for j in range(w):
            ss=S[i][j]
            for row,col in ((1,0),(-1,0),(0,1),(0,-1)):
                if i+row>=0 and i+row<h and j+col>=0 and j+col<w and ss!=S[i+row][j+col]:
                    uf.unite((i+row)*w+j+col,i*w+j) 
    ans=0
    for r in uf.roots():
        ans+=uf.member_color[r][0]*uf.member_color[r][1]
    print(ans)
if __name__=='__main__':
    main()

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

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    H,W = LI()
    M = [sys.stdin.readline().rstrip() for _ in range(H)]

    c = [[0] * W for _ in range(H)]
    q = collections.deque()
    ans = 0
    for i in range(H):
        for j in range(W):
            if c[i][j]: continue

            black = 0; white = 0
            q.append((i,j,M[i][j]))
            c[i][j] = 1
            while q:
                y,x,s = q.popleft()
                if s == '
                else: white += 1
                for dy,dx in ((0,1),(1,0),(0,-1),(-1,0)):
                    if 0 <= y+dy < H and 0 <= x+dx < W:
                        if c[y+dy][x+dx] or M[y+dy][x+dx] == s: continue
                        c[y+dy][x+dx] = 1
                        q.append((y+dy,x+dx,M[y+dy][x+dx]))
            ans += black * white
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
h,w=map(int,input().split())
maze=[input() for i in range(h)]
class UnionFind:
    
    
    __slots__ = ["_size", "_first_idx", "_parents"]
    def __init__(self, size: int, first_index: int = 0) -> None:
        self._size = size
        self._first_idx = first_index
        self._parents = [[0,0,1] for i in range(size + first_index)]
        for i in range(size):
            self._parents[i][int(maze[i//w][i%w]==".")]=1
    def find(self, x: int) -> int:
        if type(self._parents[x]) is list:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]
    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)
    def unite(self, x: int, y: int) -> bool:
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        if self._parents[x][2] < self._parents[y][2]:
            x, y = y, x
        self._parents[x] = [self._parents[x][i]+self._parents[y][i] for i in range(3)]
        self._parents[y] = x
        return True
ans=0
m=[(0,1),(0,-1),(1,0),(-1,0)]
uf=UnionFind(h*w)
for i in range(h):
    for j in range(w):
        for dx,dy in m:
            if 0<=dx+i<h and 0<=dy+j<w and maze[i][j]!=maze[i+dx][j+dy]:
                uf.unite(i*w+j,(i+dx)*w+j+dy)
for i in uf._parents:
    if type(i)is list:ans+=i[0]*i[1]
print(ans)

Solution (Python):
h,w=map(int,input().split())
maze=[input() for i in range(h)]
class UnionFind:
    
    
    __slots__ = ["_size", "_first_idx", "_parents"]
    def __init__(self, size: int, first_index: int = 0) -> None:
        self._size = size
        self._first_idx = first_index
        self._parents = [[0,0,1] for i in range(size + first_index)]
        for i in range(size):
            self._parents[i][int(maze[i//w][i%w]==".")]=1
    def find(self, x: int) -> int:
        try:
            if type(self._parents[x]) is list:
                return x
        except IndexError:print(x);exit()
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]
    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)
    def unite(self, x: int, y: int) -> bool:
        x, y = self.find(x), self.find(y)

        if x == y:
            return False
        if self._parents[x][2] < self._parents[y][2]:
            x, y = y, x
        self._parents[x] = [self._parents[x][i]+self._parents[y][i] for i in range(3)]
        self._parents[y] = x
        return True
ans=0
m=[(0,1),(0,-1),(1,0),(-1,0)]
uf=UnionFind(h*w)
for i in range(h):
    for j in range(w):
        for dx,dy in m:
            if 0<=dx+i<h and 0<=dy+j<w and maze[i][j]!=maze[i+dx][j+dy]:
                uf.unite(i*w+j,(i+dx)*w+j+dy)
for i in uf._parents:
    if type(i)is list:ans+=i[0]*i[1]
print(ans)

Solution (Python):
H,W=map(int,input().split())

mat=[[x=="


answer=0
visited_set=set()
for i in range(H):
  for j in range(W):
    if not mat[i][j] or (i,j) in visited_set:
      continue      

    queue=[(i,j)]
    d=0
    num_black=num_white=0
    while queue:
      new_queue=set()
      for q in queue:
        ii,jj=q
        visited_set.add((ii,jj))
        if d%2==0:
          num_black+=1
        else:
          num_white+=1
        
        if ii>0 and mat[ii][jj]!=mat[ii-1][jj] and not (ii-1,jj) in visited_set:
          new_queue.add((ii-1,jj))
        if ii<H-1 and mat[ii][jj]!=mat[ii+1][jj] and not (ii+1,jj) in visited_set:
          new_queue.add((ii+1,jj))
        if jj>0 and mat[ii][jj]!=mat[ii][jj-1] and not (ii,jj-1) in visited_set:
          new_queue.add((ii,jj-1))
        if jj<W-1 and mat[ii][jj]!=mat[ii][jj+1] and not (ii,jj+1) in visited_set:
          new_queue.add((ii,jj+1))
          
      queue=list(new_queue)
      d+=1
      
    
    answer+=num_black*num_white

print(answer)

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

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    H, W = map(int, rl().split())
    S = [rl().rstrip() for _ in range(H)]
    
    roots = []
    searched = [[False] * W for _ in range(H)]
    counter = defaultdict(int)
    for i in range(H):
        for j in range(W):
            if searched[i][j]:
                continue
            roots.append((i, j))
            searched[i][j] = True
            sij = S[i][j]
            counter[(i, j, sij == '.')] += 1
            que = deque([(i, j, sij)])
            while que:
                cy, cx, cc = que.popleft()
                for dy, dx in ((-1, 0), (0, 1), (1, 0), (0, -1)):
                    ny, nx = cy + dy, cx + dx
                    if 0 <= ny < H and 0 <= nx < W:
                        if searched[ny][nx]:
                            continue
                        nc = S[ny][nx]
                        if cc == nc:
                            continue
                        searched[ny][nx] = True
                        counter[(i, j, nc == '.')] += 1
                        que.append((ny, nx, nc))
    
    ans = 0
    for i, j in roots:
        ans += counter[(i, j, 0)] * counter[(i, j, 1)]
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(200000)
H,W=map(int,input().split())
S=[input() for i in range(H)]
l=[[0]*(W+2) for i in range(H+2)]
for i in range(1,H+1):
    for j in range(1,W+1):
        l[i][j]=1
a,c=0,1
def nu(h,w):
    global c,b
    if S[h-1][w-1]=="
        b+=1
    if l[h-1][w] and S[h-1][w-1]!=S[h-2][w-1]:
        l[h-1][w]=0
        c+=1
        nu(h-1,w)
    if l[h+1][w] and S[h-1][w-1]!=S[h][w-1]:
        l[h+1][w]=0
        c+=1
        nu(h+1,w)
    if l[h][w-1] and S[h-1][w-1]!=S[h-1][w-2]:
        l[h][w-1]=0
        c+=1
        nu(h,w-1)
    if l[h][w+1] and S[h-1][w-1]!=S[h-1][w]:
        l[h][w+1]=0
        c+=1
        nu(h,w+1)
for i in range(1,H+1):
    for j in range(1,W+2):
        if not l[i][j]:
            continue
        b,c=0,1
        l[i][j]=0
        nu(i,j)
        a+=b*(c-b)
print(a)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
s=[input() for _ in range(h)]
visited=[[True]*w for _ in range(h)]
def bfs(sx,sy):
    q=deque([(sx,sy)])
    visited[sx][sy]=False
    black=1
    white=0
    while q:
        x,y=q.popleft()
        for dx,dy in [[0,1],[1,0],[0,-1],[-1,0]]:
            nx,ny=x+dx,y+dy
            if 0<=nx<h and 0<=ny<w:
                if visited[nx][ny]:
                    if s[x][y]=="
                        visited[nx][ny]=False
                        q.append((nx,ny))
                        white+=1
                    elif s[x][y]=="." and s[nx][ny]=="
                        visited[nx][ny]=False
                        q.append((nx,ny))
                        black+=1
    return black,white
ans=0
for sx in range(h):
    for sy in range(w):
        if s[sx][sy]=="
            black,white=bfs(sx,sy)
            ans+=black*white
print(ans)

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

check = [[False for _ in range(w)]for __ in range(h)]

import queue
q=queue.Queue()
nh = [1,0,-1,0]
nw = [0,1,0,-1]

ans = 0
for i in range(h):
    for j in range(w):
        if check[i][j]:continue
        check[i][j] =True
        cnt = [0]*2
        cnt[s[i][j] == '
        q.put([i,j])
        while not q.empty():
            nowi,nowj = q.get()
            for ne in range(4):
                ni = nowi + nh[ne]
                nj = nowj + nw[ne]
                if ni<0 or h <=ni or nj<0 or w<=nj:continue
                if s[nowi][nowj] == s[ni][nj]:continue
                if check[ni][nj]:continue
                check[ni][nj]=True
                cnt[s[ni][nj]=='
                q.put([ni,nj])
        ans += cnt[0]*cnt[1]
print(ans)

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

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

other_color = {".": "

def dfs(i,j, color):
    num = 0
    black_num = 0
    
    if i != 0:
        if S[i-1][j] == other_color[color] and not visit_flag[i-1][j]:
            visit_flag[i-1][j] = True
            _num, _black_num = dfs(i-1, j, other_color[color])
            num += _num
            black_num += _black_num
            if other_color[color] == "
                black_num += 1
                black_visited_flag[i-1][j] = True
            else:
                num += 1
    if i != H-1:
        if S[i+1][j] == other_color[color] and not visit_flag[i+1][j]:
            visit_flag[i+1][j] = True
            _num, _black_num = dfs(i+1, j, other_color[color])
            num += _num
            black_num += _black_num
            if other_color[color] == "
                black_num += 1
                black_visited_flag[i+1][j] = True
            else:
                num += 1
    if j != 0:
        if S[i][j-1] == other_color[color] and not visit_flag[i][j-1]:
            visit_flag[i][j-1] = True
            _num, _black_num = dfs(i, j -1, other_color[color])
            num += _num
            black_num += _black_num
            if other_color[color] == "
                black_num += 1
                black_visited_flag[i][j-1] = True
            else:
                num += 1
    if j != W-1:
        if S[i][j+1] == other_color[color] and not visit_flag[i][j+1]:
            visit_flag[i][j+1] = True
            _num, _black_num = dfs(i, j+1, other_color[color])
            num += _num
            black_num += _black_num
            if other_color[color] == "
                black_num += 1
                black_visited_flag[i][j+1] = True
            else:
                num += 1
    return num, black_num



ans = 0
visit_flag = [[False] * W for _ in range(H)] 
for i, row in enumerate(S):
    for j, val in enumerate(row):
        if black_visited_flag[i][j] or S[i][j] == ".":
            continue
        num, black_num = dfs(i,j, "
        ans += (num * black_num)

print(ans)

Solution (Python):
from collections import deque
H,W=map(int,input().split())
table=[list(input()) for _ in range(H)]
dp=[[-1 for _ in range(W)] for _ in range(H)]
seen=[[0 for _ in range(W)] for _ in range(H)]
d=deque()
col=0
wlist=[0]*(H*W)
blist=[0]*(H*W)
for i in range(H):
    for j in range(W):
        if dp[i][j]==-1:
            col = i*W+j
            d.append([i,j])
            seen[i][j]=1
        while len(d)>0:
            v=d.popleft()
            x=v[0]
            y=v[1]
            dp[x][y]=col
            if x!=0:
                if (table[x][y]!=table[x-1][y])and(seen[x-1][y]==0):
                    seen[x-1][y]=1
                    d.append([x-1,y])
            if x!=H-1:
                if (table[x][y]!=table[x+1][y])and(seen[x+1][y]==0):
                    seen[x+1][y]=1
                    d.append([x + 1, y])
            if y!=0:
                if (table[x][y]!=table[x][y-1])and(seen[x][y-1]==0):
                    seen[x][y-1]=1
                    d.append([x, y-1])
            if y!=W-1:
                if (table[x][y]!=table[x][y+1])and(seen[x][y+1]==0):
                    seen[x][y+1]=1
                    d.append([x, y+1])
            
            
            
for i in range(H):
    for j in range(W):
        if table[i][j]=="
            blist[dp[i][j]]+=1
        else:
            wlist[dp[i][j]] += 1

cnt=0
for i in range(H*W):
    cnt=cnt+blist[i]*wlist[i]
print(cnt)

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

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

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

        if x == y:
            return

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

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

    def 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]


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


con_comp = UnionFind(H * W)
for i in range(H):
    for j in range(W):
        for (dh, dw) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            if i + dh < 0 or j + dw < 0 or i + dh >= H or j + dw >= W:
                continue
            if S[i][j] != S[i + dh][j + dw]:
                con_comp.union(i * W + j, (i + dh) * W + j + dw)


white = {}
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            if con_comp.find(i * W + j) in white:
                white[con_comp.find(i * W + j)] += 1
            else:
                white[con_comp.find(i * W + j)] = 1


ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '
            ans += white[con_comp.find(i * W + j)]

print(ans)

Solution (Python):
from collections import Counter


class UnionFind:
    def __init__(self, n):
        
        self.n = n
        
        self._root_table = list(range(n))
        
        self._size_table = [1] * n

    def find(self, x):
        """Returns x's root node id."""
        r = self._root_table[x]
        if r != x:
            
            r = self._root_table[x] = self.find(r)
        return r

    def union(self, x, y):
        """Merges two groups."""
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        
        if self._size_table[x] < self._size_table[y]:
            x, y = y, x

        self._size_table[x] += self._size_table[y]
        self._root_table[y] = x

    def size(self, x):
        return self._size_table[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._root_table) if x == i]

    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 = map(int, map(int, input().split()))
grid = []
for i in range(H):
    grid.append(input())
uf = UnionFind(H * W)
for i in range(H):
    for j in range(W):
        nid = i * W + j
        c = grid[i][j]
        if i > 0 and grid[i - 1][j] != c:
            uf.union(nid, (i - 1) * W + j)
        if i < H - 1 and grid[i + 1][j] != c:
            uf.union(nid, (i + 1) * W + j)
        if j > 0 and grid[i][j - 1] != c:
            uf.union(nid, i * W + (j - 1))
        if j < W - 1 and grid[i][j + 1] != c:
            uf.union(nid, i * W + (j + 1))

whites = Counter()
for i in range(H):
    for j in range(W):
        if grid[i][j] == ".":
            whites[uf.find(i * W + j)] += 1
ans = 0
for i in range(H):
    for j in range(W):
        if grid[i][j] == "
            ps = whites[uf.find(i * W + j)]
            ans += ps

print(ans)

Solution (Python):
from collections import deque

def bfs(a, b):
    global dist
    q = deque()
    q.append([a, b])
    bl, wh = 0, 0
    dist[a][b] = 0
    while q:
        p = q.popleft()
        x, y = p[0], p[1]
        if s[x][y] == "
            bl += 1
            for u in v:
                xx, yy = x + u[0], y + u[1]
                if s[xx][yy] == "." and dist[xx][yy] == -1:
                    dist[xx][yy] = dist[x][y] + 1
                    q.append([xx, yy])
        else:
            wh += 1
            for u in v:
                xx, yy = x + u[0], y + u[1]
                if s[xx][yy] == "
                    dist[xx][yy] = dist[x][y] + 1
                    q.append([xx, yy])
    return bl * wh

h, w = map(int, input().split())
s = [["$"] + list(input()) + ["$"] for _ in range(h)]
t = ["$"] * (w + 2)
s.insert(0, t)
s.append(t)
dist = [[-1] * (w + 2) for _ in range(h + 2)]
v = [[1, 0], [-1, 0], [0, 1], [0, -1]]
ans = 0
for i in range(1, h + 1):
    for j in range(1, w + 1):
        if dist[i][j] == -1:
            ans += bfs(i, j)
print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        '木の初期化をする'
        self.p = [-1] * n
        self.rank = [1]*n
        self.b = [0]*n
        self.w = [0]*n
        self.parent = set(range(n))

    def find(self, x):
        'x の親を返す'
        if self.p[x] == -1:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def unite(self, x, y):
        'rankの低い親を高い方のの親にする'
        if not self.same(x,y):
            x = self.find(x)
            y = self.find(y)
            if self.rank[x] > self.rank[y]:
                x,y = y,x
            elif self.rank[x] == self.rank[y]:
                self.rank[y] += 1
            self.b[y] += self.b[x]
            self.w[y] += self.w[x]
            self.p[x] = y
            if x in self.parent:
                self.parent.remove(x)
            return True
        else:
            return False

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

h,w = map(int,input().split())
uf = UnionFind(h*w)
S = []
for i in range(h):
    S.append(input())
    for j,s in enumerate(S[i]):
        if s == '
            uf.b[i*w+j] += 1
        else:
            uf.w[i*w+j] += 1

for i in range(h):
    for j in range(w):
        for di,dj in [[1,0],[0,1]]:
            ni = i+di
            nj = j+dj
            if ni < h and nj < w and S[i][j] != S[ni][nj]:
                uf.unite(i*w+j,ni*w+nj)
ans = 0
for p in uf.parent:
    ans += uf.b[p] * uf.w[p]
print(ans)

Solution (Python):
dy = (-1,0,1,0)
dx = (0,1,0,-1)

h,w = map(int,input().split())
grid = [input() for _ in range(h)]

ans = 0
dist = [[-1] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if dist[i][j] < 0:
            odd = 0
            even = 1
            dist[i][j] = 0
            stack = [(i,j)]
            while stack:
                a,b = stack.pop()
                if grid[a][b] == '
                    for k in range(4):
                        y = a + dy[k]
                        x = b + dx[k]
                        if y < 0 or y >= h:
                            continue
                        if x < 0 or x >= w:
                            continue
                        if grid[y][x] == '.' and dist[y][x] < 0:
                            if dist[a][b] == 0:
                                dist[y][x] = 1
                                odd += 1
                            else:
                                dist[y][x] = 0
                                even += 1
                            stack.append((y,x))
                else:
                    for k in range(4):
                        y = a + dy[k]
                        x = b + dx[k]
                        if y < 0 or y >= h:
                            continue
                        if x < 0 or x >= w:
                            continue
                        if grid[y][x] == '
                            if dist[a][b] == 0:
                                dist[y][x] = 1
                                odd += 1
                            else:
                                dist[y][x] = 0
                                even += 1
                            stack.append((y,x))    
            ans += even * odd
print(ans)

Solution (Python):







H,W = map(int,input().split())
grid = [None] * H
for i in range(H):
  grid[i] = input()
  
visited = [[False] * W for i in range(H)]

def get_next_unvisited(checked_y):
  for i in range(checked_y,H):
    for j in range(W):
      if not visited[i][j]:
        return i,j
  return -1,-1 
  
from collections import deque
ans = 0
cases = ((0,1),(0,-1),(1,0),(-1,0))
checked_y = 0
while True:
  y,x = get_next_unvisited(checked_y)
  if y == -1 and x == -1:
    print(ans)
    exit(0)
  checked_y = y
  
  q = deque([[y,x,-1,-1,"N"]])
  black = 0
  white = 0
  
  while q:
    y,x,parent_y,parent_x,parent = q.pop()
    if visited[y][x]:
      continue
    point = grid[y][x]
    if point == parent:
      continue
    visited[y][x] = True
    if point == "
      black += 1
    if point == ".":
      white += 1
    for c in cases:
      if y + c[0] == parent_y and x + c[1] == parent_x:
        continue
      if 0 <= y + c[0] < H and 0 <= x + c[1] < W:
        q.append([y + c[0],x + c[1],y,x, point])
  ans += black * white

Solution (Python):
h,w=[int(j) for j in input().split()]
s=[input()for i in range(h)]
par=[-1 for i in range(h*w)]
def root(a):
    if par[a]<0:
        return a
    else:
        return root(par[a])

def size(a):
    return -par[root(a)]

def connect(a,b):
    a=root(a)
    b=root(b)
    if a==b:
        return False
    if size(a)<size(b):
        a,b=b,a
    par[a]+=par[b]
    par[b]=a
    return True

for i in range(h):
    for j in range(w):
        for x,y in [(1,0),(-1,0),(0,1),(0,-1)]:
            p,q=i+x,j+y
            if 0<=p<h and 0<=q<w:
                if s[p][q]!=s[i][j]:
                    if root(w*p+q)!=root(w*i+j):
                        connect(w*p+q,w*i+j)

from collections import Counter
c=Counter()
for i in range(h):
    for j in range(w):
        p=i*w+j
        q=root(p)
        if c[q]==0:
            c[q]=[0,0]
        if s[i][j]=="
            c[q][0]+=1
        else:
            c[q][1]+=1
ans=0
for i in c:
    ans+=c[i][0]*c[i][1]
print(ans)

Solution (Python):
h,w=[int(j) for j in input().split()]
s=[list(input())for i in range(h)]
par=[-1 for i in range(h*w)]    
def root(a):
    if par[a]<0:
        return a
    else:
        return root(par[a])

def size(a):
    return -par[root(a)]

def connect(a,b):
    a=root(a)
    b=root(b)
    if a==b:
        return False
    if size(a)<size(b):
        a,b=b,a
    par[a]+=par[b]
    par[b]=a
    return True

for i in range(h):
    for j in range(w):
        for x,y in [(1,0),(-1,0),(0,1),(0,-1)]:
            p,q=i+x,j+y
            if 0<=p<h and 0<=q<w:
                if s[p][q]!=s[i][j]:
                    if root(w*p+q)!=root(w*i+j):
                        connect(w*p+q,w*i+j)

from collections import Counter
c=Counter()
for i in range(h):
    for j in range(w):
        p=i*w+j
        q=root(p)
        if c[q]==0:
            c[q]=[0,0]
        if s[i][j]=="
            c[q][0]+=1
        else:
            c[q][1]+=1
ans=0
for i in c:
    ans+=c[i][0]*c[i][1]
print(ans)