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):
from collections import deque

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

S=[]
for i in range(H):
    S.append([c=='


a=[[[] for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        if 0<i and (S[i][j] ^ S[i-1][j]):
            a[i][j].append((i-1,j))
        if i<H-1 and (S[i][j] ^ S[i+1][j]):
            a[i][j].append((i+1,j))
        if 0<j and (S[i][j] ^ S[i][j-1]):
            a[i][j].append((i,j-1))
        if j<W-1 and (S[i][j] ^ S[i][j+1]):
            a[i][j].append((i,j+1))
'''
for ai in a:
    print(ai)
'''
ans=0
q=deque()
r=[[False for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        if not r[i][j]:
            b,w=0,0
            q.append((i,j));r[i][j]=True
            if S[i][j]:
                b+=1
            else:
                w+=1
            while q:
                ui,uj=q.popleft()
                for v in a[ui][uj]:
                    vi,vj=v
                    if not r[vi][vj]:
                        q.append((vi,vj));r[vi][vj]=True
                        if S[vi][vj]:
                            b+=1
                        else:
                            w+=1
            ans+=b*w
print(ans)

Solution (Python):
from collections import deque

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

check = [[1 for _ in range(W)] for _ in range(H)]

def bw(s):
  if s == "
    return "."
  else:
    return "

def cnt_plus(s, cnt):
  if s == "
    c = [cnt[0] + 1, cnt[1]]
  else:
    c = [cnt[0], cnt[1] + 1]
  return c
  
def bfs(i, j):
  stack = deque()
  stack.append(((i, j), S[i][j]))
  check[i][j] = 0
  cnt = [0, 0]
  
  while stack:
    p, s = stack.popleft()
    cnt = cnt_plus(s, cnt)
    ii, jj = p
    bws = bw(s)

    if ii - 1 >= 0 and check[ii - 1][jj]:
      if S[ii - 1][jj] == bws:
        check[ii - 1][jj] = 0
        stack.append(((ii - 1, jj), bws))

    if ii + 1 < H and check[ii + 1][jj]:
      if S[ii + 1][jj] == bws:
        check[ii + 1][jj] = 0
        stack.append(((ii + 1, jj), bws))

    if jj - 1 >= 0 and check[ii][jj - 1]:
      if S[ii][jj - 1] == bws:
        check[ii][jj - 1] = 0
        stack.append(((ii, jj - 1), bws))

    if jj + 1 < W and check[ii][jj + 1]:
      if S[ii][jj + 1] == bws:
        check[ii][jj + 1] = 0
        stack.append(((ii, jj + 1), bws))
  return cnt[0] * cnt[1]

answer = 0
for i in range(H):
  for j in range(W):
    if check[i][j] and S[i][j] == "
      answer += bfs(i, j)
print(answer)

Solution (Python):
h, w = map(int, input().split())
grid = [[1 if i == "
seen = [[0] * w for _ in range(h)]
DX = (0, 1, 0, -1)
DY = (1, 0, -1, 0)
ans = 0


def dfs(X, Y, cnt):
    todo = [(X, Y)]
    seen[X][Y] = cnt
    black = 0
    white = 1
    while todo:
        x, y = todo.pop()
        now = grid[x][y]
        for dx, dy in zip(DX, DY):
            nx = x + dx
            ny = y + dy
            if nx < 0 or ny < 0 or nx >= h or ny >= w:  
                continue
            if seen[nx][ny] == cnt or now == grid[nx][ny]:  
                continue
            if 1-now:  
                black += 1
            else:
                white += 1
            seen[nx][ny] = cnt
            todo.append((nx, ny))
    return black*white


cnt = 1
for i in range(h):
    for j in range(w):
        if grid[i][j] or seen[i][j]:
            continue
        ans += dfs(i, j, cnt)
        cnt += 1

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
h, w = [int(i) for i in sys.stdin.readline().split()]
s_ls = []
bl_ls = []
for i in range(h):
    s = [1 if i == "
    for j, k in enumerate(s):
        if k == 1:
            bl_ls.append((i, j))
    s_ls.append(s)

memo_ls = dict()
def dfs(y, x, col):
    if (y, x) in memo_ls:
        return memo_ls[(y, x)]
    res = 0
    if col == -1:
        res += 1
    already.add((y, x))
    for move_y, move_x in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        next_y = y + move_y
        next_x = x + move_x
        if 0 <= next_x < w and 0 <= next_y < h and s_ls[next_y][next_x] == (-1) * col and (next_y, next_x) not in already:
            res += dfs(next_y, next_x, (-1) * col)
    return res

ans = 0
for bl in bl_ls:
    already = set()
    stack = [(bl[0], bl[1], 1, 0)]
    cnt = 0
    while len(stack) > 0:
        y, x, col, _sum = stack.pop(-1)
        if (y, x) in memo_ls:
            cnt = memo_ls[(y, x)]
            break
        if col == -1:
            cnt += 1
        already.add((y, x))
        for move_y, move_x in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            next_y = y + move_y
            next_x = x + move_x
            if 0 <= next_x < w and 0 <= next_y < h and s_ls[next_y][next_x] == (-1) * col and (
            next_y, next_x) not in already:
                stack.append((next_y, next_x, (-1) * col, _sum))
                already.add((next_y, next_x))
    res = cnt
    ans += res
    for al in list(already):
        memo_ls[al] = res
print(ans)

Solution (Python):
class UnionFindTree:
    """Disjoint-Set Data Structure
       Union-Find Tree
       complexity:
          init: O(n)
          find, unite, same: O(alpha(n))
       used in SRM505 div.2 900, ATC001 A, DSL1A(AOJ)
    """
    def __init__(self, n):
        self.par = list(range(n))  
        self.rank = [0] * n  

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

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

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

H, W = map(int, input().split())
uft = UnionFindTree(H * W)
board = [input() for _ in range(H)]
drc = [(1, 0), (0, 1)]
for r in range(H):
    for c in range(W):
        if r < H - 1 and board[r + 1][c] != board[r][c]:
            uft.unite(r * W + c, (r + 1) * W + c)
        if c < W - 1 and board[r][c + 1] != board[r][c]:
            uft.unite(r * W + c, r * W + c + 1)
par_dict_w, par_dict_b = dict(), dict()
for r in range(H):
    for c in range(W):
        par = uft.find(r * W + c)
        if board[r][c] == "
            par_dict_b[par] = par_dict_b.get(par, 0) + 1
        else:
            par_dict_w[par] = par_dict_w.get(par, 0) + 1
print(sum(par_dict_w[k] * par_dict_b.get(k, 0) for k in par_dict_w.keys()))

Solution (Python):
class UnionFindTree:
    """Disjoint-Set Data Structure
       Union-Find Tree
       complexity:
          init: O(n)
          find, unite, same: O(alpha(n))
       used in SRM505 div.2 900, ATC001 A, DSL1A(AOJ)
    """
    def __init__(self, n):
        self.par = list(range(n))  
        self.rank = [0] * n  

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

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

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

H, W = map(int, input().split())
uft = UnionFindTree(H * W)
board = [input() for _ in range(H)]
drc = [(1, 0), (0, 1)]
for r in range(H):
    for c in range(W):
        if r < H - 1 and board[r + 1][c] != board[r][c]:
            uft.unite(r * W + c, (r + 1) * W + c)
        if c < W - 1 and board[r][c + 1] != board[r][c]:
            uft.unite(r * W + c, r * W + c + 1)
par_dict_w, par_dict_b = dict(), dict()
for r in range(H):
    for c in range(W):
        par = uft.find(r * W + c)
        if board[r][c] == "
            par_dict_b[par] = par_dict_b.get(par, 0) + 1
        else:
            par_dict_w[par] = par_dict_w.get(par, 0) + 1
print(sum(par_dict_w[k] * par_dict_b.get(k, 0) for k in par_dict_w.keys()))

Solution (Python):
h, w = map(int ,input().split())
s = [list(input()) for _ in range(h)]
check = [[0] * w for _ in range(h)]
move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
ans = 0

for i in range(h):
    for j in range(w):
        if check[i][j] == 1:
            continue
        black, white = 0, 0 

        stack = [[i, j]]
        check[i][j] = 1
        if s[i][j] == '
            black += 1
        else:
            white += 1

        while len(stack) > 0:
            x, y = stack.pop()
            tmp = s[x][y]
            for dx, dy in move:
                nx, ny = x + dx, y + dy
                if 0 <= nx < h and 0 <= ny < w and tmp != s[nx][ny] and check[nx][ny] == 0:
                    stack.append([nx, ny])
                    check[nx][ny] = 1
                    if s[nx][ny] == '
                        black += 1
                    else:
                        white += 1

        ans += black * white

print(ans)

Solution (Python):
h, w = map(int ,input().split())
s = [list(input()) for _ in range(h)]
check = [[0] * w for _ in range(h)]
move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
ans = 0

for i in range(h):
    for j in range(w):
        if check[i][j] == 1:
            continue
        black, white = 0, 0 

        stack = [[i, j]]
        check[i][j] = 1
        if s[i][j] == '
            black += 1
        else:
            white += 1

        while len(stack) > 0:
            x, y = stack.pop()
            tmp = s[x][y]
            for dx, dy in move:
                nx, ny = x + dx, y + dy
                if 0 <= nx < h and 0 <= ny < w and tmp != s[nx][ny] and check[nx][ny] == 0:
                    stack.append([nx, ny])
                    check[nx][ny] = 1
                    if s[nx][ny] == '
                        black += 1
                    else:
                        white += 1

        ans += black * white

print(ans)

Solution (Python):
import sys
from collections import deque

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  

def bfs(x, y, c):
    global data
    
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    que = deque()
    que.append(((x, y), c))
    data[y][x] = 'visited'
    black = 1
    white = 0

    while que:
        p, color = que.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            next_color = '
            if 0 <= ny and ny <= H-1 and 0 <= nx and nx <= W-1 and \
                    data[ny][nx] == next_color:
                data[ny][nx] = 'visited'
                if next_color == '.':
                    white += 1
                elif next_color == '
                    black += 1
                que.append(((nx, ny), next_color))
    return white * black

H, W = rl()
data = [list(rs()) for _ in range(H)]
answer = 0

for y in range(H):
    for x in range(W):
        if data[y][x] == '
            answer += bfs(x, y, data[y][x])

print(answer)

Solution (Python):
def main():
	t, *grid = open(0)
	h, w = map(int, t.split())
	vis = [[False] * w for _ in range(h)]
	ans = 0
	for y in range(h):
		for x in range(w):
			if vis[y][x]:
				continue
			q = [(y, x, grid[y][x])]
			d = {"
			while q:
				cy, cx, cc = q.pop()
				for ny, nx in ((cy + 1, cx), (cy - 1, cx), (cy, cx + 1), (cy, cx - 1)):
					if not (0 <= ny < h and 0 <= nx < w) or vis[ny][nx] or cc == grid[ny][nx]:
						continue
					nc = grid[ny][nx]
					d[nc] += 1
					vis[ny][nx] = True
					q.append((ny, nx, nc))
			ans += d["
	print(ans)

if __name__=="__main__":
	main()

Solution (Python):
def main():
	t, *grid = open(0)
	h, w = map(int, t.split())
	vis = [[False] * w for _ in range(h)]
	ans = 0
	for y in range(h):
		for x in range(w):
			if vis[y][x]:
				continue
			q = [(y, x, grid[y][x])]
			d = {"
			while q:
				cy, cx, cc = q.pop(0)
				for ny, nx in ((cy + 1, cx), (cy - 1, cx), (cy, cx + 1), (cy, cx - 1)):
					if not (0 <= ny < h and 0 <= nx < w) or vis[ny][nx] or cc == grid[ny][nx]:
						continue
					nc = grid[ny][nx]
					d[nc] += 1
					vis[ny][nx] = True
					q.append((ny, nx, nc))
			ans += d["
	print(ans)

if __name__=="__main__":
	main()

Solution (Python):
t,*grid=open(0)
h,w=map(int,t.split())
vis=[[False]*w for _ in range(h)]
ans=0
for y in range(h):
	for x in range(w):
		if vis[y][x]:
			continue
		q=[(y,x)]
		d={"
		while q:
			cy,cx=q.pop(0)
			for ny,nx in ((cy+1,cx),(cy-1,cx),(cy,cx+1),(cy,cx-1)):
				if not (0<=ny<h and 0<=nx<w) or vis[ny][nx] or grid[cy][cx]==grid[ny][nx]:
					continue
				d[grid[ny][nx]]+=1
				vis[ny][nx]=True
				q.append((ny,nx))
		ans+=d["
print(ans)

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

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

check = [[0] * W for _ in range(H)]

ans = 0

move = [[1, 0], [-1, 0], [0, 1], [0, -1]]

for h in range(H):
    for w in range(W):
        if check[h][w] == 1:
            continue
        black = 0
        white = 0

        stack = [[h, w]]
        check[h][w] = 1
        if S[h][w] == '
            black += 1
        elif S[h][w] == '.':
            white += 1

        while len(stack) != 0:
            x, y = stack.pop()
            tmp = S[x][y]
            for dx, dy in move:
                nx = x + dx
                ny = y + dy
                if 0 <= nx < H and 0 <= ny < W and tmp != S[nx][ny] and check[nx][ny] == 0:
                    check[nx][ny] = 1
                    stack.append([nx, ny])
                    if S[nx][ny] == '
                        black += 1
                    elif S[nx][ny] == '.':
                        white += 1
        
        ans += black * white

print (ans)

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

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

check = [[0] * W for _ in range(H)]

ans = 0

move = [[1, 0], [-1, 0], [0, 1], [0, -1]]

for h in range(H):
    for w in range(W):
        if check[h][w] == 1:
            continue
        black = 0
        white = 0

        stack = [[h, w]]
        check[h][w] = 1
        if S[h][w] == '
            black += 1
        elif S[h][w] == '.':
            white += 1

        while len(stack) != 0:
            x, y = stack.pop()
            tmp = S[x][y]
            for dx, dy in move:
                nx = x + dx
                ny = y + dy
                if 0 <= nx < H and 0 <= ny < W and tmp != S[nx][ny] and check[nx][ny] == 0:
                    check[nx][ny] = 1
                    stack.append([nx, ny])
                    if S[nx][ny] == '
                        black += 1
                    elif S[nx][ny] == '.':
                        white += 1
        
        ans += black * white

print (ans)

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

ans = 0
visited = [[0]*W for _ in range(H)]
stack = []
dx = [1,0,-1,0]
dy = [0,1,0,-1]

for i in range(H):
    for j in range(W):
        b,w = 0,0
        if not visited[i][j]:
            stack.append([i,j])
            visited[i][j] = 1
            while stack:
                x,y = stack.pop()
                if S[x][y]=='
                    b += 1
                else:
                    w += 1
                for k in range(4):
                    nx,ny = x+dx[k],y+dy[k]
                    if not(0<=nx<H and 0<=ny<W):
                        continue
                    if not visited[nx][ny] and S[x][y]!=S[nx][ny]:
                        visited[nx][ny] = 1
                        stack.append([nx,ny])
            ans += b*w

print(ans)

Solution (Python):
def dfs_grid(h,w,sy, sx, maze,visited):
    cur = defaultdict(int)
    def bfs(cur):
        queue = []
        queue.insert(0, (sy, sx))
        visited[sy][sx] = True
        cur[maze[sy][sx]] += 1
        while len(queue):
            y, x = queue.pop()
            now = maze[y][x]
            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                if (0<= nx <w and 0<= ny <h and maze[ny][nx] != now and (not visited[ny][nx])):
                    queue.insert(0, (ny, nx))
                    visited[ny][nx] = True
                    cur[maze[ny][nx]] +=1
        return cur
    return bfs(cur)
def examC():
    H, W = LI()
    S = [SI() for _ in range(H)]
    ans = 0
    visited = [[False]*(W) for _ in range(H)]
    for i in range(H):
        for j in range(W):
            d = dfs_grid(H,W,i,j,S,visited)
            ans += d["."]*d["
    print(ans)

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examC()

Solution (Python):
def dfs_grid(h,w,sy, sx, maze,visited):
    cur = defaultdict(int)
    def bfs(cur):
        queue = []
        queue.insert(0, (sy, sx))
        visited[sy][sx] = True
        cur[maze[sy][sx]] += 1
        while len(queue):
            y, x = queue.pop()
            now = maze[y][x]
            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                if (0<= nx <w and 0<= ny <h and maze[ny][nx] != now and (not visited[ny][nx])):
                    queue.insert(0, (ny, nx))
                    visited[ny][nx] = True
                    cur[maze[ny][nx]] +=1
        return cur
    return bfs(cur)
def examC():
    H, W = LI()
    S = [SI() for _ in range(H)]
    ans = 0
    visited = [[False]*(W) for _ in range(H)]
    for i in range(H):
        for j in range(W):
            d = dfs_grid(H,W,i,j,S,visited)
            ans += d["."]*d["
    print(ans)

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examC()

Solution (Python):
from fractions import gcd

from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7





def main():
    
    h, w = map(int, input().split())
    s = [list(input()) for i in range(h)]
    start = []
    for i in range(h):
        for j in range(w):
            if s[i][j] == "
                start.append([i,j])

    ans = [0,0]
    vis = [[-1 for i in range(w)] for j in range(h)]
    def f(x, y, pre):
        vis[x][y] = 1
        if s[x][y] == "
            ans[0] += 1
        else:
            ans[1] +=1
        for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            nx = i + x
            ny = j + y
            if nx >= 0 and ny >= 0 and nx < h and ny < w and vis[nx][ny] == -1:
                if pre == "B" and s[nx][ny] == ".":
                    f(nx,ny,"W")
                elif pre == "W" and s[nx][ny] == "
                    f(nx, ny, "B")
                
    
    ret = 0
    for i, j in start:
        if vis[i][j] == -1:
            f(i, j, "B")
        ret += ans[0] * ans[1]
        ans[0] = ans[1] = 0
    print(ret)
        

if __name__ == '__main__':
    main()

Solution (Python):
from fractions import gcd

from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def main():
    
    h, w = map(int, input().split())
    s = [list(input()) for i in range(h)]
    start = []
    for i in range(h):
        for j in range(w):
            if s[i][j] == "
                start.append([i,j])

    ans = [0,0]
    vis = [[-1 for i in range(w)] for j in range(h)]
    def f(x, y, pre):
        vis[x][y] = 1
        if s[x][y] == "
            ans[0] += 1
        else:
            ans[1] +=1
        for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            nx = i + x
            ny = j + y
            if nx >= 0 and ny >= 0 and nx < h and ny < w and vis[nx][ny] == -1:
                if pre == "B" and s[nx][ny] == ".":
                    f(nx,ny,"W")
                elif pre == "W" and s[nx][ny] == "
                    f(nx, ny, "B")
                
    
    ret = 0
    for i, j in start:
        if vis[i][j] == -1:
            f(i, j, "B")
        ret += ans[0] * ans[1]
        ans[0] = ans[1] = 0
    print(ret)
        

if __name__ == '__main__':
    main()

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

Solution (Python):
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.root=[-1]*(n+1)
        self.rnk=[0]*(n+1)

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

    def Unite(self,x,y):
        x=self.Find_Root(x)
        y=self.Find_Root(y)
        if x==y:
            return
        elif self.rnk[x]>self.rnk[y]:
            self.root[x]+=self.root[y]
            self.root[y]=x
        else:
            self.root[y]+=self.root[x]
            self.root[x]=y
            if self.rnk[x]==self.rnk[y]:
                self.rnk[y]+=1

    def isSameGroup(self,x,y):
        return self.Find_Root(x)==self.Find_Root(y)

    def Count(self,x):
        return -self.root[self.Find_Root(x)]

h,w=map(int,input().split())
g=[list(input()) for _ in range(h)]
uf=UnionFind(h*w)
dyx=[(1,0),(-1,0),(0,1),(0,-1)]
for i in range(h):
    for j in range(w):
        if g[i][j]==".":
            continue
        p=i*w+j
        for dy,dx in dyx:
            y=i+dy
            x=j+dx
            if 0<=y<h and 0<=x<w:
                if g[y][x]==".":
                    np=y*w+x
                    uf.Unite(p,np)

rt=[0]*(h*w)
for i in range(h*w):
    rt[i]=uf.Find_Root(i)

m=min(rt)
rt=list(map(lambda x:x-m, rt))
m=max(rt)
a=[[0,0] for _ in range(m+1)]
for i in range(h*w):
    y=i//w
    x=i%w
    if g[y][x]=="
        a[rt[i]][0]+=1
    else:
        a[rt[i]][1]+=1
ans=0
for i,j in a:
    ans+=i*j

print(ans)

Solution (Python):
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.root=[-1]*(n+1)
        self.rnk=[0]*(n+1)

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

    def Unite(self,x,y):
        x=self.Find_Root(x)
        y=self.Find_Root(y)
        if x==y:
            return
        elif self.rnk[x]>self.rnk[y]:
            self.root[x]+=self.root[y]
            self.root[y]=x
        else:
            self.root[y]+=self.root[x]
            self.root[x]=y
            if self.rnk[x]==self.rnk[y]:
                self.rnk[y]+=1

    def isSameGroup(self,x,y):
        return self.Find_Root(x)==self.Find_Root(y)

    def Count(self,x):
        return -self.root[self.Find_Root(x)]

h,w=map(int,input().split())
g=[list(input()) for _ in range(h)]
uf=UnionFind(h*w)
dyx=[(1,0),(-1,0),(0,1),(0,-1)]
for i in range(h):
    for j in range(w):
        if g[i][j]==".":
            continue
        p=i*w+j
        for dy,dx in dyx:
            y=i+dy
            x=j+dx
            if 0<=y<h and 0<=x<w:
                if g[y][x]==".":
                    np=y*w+x
                    uf.Unite(p,np)

rt=[0]*(h*w)
for i in range(h*w):
    rt[i]=uf.Find_Root(i)

m=min(rt)
rt=list(map(lambda x:x-m, rt))
m=max(rt)
a=[[0,0] for _ in range(m+1)]
for i in range(h*w):
    y=i//w
    x=i%w
    if g[y][x]=="
        a[rt[i]][0]+=1
    else:
        a[rt[i]][1]+=1
ans=0
for i,j in a:
    ans+=i*j

print(ans)

Solution (Python):
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy


from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): 
    return int(input())
def inpm(): 
    return map(int,input().split())
def inpl(): 
    return list(map(int, input().split()))
def inpls(): 
    return list(input().split())
def inplm(n): 
    return list(int(input()) for _ in range(n))
def inpll(n): 
    return sorted([list(map(int, input().split())) for _ in range(n)])


def main():
    h,w=inpm()
    s=[input() for _ in range(h)]
    que=deque()
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    went = [[False for _ in range(w)] for _ in range(h)]
    ans = 0
    for i in range(h):
        for j in range(w):
            if s[i][j]=="
                if not went[i][j]:
                    went[i][j] = True
                    que = deque()
                    que.append((i,j))
                    a,b = 1,0
                    while len(que)>0:
                        x,y=que.pop()
                        for k in range(4):
                            nx,ny=x+dx[k],y+dy[k]
                            if nx<0 or h<=nx or ny<0 or w<=ny or went[nx][ny]:
                                continue
                            if s[x][y] != s[nx][ny]:
                                if s[nx][ny] == '
                                    a+=1
                                else:
                                    b+=1
                                went[nx][ny]=True
                                que.append((nx,ny))
                    ans += a*b
    print(ans)
    
if __name__ == "__main__":
    main()

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

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

def search(sx, sy) :
    q = [(sx, sy)]
    visited[sy][sx] = True
    
    b, w = 0, 0
    if S[sy][sx] == '
        b += 1
    else :
        w += 1
        
    while q :
        cx, cy = q.pop()
        for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)) :
            nx, ny = cx + dx, cy + dy
            if 0 <= nx < W and 0 <= ny < H and not visited[ny][nx] and S[cy][cx] != S[ny][nx] :
                visited[ny][nx] = True
                q.append((nx, ny))
                if S[ny][nx] == '
                    b += 1
                else :
                    w += 1           
    return b * w

ret = 0
for y in range(H) :
    for x in range(W) :
        if not visited[y][x] :
            ret += search(x, y)
            
print(ret)

Solution (Python):
import sys
from collections import deque as dq
input = sys.stdin.readline
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
d = [-1, 0, 1, 0]
vis = [[0] * W for _ in range(H)]
Q = dq([])
res = 0
for i in range(H):
  for j in range(W):
    if vis[i][j] == 1: continue
    Q.append((i, j))
    w = 0
    b = 0
    while len(Q):
      p = Q.popleft()
      if S[p[0]][p[1]] == "
      elif S[p[0]][p[1]] == ".": w += 1
      vis[p[0]][p[1]] = 1
      for way in range(4):
        x = p[1] + d[way]
        y = p[0] + d[-1 - way]
        if 0 <= y < H and (0 <= x < W):
          if S[p[0]][p[1]] == S[y][x]:
            continue
          if vis[y][x] == 1: continue
          Q.append((y, x))
          vis[y][x] = 1
    res += b * w
print(res)