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
import math
import collections
import bisect
import copy



sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))





def main():
    h, w = ns()
    mat = [list(input()) for _ in range(h)]
    visited = [[False for _ in range(w)] for __ in range(h)]

    B, W = 0, 1
    for y in range(h):
        for x in range(w):
            if mat[y][x] == "
                mat[y][x] = B
            else:
                mat[y][x] = W

    cnt = [0, 0]
    pos = [[0, 1], [0, -1], [1, 0], [-1, 0]]

    def bfs(y, x, here):
        visited[y][x] = True
        cnt[here] += 1

        for yi, xi in pos:
            ty = y + yi
            tx = x + xi
            if 0 <= ty < h and 0 <= tx < w:
                if not visited[ty][tx] and mat[ty][tx] == here ^ 1:
                    bfs(ty, tx, here ^ 1)

    ans = 0
    for y in range(h):
        for x in range(w):
            if not visited[y][x]:
                cnt = [0, 0]
                bfs(y, x, mat[y][x])
                ans += cnt[B] * cnt[W]

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math
import collections
import bisect
import copy



sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))





def main():
    h, w = ns()
    mat = [list(input()) for _ in range(h)]
    visited = [[False for _ in range(w)] for __ in range(h)]

    B, W = 0, 1
    for y in range(h):
        for x in range(w):
            if mat[y][x] == "
                mat[y][x] = B
            else:
                mat[y][x] = W

    cnt = [0, 0]
    pos = [[0, 1], [0, -1], [1, 0], [-1, 0]]

    def bfs(y, x, here):
        visited[y][x] = True
        cnt[here] += 1

        for yi, xi in pos:
            ty = y + yi
            tx = x + xi
            if 0 <= ty < h and 0 <= tx < w:
                if not visited[ty][tx] and mat[ty][tx] == here ^ 1:
                    bfs(ty, tx, here ^ 1)

    ans = 0
    for y in range(h):
        for x in range(w):
            if not visited[y][x]:
                cnt = [0, 0]
                bfs(y, x, mat[y][x])
                ans += cnt[B] * cnt[W]

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

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

q=deque([])
T=[]
seen=[[0]*W for _ in range(H)]
step=[[0,1],[0,-1],[1,0],[-1,0]]
for h in range(H):
    for w in range(W):
        temp=[]
        if seen[h][w]==0:
            temp.append(S[h][w])
            seen[h][w]=1
            q.append([h,w,S[h][w]])
            while q:
                oh,ow,m=q.popleft()
                for dh,dw in step:
                    if 0<=oh+dh<H and 0<=ow+dw<W:
                        if seen[oh+dh][ow+dw]==0 and m!=S[oh+dh][ow+dw]:
                            temp.append(S[oh+dh][ow+dw])
                            seen[oh+dh][ow+dw]=1
                            q.append([oh+dh,ow+dw,S[oh+dh][ow+dw]])
            T.append(temp)

ans=0
for i in range(len(T)):
    black=0
    white=0
    for s in T[i]:
        if s=="
            black+=1
        else:
            white+=1
    ans+=black*white

print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(1000000)


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

def DFS(h,w,black,white,m):
    black,white=BorW(h,w,black,white)
    step=[[0,1],[0,-1],[1,0],[-1,0]]
    seen[h][w]=1
    for dh,dw in step:
        nh=h+dh
        nw=w+dw
        if 0<=nh<H and 0<=nw<W:
            if seen[nh][nw]==0 and m!=S[nh][nw]:
                seen[nh][nw]=1
                black,white=DFS(nh,nw,black,white,S[nh][nw])
    return black,white


def BorW(h,w,black,white):
    if S[h][w]=="
        black+=1
    else:
        white+=1
    return black,white


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

L=[]
for h in range(H):
    for w in range(W):
        black=0
        white=0
        if seen[h][w]==0:
            black,white=DFS(h,w,black,white,S[h][w])
            L.append([black,white])
ans=0
for b,w in L:
     ans+=b*w

print(ans)

Solution (Python):


import sys
from collections import deque
input=sys.stdin.readline

def main():
    H,W=map(int,input().split())
    masu=[input().strip("\n") for i in range(H)]
    
    di=[(-1,0), (1,0), (0,-1), (0,1)]
    dist=[[-1]*W for i in range(H)]
    ans=0
    
    for i in range(H):
        for j in range(W):
            if masu[i][j]=="
                bcnt=0
                wcnt=0
                qu=deque([(i,j)])
                dist[i][j]=0
                while(len(qu)>0):
                    v=qu.popleft()
                    if masu[v[0]][v[1]]=="
                        nex="."
                        bcnt+=1
                    else:
                        nex="
                        wcnt+=1
                    for d in di:
                        nv=(v[0]+d[0],v[1]+d[1])
                        if 0<=nv[0]<H and 0<=nv[1]<W and dist[nv[0]][nv[1]]==-1 and masu[nv[0]][nv[1]] == nex:
                            dist[nv[0]][nv[1]]=dist[v[0]][v[1]]+1
                            qu.append(nv)
                ans+=bcnt*wcnt
    print(ans)
    
    
if __name__=="__main__":
    main()

Solution (Python):
from collections import deque

h,w = map(int,input().split())

s = [0]*(h+2)
for i in range(1,h+1):
    s[i] = [0] + list(input()) + [0]
s[0] = [0]*(w+2)
s[-1] = [0]*(w+2)

reach = [[-1 for j in range(w+2)] for i in range(h+2)]
lis = []

for i in range(1,h+1):
    for j in range(1,w+1):
        if reach == 0:
            pass
        else:
            black = 0
            white = 0
            if s[i][j] == "
                state = 1
                black += 1
            else:
                state = 0
                white += 1
                
            q = deque()
            q.append([i,j,state])
            reach[i][j] = 0
            
            while q:
                [x,y,state] = q.popleft()
                
                if reach[x-1][y] == -1:
                    if state == 0 and s[x-1][y] == "
                        reach[x-1][y] = 0
                        q.append([x-1, y ,1])
                        black += 1
                    elif  state == 1 and s[x-1][y] == ".":
                        reach[x-1][y] = 0
                        q.append([x-1, y ,0])
                        white += 1
                
                if reach[x+1][y] == -1:
                    if state == 0 and s[x+1][y] == "
                        reach[x+1][y] = 0
                        q.append([x+1, y ,1])
                        black += 1
                    elif  state == 1 and s[x+1][y] == ".":
                        reach[x+1][y] = 0
                        q.append([x+1, y ,0])
                        white += 1
                        
                if reach[x][y-1] == -1:
                    if state == 0 and s[x][y-1] == "
                        reach[x][y-1] = 0
                        q.append([x, y-1 ,1])
                        black += 1
                    elif  state == 1 and s[x][y-1] == ".":
                        reach[x][y-1] = 0
                        q.append([x, y-1 ,0])
                        white += 1
                    
                if reach[x][y+1] == -1:
                    if state == 0 and s[x][y+1] == "
                        reach[x][y+1] = 0
                        q.append([x, y+1 ,1])
                        black += 1
                    elif  state == 1 and s[x][y+1] == ".":
                        reach[x][y+1] = 0
                        q.append([x, y+1 ,0])
                        white += 1
                
            lis.append([black,white])
ans = 0
for s,t in lis:
    ans += s*t
print(ans)

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

def main():
  h, w = map(int, input().split())
  s = [input() for _ in range(h)]
  
  ans = 0
  already = [[False]*w for _ in range(h)]
  for i in range(h):
    for j in range(w):
      if already[i][j] or s[i][j] == ".":
        continue
      already[i][j] = True
      black, white = 0, 0
      not_yet = deque([(i, j)])
      while not_yet:
        p, q = not_yet.pop()
        if s[p][q] == "
          black += 1
        else:
          white += 1
        if p > 0 and s[p-1][q] != s[p][q] and not already[p-1][q]:
          not_yet.append((p-1, q))
          already[p-1][q] = True
        if p < h-1 and s[p+1][q] != s[p][q] and not already[p+1][q]:
          not_yet.append((p+1, q))
          already[p+1][q] = True
        if q > 0 and s[p][q-1] != s[p][q] and not already[p][q-1]:
          not_yet.append((p, q-1))
          already[p][q-1] = True
        if q < w-1 and s[p][q+1] != s[p][q] and not already[p][q+1]:
          not_yet.append((p, q+1))
          already[p][q+1] = True
      ans += black*white
  
  print(ans)

  
if __name__ == "__main__":
  main()

Solution (Python):
from collections import deque
h,w=map(int,input().split())
G=[["@"]*(w+2) for i in range(h+2)]
for i in range(1,h+1):
  G[i]=["@"]+list(input())+["@"]
V=[[0]*(w+2) for i in range(h+2)]
X=deque([])
Y=deque([])
XX=[-1,0,0,1]
YY=[0,-1,1,0]
ans=0
for i in range(h+2):
  for j in range(w+2):
    if V[i][j]==0 and G[i][j]=="
      X.append(i)
      Y.append(j)
      V[i][j]=1
      C=[1,0]
      while len(X)>0:
        x=X[0]
        y=Y[0]
        X.popleft()
        Y.popleft()
        if G[x][y]=="
          for k in range(4):
            if V[x+XX[k]][y+YY[k]]==0 and G[x+XX[k]][y+YY[k]]==".":
              X.append(x+XX[k])
              Y.append(y+YY[k])
              V[x+XX[k]][y+YY[k]]=1
              C[1]+=1
        else:
          for k in range(4):
            if V[x+XX[k]][y+YY[k]]==0 and G[x+XX[k]][y+YY[k]]=="
              X.append(x+XX[k])
              Y.append(y+YY[k])
              V[x+XX[k]][y+YY[k]]=1
              C[0]+=1
      ans=ans+C[0]*C[1]
print(ans)

Solution (Python):
import sys
from collections import deque

input = sys.stdin.readline


def main():
    H, W = map(int, input().split())
    S = [None] * (H + 2)
    S[0] = S[-1] = "x" * (W + 2)
    for i in range(1, H + 1):
        S[i] = "".join(["x", input().rstrip(), "x"])

    group = []
    visited = [[True] + [False] * W + [True] for _ in range(H + 2)]
    visited[0] = visited[-1] = [True] * (W + 2)
    for h in range(1, H + 1):
        for w in range(1, W + 1):
            if visited[h][w]:
                continue
            queue = deque([(h, w, S[h][w])])
            group.append({"
            while queue:
                y, x, s = queue.popleft()
                if visited[y][x]:
                    continue
                visited[y][x] = True
                group[-1][s] += 1
                for i, j in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                    yy, xx = y + i, x + j
                    if visited[yy][xx]:
                        continue
                    if s == "
                        queue.append((yy, xx, "."))
                    elif s == "." and S[yy][xx] == "
                        queue.append((yy, xx, "

    ans = 0
    for g in group:
        ans += g["
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
belong=list()
group=list()
C=list()

def init(X):
  global belong,group,C
  belong=list(range(X))
  group=[[i] for i in range(X)]
  C=[[S[i//W][i%W]=='

def unite(x,y):
  if len(group[belong[x]])<len(group[belong[y]]):
    x,y=y,x
  if belong[x]==belong[y]:
    return True
  z=belong[y]
  for i in range(len(group[z])):
    belong[group[z][-1]]=belong[x]
    group[belong[x]].append(group[z][-1])
    del group[z][-1]
  for i in range(2):
    C[belong[x]][i]+=C[z][i]
    C[z][i]=0
  return False

H,W=map(int,input().split())
S=[input() for i in range(H)]
init(H*W)
for i in range(H):
  for j in range(W):
    if i:
      if S[i][j]!=S[i-1][j]:
        unite(i*W+j,i*W+j-W)
    if j:
      if S[i][j]!=S[i][j-1]:
        unite(i*W+j,i*W+j-1)
    if i+1<H:
      if S[i][j]!=S[i+1][j]:
        unite(i*W+j,i*W+j+W)
    if j+1<W:
      if S[i][j]!=S[i][j+1]:
        unite(i*W+j,i*W+j+1)
P=0
for i in range(H*W):
  P+=C[i][0]*C[i][1]
print(P)

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

G = [[None for j in range(W)] for i in range(H)]

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

count = 0

for i in range(H):
    for j in range(W):
        if G[i][j] is not None:
            continue
        if S[i][j] == '
            color = 1
        else:
            color = 0
        stack = [(i, j, color)]
        G[i][j] = count
        while stack:
            x, y, c = stack.pop()
            for k in range(4):
                nx, ny = x + dx[k], y + dy[k]
                if not (0 <= nx < H and 0 <= ny < W):
                    continue
                if G[nx][ny] is not None:
                    continue
                if S[nx][ny] == '
                    nc = 1
                else:
                    nc = 0
                if nc == c:
                    continue
                G[nx][ny] = count
                stack.append((nx, ny, nc))
        count += 1

C = [[0, 0] for _ in range(count)]

for i in range(H):
    for j in range(W):
        if S[i][j] == '
            C[G[i][j]][0] += 1
        else:
            C[G[i][j]][1] += 1

res = 0

for b, w in C:
    res += b * w

print(res)

Solution (Python):
from collections import deque, defaultdict

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

visited = [[False] * W for i in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if visited[i][j]:
            continue
        q = deque()
        q.append((i, j))
        visited[i][j] = True
        n = defaultdict(int)
        while len(q) > 0:
            si, sj = q.popleft()
            n[S[si][sj]] += 1
            for di, dj in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
                if 0 <= si + di < H and 0 <= sj + dj < W and S[si][sj] != S[si + di][sj + dj] and not visited[si + di][sj + dj]:
                    q.append((si + di, sj + dj))
                    visited[si + di][sj + dj] = True
        ans += n['

print(ans)

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

def C(i, j):
    p = [1, 0]
    q = deque([(i, j, ".")])
    while q:
        x, y, c = q.popleft()
        for u, v in d:
            dx, dy = x + u, y + v
            if 0 <= dx < h and 0 <= dy < w and s[dx][dy] != c and use[dx][dy]:
                use[dx][dy] = False
                p[s[dx][dy] == "
                q.append((dx, dy, s[dx][dy]))
    return p[0]*p[1]


h, w = map(int, input().split())
s = [input() for i in range(h)]
use = [[1] * w for i in range(h)]
d = [(0, 1), (1, 0), (0, -1), (-1, 0)]
ans = 0
for i in range(h):
    for j in range(w):
        if use[i][j] and s[i][j] == ".":
            use[i][j] = False
            ans += C(i, j)
print(ans)

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]

    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,input().split())
N = H*W
def num(i,j):
    return i*W+j
def coo(num):
    i = num // W
    j = num % W
    return(i,j)

uf = UnionFind(N)
color = [-1]*N
grid = []
for i in range(H):
    grid.append(list(input()))
for i in range(H):
    for j in range(W):
        color[num(i,j)]= grid[i][j]
for i in range(H):
    for j in range(W-1):
        if grid[i][j] != grid[i][j+1]:
            uf.union(num(i,j),num(i,j+1))
for i in range(H-1):
    for j in range(W):
        if grid[i][j] != grid[i+1][j]:
            uf.union(num(i,j),num(i+1,j))
ans = 0
BW = [[0,0] for _ in range(N)]
for i in range(N):
    root = uf.find(i)
    if color[i] == "
        BW[root][0] += 1
    else:
        BW[root][1] += 1
for root in uf.roots():
    ans += BW[root][0]*BW[root][1]
print(ans)

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

def C(i, j):
    p = [1, 0]
    q = deque([(i, j, ".")])
    while q:
        x, y, c = q.popleft()
        for u, v in d:
            dx, dy = x + u, y + v
            if 0 <= dx < h and 0 <= dy < w and s[dx][dy] != c and use[dx][dy]:
                use[dx][dy] = False
                p[s[dx][dy] == "
                q.append((dx, dy, s[dx][dy]))
    return p[0]*p[1]


h, w = map(int, input().split())
s = [input() for i in range(h)]
use = [[1] * w for i in range(h)]
d = [(0, 1), (1, 0), (0, -1), (-1, 0)]
ans = 0
for i in range(h):
    for j in range(w):
        if use[i][j] and s[i][j] == ".":
            use[i][j] = False
            ans += C(i, j)
print(ans)

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W = map(int, input().split())
    grid = list(list(input()) for _ in range(H))

    res = [[0] * W for _ in range(H)]
    visited = [[False] * W for _ in range(H)]
    for y in range(H):
        for x in range(W):
            if grid[y][x] == "
                visited[y][x] = True
                que = deque([[y, x]])
                cnt = 1
                tmp = []
                while que:
                    h, w = que.popleft()
                    for dh, dw in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                        next_h, next_w = h + dh, w + dw
                        if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                            continue
                        if grid[h][w] == "
                            if not visited[next_h][next_w]:
                                que.append([next_h, next_w])
                                tmp.append([next_h, next_w])
                                visited[next_h][next_w] = True
                        elif grid[h][w] == "." and grid[next_h][next_w] == "
                            if not visited[next_h][next_w]:
                                cnt += 1
                                que.append([next_h, next_w])
                                visited[next_h][next_w] = True
                for h, w in tmp:
                    res[h][w] = cnt
    ans = 0
    for h in range(H):
        ans += sum(res[h])
    print(ans)


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys
import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007



def check_path(mp, is_archive, wi, hi):
	w = len(mp[0])
	h = len(mp)
	nb = 0
	nw = 0
	qq=collections.deque()
	st_color = mp[hi][wi]
	nb+=1
	qq.append((wi, hi, st_color))
	is_archive[hi][wi] = 1
	while qq:
		pw, ph, pc = qq.popleft()
		for dw, dh in ((1,0), (-1,0), (0,1),(0,-1)):
			if pw+dw<0 or pw+dw>=w or ph+dh < 0 or ph+dh >= h:
				continue
			if is_archive[ph+dh][pw+dw]>0:
				continue
			if mp[ph+dh][pw+dw]==pc:
				continue
			nc = mp[ph+dh][pw+dw]
			if nc == st_color:
				nb += 1
			else:
				nw += 1
			
			qq.append((pw+dw, ph+dh, nc))
			is_archive[ph+dh][pw+dw]=1
	
	return nb*nw

def main():
	
	h, w = tin()
	
	mp = [input() for _ in range(h)]
	is_archive = [[-1]*w for _ in range(h)]
	ret = 0
	for wi in range(w):
		for hi in range(h):
			if is_archive[hi][wi] != -1:
				continue
			nn = check_path(mp, is_archive, wi, hi)
			ret += nn
	print(ret)
			
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
import sys
import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007



def check_path(mp, is_archive, wi, hi):
	w = len(mp[0])
	h = len(mp)
	nb = 0
	nw = 0
	qq=collections.deque()
	st_color = mp[hi][wi]
	nb+=1
	qq.append((wi, hi, st_color))
	is_archive[hi][wi] = 1
	while qq:
		pw, ph, pc = qq.popleft()
		for dw, dh in ((1,0), (-1,0), (0,1),(0,-1)):
			if pw+dw<0 or pw+dw>=w or ph+dh < 0 or ph+dh >= h:
				continue
			if is_archive[ph+dh][pw+dw]>0:
				continue
			if mp[ph+dh][pw+dw]==pc:
				continue
			nc = mp[ph+dh][pw+dw]
			if nc == st_color:
				nb += 1
			else:
				nw += 1
			
			qq.append((pw+dw, ph+dh, nc))
			is_archive[ph+dh][pw+dw]=1
	
	return nb*nw

def main():
	
	h, w = tin()
	
	mp = [input() for _ in range(h)]
	is_archive = [[-1]*w for _ in range(h)]
	ret = 0
	for wi in range(w):
		for hi in range(h):
			if is_archive[hi][wi] != -1:
				continue
			nn = check_path(mp, is_archive, wi, hi)
			ret += nn
	print(ret)
			
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):


import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union








from collections import deque                






















def main():
    Num = Union[int, float]
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input():  return sys.stdin.readline().rstrip()
    def ii():     return int(input())
    def isp():    return input().split()
    def mi():     return map(int, input().split())
    def mi_0():   return map(lambda x: int(x)-1, input().split())
    def lmi():    return list(map(int, input().split()))
    def lmi_0():  return list(map(lambda x: int(x)-1, input().split()))
    def li():     return list(input())
    def debug(x): print(x, file=sys.stderr)
    
    
    
    h, w = mi()
    grid = []
    B = 1
    W = -1
    for _ in range(h):
        line = input()
        grid.append(list(map(lambda x: B if x == '
    visited = [[False] * w for _ in range(h)]

    
    


    def bfs(p):
        d = ((1, 0), (-1, 0), (0, 1), (0, -1))
        black_cnt, white_cnt = 0, 0
        q = deque()
        q.append(p)
        while q:
            i, j = q.popleft()
            if not visited[i][j]:
                visited[i][j] = True
                if grid[i][j] == B:
                    black_cnt += 1
                else:
                    white_cnt += 1
                for dx, dy in d:
                    nx, ny = i + dx, j + dy
                    if 0 <= nx < h and 0 <= ny < w and not visited[nx][ny] and grid[i][j] * grid[nx][ny] == -1:
                        q.append((nx, ny))
        return black_cnt, white_cnt


    ans = 0
    for i in range(h):
        for j in range(w):
            if grid[i][j] == B and not visited[i][j]:
                black_cnt, white_cnt = bfs((i, j))
                ans += black_cnt * white_cnt

    print(ans)




if __name__ == "__main__":
    main()

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

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

is_used = [[False] * w for _ in range(h)]

di = [+1, 0, -1, 0]
dj = [0, +1, 0, -1]


def dfs(i, j):
    if s[i][j] == '
        cnt_w, cnt_b = 0, 1
    else:
        cnt_w, cnt_b = 1, 0

    for k in range(4):
        ni = i + di[k]
        nj = j + dj[k]
        if ni < 0 or ni >= h or nj < 0 or nj >= w:
            continue
        if is_used[ni][nj]:
            continue
        if s[i][j] == s[ni][nj]:
            continue

        is_used[ni][nj] = True
        cw, cb = dfs(ni, nj)
        cnt_w += cw
        cnt_b += cb
    return (cnt_w, cnt_b)


ans = 0
for i in range(h):
    for j in range(w):
        if not is_used[i][j]:
            is_used[i][j] = True
            cnt_w, cnt_b = dfs(i, j)
            ans += cnt_w * cnt_b

print(ans)

Solution (Python):
from collections import deque
H,W = map(int,input().split())
S = []
for i in range(H):
    S.append(list(input()))
flg = [[True] * W for i in range(H)]

def bfs(i,j,S,flg):
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    que = deque([(i,j)])
    black = 1
    cnt = 1

    while len(que) != 0:
        p = que.popleft()
        
        flg[p[0]][p[1]] = False
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if nx >= 0 and nx < H and ny >= 0 and ny < W and flg[nx][ny] == True:
                if S[p[0]][p[1]] == '
                    que.append((nx,ny))
                    cnt += 1
                    flg[nx][ny] = False
                if S[p[0]][p[1]] == '.' and S[nx][ny] == '
                    que.append((nx,ny))
                    cnt += 1
                    black += 1
                    flg[nx][ny] = False
    
    
    
    
    return black * (cnt-black) 

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

print(ans)

Solution (Python):
from collections import deque


def main():
    H, W = list(map(int, input().split()))
    S = [input() for _ in range(H)]
    visited = [[0] * W for _ in range(H)]
    ans = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '
                continue
            n_white, n_black = 0, 0
            que = deque()
            que.append((h, w))
            while len(que) > 0:
                ch, cw = que.pop()
                if visited[ch][cw] == 1:
                    continue
                visited[ch][cw] = 1
                if S[ch][cw] == '.':
                    n_white += 1
                else:
                    n_black += 1
                for dh, dw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                    next_h, next_w = ch + dh, cw + dw
                    if 0 <= next_h < H and 0 <= next_w < W and \
                        S[ch][cw] != S[next_h][next_w] and \
                        visited[next_h][next_w] == 0:
                        que.append((next_h, next_w))
            ans += n_white * n_black
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



H, W = MAP()
S = [input() for _ in range(H)]

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

for y0 in range(H):
	for x0 in range(W):
		if S[y0][x0] ==  "." or check[y0][x0] == 1:
			continue
		cnt_black = 1
		cnt_white = 0
		check[y0][x0] = 1
		q = deque([(y0, x0)])
		while q:
			
			y, x = q.popleft()
			for i in range(4):
				ny = y + dy[i]
				nx = x + dx[i]
				if 0 <= ny < H and 0 <= nx < W:
					if S[y][x] == "
						check[ny][nx] = 1
						
						cnt_white += 1
						q.append((ny, nx))
					if S[y][x] == "." and S[ny][nx] == "
						check[ny][nx] = 1
						cnt_black += 1
						q.append((ny, nx))
		ans += cnt_white*cnt_black
print(ans)