Problem:
 Score : 300 points    Problem Statement There is a grid with H rows and W columns, where each square is painted black or white.  You are given H strings S_1, S_2, ..., S_H , each of length W .
If the square at the i -th row from the top and the j -th column from the left is painted black, the j -th character in the string S_i is # ; if that square is painted white, the j -th character in the string S_i is . .  Find the number of pairs of a black square c_1 and a white square c_2 that satisfy the following condition:   There is a path from the square c_1 to the square c_2 where we repeatedly move to a vertically or horizontally adjacent square through an alternating sequence of black and white squares: black, white, black, white...       Constraints  1 \leq H, W \leq 400  |S_i| = W ( 1 \leq i \leq H )  For each i ( 1 \leq i \leq H ), the string S_i consists of characters # and . .         Input Input is given from Standard Input in the following format:  H  W  S_1  S_2  :  S_H       Output Print the answer.        Sample Input 1 3 3
.#.
..#
#..      Sample Output 1 10  Some of the pairs satisfying the condition are ((1, 2), (3, 3)) and ((3, 1), (3, 2)) , where (i, j) denotes the square at the i -th row from the top and the j -th column from the left.       Sample Input 2 2 4
....
....      Sample Output 2 0       Sample Input 3 4 3
###
###
...
###      Sample Output 3 6

Solution (Python):
def getminLT(i):
  if LT[i] == i:
    return i
  else:
    return getminLT(LT[i])

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

D = []
for i in range(H):
  D.append(input())

M = [[0] * W for i in range(H)]
LT = [0]
for i in range(H):
  for j in range(W):
    if i == 0 and j == 0:
      continue
    flag = False
    if i != 0:
      if D[i][j] != D[i-1][j]:
        M[i][j] = M[i-1][j]
        flag = True
    if j != 0:
      if D[i][j] != D[i][j-1]:
        M[i][j] = M[i][j-1]
        if flag == True:
          
          LT[max(getminLT(M[i-1][j]), getminLT(M[i][j-1]))] = LT[min(getminLT(M[i][j-1]), getminLT(M[i-1][j]))]
        flag = True
    if flag == False:
        M[i][j] = len(LT)
        LT.append(len(LT))
for i in range(len(LT)):
  LT[i] = getminLT(LT[i])
  
L = [[] for i in range(len(LT))]
for i in range(H):
  for j in range(W):
  	L[LT[M[i][j]]].append((i, j))



cnt = 0
for i in L:
  E = 0
  A = 0
  for j in i:
    if (j[0] + j[1]) % 2 == 0:
      E += 1
    else:
      A += 1
  cnt += E * A
print(cnt)

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


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

move = ((1, 0), (-1, 0), (0, 1), (0, -1))
visited = [[False] * W for _ in range(H)]
b, w = 0, 0

def dfs(i, j):
    if visited[i][j]:
        return (0, 0)

    visited[i][j] = True

    if S[i][j] == '
        b, w = 1, 0
    else:
        b, w = 0, 1

    for di, dj in move:
        ni, nj = i + di, j + dj
        if not (0 <= ni < H and 0 <= nj < W):
            continue
        if S[i][j] != S[ni][nj]:
                db, dw = dfs(ni, nj)
                b, w = b + db, w + dw

    return (b, w)


result = 0
for i in range(H):
    for j in range(W):
        b, w = dfs(i, j)
        result += b * w
print(result)

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

ans = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == "x":
            continue
        q = deque()
        q.append((h, w))
        shw = S[h][w]
        bl = wh = 0
        while len(q):
            i, j = q.popleft()
            if not 0 <= i < H or not 0 <= j < W:
                continue
            if S[i][j] == "x":
                continue
            dist = i + j - h - w
            if dist % 2 == 0 and shw != S[i][j]:
                continue
            if dist % 2 == 1 and shw == S[i][j]:
                continue
            if S[i][j] == "
                bl += 1
            else:
                wh += 1
            S[i][j] = "x"
            q.append((i-1, j))
            q.append((i+1, j))
            q.append((i, j-1))
            q.append((i, j+1))
        ans += bl * wh

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(200000)

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

move = ((1, 0), (-1, 0), (0, 1), (0, -1))
visited = [[False] * W for _ in range(H)]
b, w = 0, 0

def dfs(i, j):
    global b, w

    visited[i][j] = True

    if S[i][j] == '
        b += 1
    else:
        w += 1

    for di, dj in move:
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W:
            if S[i][j] != S[ni][nj] and not visited[ni][nj]:
                dfs(ni, nj)


result = 0
for i in range(H):
    for j in range(W):
        if visited[i][j]:
            continue
        b, w = 0, 0
        dfs(i, j)
        result += b * w
print(result)

Solution (Python):
import sys
sys.setrecursionlimit(180000)

def dfs(i,j):
    for m in move:
        ni = i + m[0]
        nj = j + m[1]
        if ni < 0 or ni >= H or nj < 0 or nj >= W:
            continue
        if ch[ni][nj]:
            continue
        if X[i][j] == X[ni][nj]:
            continue
            
        ch[ni][nj] = 1
        K[(ni+nj)%2] += 1
        dfs(ni, nj)
        
H, W = map(int, input().split())
X = [[[0, 1][a=="
ch = [[0] * W for _ in range(H)]
    
move = [[0,1], [0,-1], [1,0], [-1,0]]

K = [0, 0]
ans = 0
for i in range(H):
    for j in range(W):
        if ch[i][j] > 0:
            continue
        ch[i][j] = 1
        K = [0, 0]
        K[(i+j)%2] = 1
        dfs(i, j)
        ans += K[0] * K[1]
        
print(ans)

Solution (Python):
from itertools import chain, product
H,W = map(int,input().split())
grid = list(chain(
    ([None,]*(W+2),),
    (list(chain(
      (None,),
      map(lambda x: x=='
      (None,),
      )) for _ in range(H)),
    ([None,]*(W+2),),
    ))

neighbors = ((1,0),(0,1),(-1,0),(0,-1))

res = 0

stack = []

for y,x in product(range(1,H+1),range(1,W+1)):
  if grid[y][x] is None:
    continue
  stack.append((y,x))
  black,white = 0,0

  while stack:
    y,x = stack.pop()
    v = grid[y][x]
    if v is None:
      continue
    grid[y][x] = None

    if v:
      black += 1
    else:
      white += 1
    v = not v

    for dy,dx in neighbors:
      w = grid[y+dy][x+dx]
      if w == v:
        stack.append((y+dy,x+dx))

  res += black*white

print(res)

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

H,W = map(int,input().split())
grid = [["&"] * (W+2) for i in range(H+2)]
visited = [[False] * (W+2) for i in range(H+2)]

start = []
for i in range(H):
    s = input()
    for j in range(W):
        grid[i+1][j+1] = s[j]

ans = 0
b = 0
w = 0
def dfs(p_i,p_j):
    if visited[p_i][p_j] is True:
        global ans
        return
    visited[p_i][p_j] = True
    if grid[p_i][p_j] == "
        
        global b
        b += 1
    elif grid[p_i][p_j] == ".":
        
        global w
        w += 1
    around = [[p_i,p_j+1],[p_i+1,p_j],[p_i,p_j-1],[p_i-1,p_j]]
    for i,j in around:
        if grid[p_i][p_j] == "
            dfs(i,j)
        elif grid[p_i][p_j] == "." and grid[i][j] == "
            dfs(i,j)

for i in range(1,H+1):
    for j in range(1,W+1):
        if visited[i][j] is False:
            dfs(i,j)
            ans += b * w
            b = 0
            w = 0

print(ans)

""" debug
print(start)
for line in visited_count:
    print(line)
print("b = {}".format(b))
print("w = {}".format(w)) """

Solution (Python):
import sys
from itertools import product

sys.setrecursionlimit(200000)


def input():
    return sys.stdin.readline()[:-1]


def ii(t: type = int):
    return t(input())


def il(t: type = int):
    return list(map(t, input().split()))


def imi(N: int, t: type = int):
    return [ii(t) for _ in range(N)]


def iml(N: int, t: type = int):
    return [il(t) for _ in range(N)]


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in 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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        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_check(self, x, y):
        return self.find(x) == self.find(y)


H, W = il()
S = imi(H, str)
tree = UnionFind(H * W)
for i, j in product(range(H), range(W)):
    for d in ((-1, 0), (0, -1), (1, 0), (0, 1)):
        x = i + d[0]
        y = j + d[1]
        if 0 <= x < H and 0 <= y < W:
            if S[i][j] != S[x][y]:
                tree.union((i * W + j), (x * W + y))

k = set(tree.par)
dot = {i: 0 for i in k}
sharp = {i: 0 for i in k}
for i, j in product(range(H), range(W)):
    if S[i][j] == ".":
        dot[tree.find(i * W + j)] += 1
    else:
        sharp[tree.find(i * W + j)] += 1

ans = 0
for i in k:
    ans += dot[i] * sharp[i]
print(ans)

Solution (Python):
H,W=map(int,input().split())
S=[list(input()) for i in range(H)]
N=H*W
par=[0 for i in range(N)]
rnk=[0 for i in range(N)]
def init(n):
    for i in range(N):
        par[i]=i
        rnk[i]=0
def find(x):
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def unite(x,y):
    x=find(x)
    y=find(y)
    if x==y:
        return
    if (rnk[x]<rnk[y]):
        par[x]=y
    else:
        par[y]=x
        if(rnk[x]==rnk[y]):
            rnk[x]+=1
def same(x,y):
    return find(x)==find(y)
init(N)
dx=[0,0,1,-1]
dy=[1,-1,0,0]
for i in range(H):
    for j in range(W):
        for k in range(4):
            nx=dx[k]+i
            ny=dy[k]+j
            if 0<=nx<H and 0<=ny<W:
                if S[nx][ny]!=S[i][j]:
                    p=i*W+j
                    q=nx*W+ny
                    unite(p,q)
A=[find(i) for i in range(N)]
D=dict()
for j in range(N):
    i=A[j]
    if not(i in D):
        D[i]=[0,0]
    if S[j//W][j%W]=="
        D[i][1]+=1
    else:
        D[i][0]+=1
ans=0
for i in D:
    seq=D[i]
    ans+=seq[0]*seq[1]
print(ans)

Solution (Python):
import sys
from itertools import product

sys.setrecursionlimit(200000)


def input():
    return sys.stdin.readline()[:-1]


def ii(t: type = int):
    return t(input())


def il(t: type = int):
    return list(map(t, input().split()))


def imi(N: int, t: type = int):
    return [ii(t) for _ in range(N)]


def iml(N: int, t: type = int):
    return [il(t) for _ in range(N)]


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [0] * (n + 1)

    
    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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        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_check(self, x, y):
        return self.find(x) == self.find(y)


H, W = il()
S = imi(H, str)
tree = UnionFind(H * W)
for i, j in product(range(H), range(W)):
    for d in ((-1, 0), (0, -1), (1, 0), (0, 1)):
        x = i + d[0]
        y = j + d[1]
        if 0 <= x < H and 0 <= y < W:
            if S[i][j] != S[x][y]:
                tree.union((i * W + j), (x * W + y))

dot = [0] * (H * W)
sharp = [0] * (H * W)
for i, j in product(range(H), range(W)):
    if S[i][j] == ".":
        dot[tree.find(i * W + j)] += 1
    else:
        sharp[tree.find(i * W + j)] += 1

ans = 0
for i in range(H * W):
    ans += dot[i] * sharp[i]
print(ans)

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

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

def dfs(i,j,color): 
    if not(0<=i<h and 0<=j<w): return 0,0 
    if s[i][j]==color: return 0,0 
    if t[i][j]: return 0,0 
    
    t[i][j]=True
    c = s[i][j]
    bl, wh=0,0
    if c=='
        bl+=1
    else:
        wh+=1
    

    
    

    
    
            
    
    

    
    

    

    tmp1, tmp2 = dfs(i-1,j,s[i][j])
    bl,wh = bl+tmp1, wh+tmp2

    tmp1, tmp2 = dfs(i+1,j,s[i][j])
    bl,wh = bl+tmp1, wh+tmp2

    tmp1, tmp2 = dfs(i,j-1,s[i][j])
    bl,wh = bl+tmp1, wh+tmp2

    tmp1, tmp2 = dfs(i,j+1,s[i][j])
    bl,wh = bl+tmp1, wh+tmp2

    return bl,wh

ans = 0
for i in range(h):
    for j in range(w):
        a,b = dfs(i,j,'!')
        ans += a*b
print(ans)

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

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

def dfs(i,j,color): 
    if not(0<=i<h and 0<=j<w): return 0,0 
    if s[i][j]==color: return 0,0 
    if t[i][j]: return 0,0 
    
    t[i][j]=True
    c = s[i][j]
    bl, wh=0,0
    if c=='
        bl+=1
    else:
        wh+=1
    

    tmp1,tmp2=dfs(i+1,j,c)
    bl,wh=bl+tmp1,wh+tmp2

    tmp1,tmp2=dfs(i-1,j,c)
    bl,wh=bl+tmp1,wh+tmp2
            
    tmp1,tmp2=dfs(i,j-1,c)
    bl,wh=bl+tmp1,wh+tmp2

    tmp1,tmp2=dfs(i,j+1,c)
    bl,wh=bl+tmp1,wh+tmp2

    return bl,wh

    
    

    
    

    
    

    
    

    

ans = 0
for i in range(h):
    for j in range(w):
        a,b = dfs(i,j,'!')
        ans += a*b
print(ans)

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

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

def dfs(i,j,color): 
    if not(0<=i<h and 0<=j<w): return 0,0 
    if s[i][j]==color: return 0,0 
    if t[i][j]: return 0,0 
    
    t[i][j]=True
    c = s[i][j]
    wh, bl=0,0
    if c=='
        bl+=1
    else:
        wh+=1
    

    tmp1,tmp2=dfs(i+1,j,c)
    wh,bl=wh+tmp1,bl+tmp2

    tmp1,tmp2=dfs(i-1,j,c)
    wh,bl=wh+tmp1,bl+tmp2
            
    tmp1,tmp2=dfs(i,j-1,c)
    wh,bl=wh+tmp1,bl+tmp2

    tmp1,tmp2=dfs(i,j+1,c)
    wh,bl=wh+tmp1,bl+tmp2

    return wh,bl

    
    

    
    

    
    

    
    

    

ans = 0
for i in range(h):
    for j in range(w):
        a,b = dfs(i,j,'!')
        ans += a*b
print(ans)

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

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

def dfs(i,j,color): 
    if not(0<=i<h and 0<=j<w): return 0,0 
    if s[i][j]==color: return 0,0 
    if t[i][j]: return 0,0 
    
    t[i][j]=True
    
    wh, bl=0,0
    if s[i][j]=='
        bl+=1
    else:
        wh+=1
    

    tmp1,tmp2=dfs(i+1,j,s[i][j])
    wh,bl=wh+tmp1,bl+tmp2

    tmp1,tmp2=dfs(i-1,j,s[i][j])
    wh,bl=wh+tmp1,bl+tmp2
            
    tmp1,tmp2=dfs(i,j-1,s[i][j])
    wh,bl=wh+tmp1,bl+tmp2

    tmp1,tmp2=dfs(i,j+1,s[i][j])
    wh,bl=wh+tmp1,bl+tmp2

    return wh,bl

    
    

    
    

    
    

    
    

    

ans = 0
for i in range(h):
    for j in range(w):
        a,b = dfs(i,j,'!')
        ans += a*b
print(ans)

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

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

def dfs(i,j,color):

  if not (0<=i<h and 0<=j<w):return 0,0
  if s[i][j]==color: return 0,0
  if t[i][j]:return 0,0

  t[i][j]=True
  wh,bl=0,0
  if s[i][j]=="
    bl+=1
  else:
    wh+=1

  tmp1,tmp2=dfs(i+1,j,s[i][j])
  wh,bl=wh+tmp1,bl+tmp2

  tmp1,tmp2=dfs(i-1,j,s[i][j])
  wh,bl=wh+tmp1,bl+tmp2
        
  tmp1,tmp2=dfs(i,j-1,s[i][j])
  wh,bl=wh+tmp1,bl+tmp2

  tmp1,tmp2=dfs(i,j+1,s[i][j])
  wh,bl=wh+tmp1,bl+tmp2

  return wh,bl

ans=0
for i in range(h):
  for j in range(w):
    a,b=dfs(i,j,"!")
    ans+=a*b

print(ans)

Solution (Python):
import sys
c=0
b=0
wi=0
x=[-1,0,1,0]
y=[0,-1,0,1]
buf=[]
def one():
    return -1
def count(h,w,S,table,H,W,index):
    global buf,x,y,b,wi
    if index==1:
        b+=1
    else:
        wi+=1
    if index==1:
        S[h][w]='@'
    for i in range(4):
        if h+y[i]>=0 and h+y[i]<H and w+x[i]>=0 and w+x[i]<W:
            if table[h+y[i]][w+x[i]]==-1:
                if index==0 and S[h+y[i]][w+x[i]]=='
                    table[h+y[i]][w+x[i]]=1
                    buf.append([h+y[i],w+x[i],1])
                elif index==1 and S[h+y[i]][w+x[i]]=='.':
                    table[h+y[i]][w+x[i]]=1
                    buf.append([h+y[i],w+x[i],0])
    if buf:
        a=buf.pop(0)
        count(a[0],a[1],S,table,H,W,a[2])
sys.setrecursionlimit(10000000)
H,W=map(int,input().split())
T=[]
table=[[-1 for j in range(W)] for i in range(H)]
for i in range(H):
    T.append(input())
S=[['' for j in range(W)]for i in range(H)]
for h in range(H):
    for w in range(W):
        S[h][w]=T[h][w]
for h in range(H):
    for w in range(W):
        if S[h][w]=='
            table[h][w]=0
            count(h,w,S,table,H,W,1)
            c+=b*wi
            b=0
            wi=0
print(c)

Solution (Python):
from collections import deque

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


di = (1, 0, -1, 0)
dj = (0, 1, 0, -1)
visited = [[False] * W for _ in range(H)]

result = 0
for i in range(H):
    for j in range(W):

        if visited[i][j]:
            continue
        visited[i][j] = True

        b, w = 0, 0

        que = deque([(i, j)])
        while que:
            (ci, cj) = que.pop()
            if S[ci][cj] == '
                b += 1
            else:
                w += 1

            for d in range(4):

                ni, nj = ci + di[d], cj + dj[d]
                if not (0 <= ni < H and 0 <= nj < W):
                    continue

                if S[ci][cj] == S[ni][nj]:
                    continue

                if visited[ni][nj]:
                    continue
                visited[ni][nj] = True

                que.append((ni, nj))

        result += b * w


print(result)

Solution (Python):
class UnionFind:
    """
    - sizeを指定
    - 要素をグループにまとめる(unite) 
    - 要素同士が同じグループか判定する(isSame)
    - 分離はできない
    - par: 親の番号(はじめ par[i]==i つまりすべての頂点が根)
    - 始め各要素は別々のグループ"""
    def __init__(self, size: int):
        self.par = [-1]*size
        for i in range(size):
            self.par[i] = i 
    
    def root(self, x: int) -> int:
        """根を求める"""
        if self.par[x] == x: 
            return x
        else:
            self.par[x] = self.root(self.par[x]) 
            return self.par[x]
    
    def isSame(self, x:int, y:int)->bool:
        """x と y が同じ集合に属するか否か"""
        return self.root(x)==self.root(y)
    
    def unite(self, x:int, y:int):
        """x と y の属する集合を併合"""
        x = self.root(x)
        y = self.root(y)
        if x == y: return
        self.par[x] = y


H,W = map(int, input().split())
s = [input() for _ in range(H)]
uf = UnionFind(H*W) 

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

for h in range(H):
    for w in range(W):        
        for dh, dw in zip((0, 1), (1, 0)):
            if not(0<=h+dh<H and 0<=w+dw<W):
                continue
            if s[h][w] != s[h+dh][w+dw]: 
                uf.unite(pos2int(h, w), pos2int(h+dh, w+dw))
                
white = [0] * H*W
black = [0] * H*W
 
for h in range(H):
    for w in range(W):
        n = pos2int(h, w)
        r = uf.root(n)
        
        if s[h][w] == ".":
            white[r] += 1
        else:
            black[r] += 1


ans = 0
for h in range(H):
    for w in range(W):
        n = pos2int(h, w)
        ans += white[n] * black[n]
print(ans)

Solution (Python):
from collections import deque


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


di = (1, 0, -1, 0)
dj = (0, 1, 0, -1)

def is_valid(i, j, d):
    ni = i + di[d]
    nj = j + dj[d]
    if not (0 <= ni < H and 0 <= nj < W):
        return False
    if S[i][j] == S[ni][nj]:
        return False
    return True


result = 0
visited = [[False] * W for _ in range(H)]
for i in range(H):
    for j in range(W):

        if visited[i][j]:
            continue
        visited[i][j] = True

        b = 0
        w = 0
        que = deque()
        que.append((i, j))
        while que:
            (ci, cj) = que.pop()
            if S[ci][cj] == '
                b += 1
            else:
                w += 1

            for d in range(4):
                if not is_valid(ci, cj, d):
                    continue
                ni = ci + di[d]
                nj = cj + dj[d]
                if visited[ni][nj]:
                    continue
                visited[ni][nj] = True
                que.append((ni, nj))

        result += b * w


print(result)

Solution (Python):
from collections import deque


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


di = (1, 0, -1, 0)
dj = (0, 1, 0, -1)

def is_valid(i, j, d):
    ni = i + di[d]
    nj = j + dj[d]
    if not (0 <= ni < H and 0 <= nj < W):
        return False
    if S[i][j] == S[ni][nj]:
        return False
    return True


result = 0
visited = [[False] * W for _ in range(H)]
for i in range(H):
    for j in range(W):

        if visited[i][j]:
            continue
        visited[i][j] = True

        b = 0
        w = 0
        que = deque()
        que.append((i, j))
        while que:
            (ci, cj) = que.pop()
            if S[ci][cj] == '
                b += 1
            else:
                w += 1

            for d in range(4):
                if not is_valid(ci, cj, d):
                    continue
                ni = ci + di[d]
                nj = cj + dj[d]
                if visited[ni][nj]:
                    continue
                visited[ni][nj] = True
                que.append((ni, nj))

        result += b * w


print(result)

Solution (Python):
def c_alternating_path(H, W, Grid):
    from itertools import product
    from collections import deque

    ans = 0
    is_visited = [[False] * W for _ in range(H)]
    for h, w in product(range(H), range(W)):
        if Grid[h][w] == '
            count_white, count_black = 0, 0
            q = deque([(h, w)])
            while q:
                row, col = q.popleft()
                if is_visited[row][col]:
                    continue

                is_visited[row][col] = True
                if Grid[row][col] == '
                    count_black += 1
                else:
                    count_white += 1

                for dr, dc in [(0, -1), (1, 0), (0, 1), (-1, 0)]:
                    nr, nc = row + dr, col + dc
                    if (0 <= nr < H and 0 <= nc < W
                        and Grid[row][col] != Grid[nr][nc]
                            and not is_visited[nr][nc]):
                        q.append((nr, nc))
            ans += count_black * count_white
    return ans

H, W = [int(i) for i in input().split()]
Grid = [input() for _ in range(H)]
print(c_alternating_path(H, W, Grid))

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

X = [[0] * W for i in range(H)]
G = [[0,0] for i in range(W*H)] 
L = [[-1] * W for i in range(H)] 

for i in range(H):
    s = input()
    for j in range(W):
        if (i+j) % 2 == 0:
            if s[j] == "
                X[i][j] = 1
        else:
            if s[j] != "
                X[i][j] = 1



g = -1
for i in range(H):
    for j in range(W):
        if L[i][j] < 0:
            g += 1
            L[i][j] = g
            post = [[i,j]]
            G[g][(i+j)%2] += 1
            while post:
                pre = post
                post = []
                for ggg in pre:
                    i0, j0 = ggg
                    if i0>0 and L[i0-1][j0] < 0 and X[i0][j0] == X[i0-1][j0]:
                        post.append([i0-1,j0])
                        L[i0-1][j0] = g
                        G[g][(i0+j0+1)%2] += 1
                    if i0<H-1 and L[i0+1][j0] < 0 and X[i0][j0] == X[i0+1][j0]:
                        post.append([i0+1,j0])
                        L[i0+1][j0] = g
                        G[g][(i0+j0+1)%2] += 1
                    if j0>0 and L[i0][j0-1] < 0 and X[i0][j0] == X[i0][j0-1]:
                        post.append([i0,j0-1])
                        L[i0][j0-1] = g
                        G[g][(i0+j0+1)%2] += 1
                    if j0<W-1 and L[i0][j0+1] < 0 and X[i0][j0] == X[i0][j0+1]:
                        post.append([i0,j0+1])
                        L[i0][j0+1] = g
                        G[g][(i0+j0+1)%2] += 1
                        
            

ans = 0
for t in G:
    aa, bb = t
    ans += aa * bb
    
print(ans)

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

def path(i,j):
    p=[]
    for k in [1,-1]:
        if 0<=i+k<H:
            if S[i][j]!=S[i+k][j]:
                p.append((i+k,j))
        if 0<=j+k<W:
            if S[i][j]!=S[i][j+k]:
                p.append((i,j+k))
    return p
f = [[0 for i in range(W)] for j in range(H)]
ans=0

for i in range(H):
    for j in range(W):
        if f[i][j]==0:
            f[i][j]=1
            b=0
            w=0
            if S[i][j]=='
                b+=1
            else:
                w+=1
            que=path(i,j)

            while len(que)>0:
                tmp=[]
                for q in que:
                    q0,q1=q
                    if f[q0][q1]==0:
                        f[q0][q1]=1
                        if S[q0][q1]=='
                            b+=1
                        else:
                            w+=1
                        for p in path(q0,q1):
                            if f[p[0]][p[1]]==0:
                                tmp.append(p)
                que=tmp
            ans+=b*w
print(ans)

Solution (Python):
from collections import deque

dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]

H, W = map(int, input().split())
a = [[None for _ in range(W)] for _ in range(H)]  
reached = [[False for _ in range(W)] for _ in range(H)]
for r in range(H):
    s = input()
    for c in range(W):
        a[r][c] = (s[c] == '

ans = 0
for r in range(H):
    for c in range(W):
        if reached[r][c]: continue
        reached[r][c] = True

        b = 0
        w = 0

        dq = deque()
        dq.append((r, c))

        while dq:
            rr, cc = dq.popleft()
            if a[rr][cc]:
                b += 1
            else:
                w += 1
            for di in range(4):
                nr = rr + dr[di]
                if not (0 <= nr < H): continue

                nc = cc + dc[di]
                if not (0 <= nc < W): continue

                if a[rr][cc] == a[nr][nc]: continue

                if reached[nr][nc]: continue
                reached[nr][nc] = True

                dq.append((nr, nc))
        ans += b * w

print(ans)

Solution (Python):
H, W = map(int, input().split())
S = ['' for i in range(H)]
for i in range(H):
  S[i] = input()
R = [[[i, j] for j in range(W)] for i in range(H)]
U = [[1 for j in range(W)] for i in range(H)]
def root(A):
  if R[A[0]][A[1]] == A:
    return A
  else:
    R[A[0]][A[1]] = root(R[A[0]][A[1]])
    return R[A[0]][A[1]]
def union(A, B):
  rA = root(A)
  rB = root(B)
  if rA[0] < rB[0]:
    R[rB[0]][rB[1]] = rA
    U[rA[0]][rA[1]] += U[rB[0]][rB[1]]
  elif rB[0] < rA[0]:
    R[rA[0]][rA[1]] = rB
    U[rB[0]][rB[1]] += U[rA[0]][rA[1]]
  elif rA[1] < rB[1]:
    R[rB[0]][rB[1]] = rA
    U[rA[0]][rA[1]] += U[rB[0]][rB[1]]
  elif rB[1] < rA[1]:
    R[rA[0]][rA[1]] = rB
    U[rB[0]][rB[1]] += U[rA[0]][rA[1]]
for i in range(H):
  for j in range(W):
    if S[i][j] == ".":
      if i > 0 and S[i - 1][j] == "
        if j > 0 and S[i - 1][j - 1] == ".":
          union([i, j], [i - 1, j - 1])
        if i > 1 and S[i - 2][j] == ".":
          union([i, j], [i - 2, j])
        if j < W - 1 and S[i - 1][j + 1] == ".":
          union([i, j], [i - 1, j + 1])
      if j > 0 and S[i][j - 1] == "
        if i > 0 and S[i - 1][j - 1] == ".":
          union([i, j], [i - 1, j - 1])
        if j > 1 and S[i][j - 2] == ".":
          union([i, j], [i, j - 2])
        if i < H - 1 and S[i + 1][j - 1] == ".":
          union([i, j], [i + 1, j - 1])
      if j < W - 1 and S[i][j + 1] == "
        if i > 0 and S[i - 1][j + 1] == ".":
          union([i, j], [i - 1, j + 1])
for i in range(H):
  for j in range(W):
    root([i, j])
cnt = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == "
      if i > 0 and S[i - 1][j] == ".":
        r = R[i - 1][j]
        cnt += U[r[0]][r[1]]
      elif i < H - 1 and S[i + 1][j] == ".":
        r = R[i + 1][j]
        cnt += U[r[0]][r[1]]
      elif j > 0 and S[i][j - 1] == ".":
        r = R[i][j - 1]
        cnt += U[r[0]][r[1]]
      elif j < W - 1 and S[i][j + 1] == ".":
        r = R[i][j + 1]
        cnt += U[r[0]][r[1]]
print(cnt)

Solution (Python):

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

def func(h,w): 
    move = [(0,-1),(-1,0),(0,1),(1,0)]
    w_cnt = 0
    b_cnt = 0
    que = deque()
    que.append((h,w))
    while len(que) > 0:
        xh,xw = que.popleft()
        if visited[xh][xw] == 0:
            visited[xh][xw] = 1
            if Sn[xh][xw] == "
                b_cnt += 1
            else:
                w_cnt += 1
        else:
            continue
            
        for mh, mw in move:
            if 0 <= xh + mh < H and 0 <= xw + mw < W:
                if Sn[xh][xw] != Sn[xh + mh][xw + mw] and visited[xh + mh][xw + mw] == 0:
                    que.append((xh + mh, xw + mw))

    return b_cnt, w_cnt

cnt = 0
visited = [[0 for _ in range(W)] for _ in range(H)]

for i in range(H):
    for j in range(W):
        if Sn[i][j] == "
            b_cnt, w_cnt = func(i, j)
            cnt += b_cnt*w_cnt
            
print(cnt)

Solution (Python):


import sys
sys.setrecursionlimit(2 * 10 ** 5)

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

ans = 0

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

un_reached = [[True for i in range(W)] for j in range(H)]


def isIn(x, y):
    return 0 <= x < H and 0 <= y < W


def dfs(x, y):
    un_reached[x][y] = False
    if s[x][y] == '
        cc[1] += 1
    else:
        cc[0] += 1

    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if isIn(nx, ny) and s[nx][ny] != s[x][y] and un_reached[nx][ny]:
            dfs(nx, ny)


for i in range(H):
    for j in range(W):
        if un_reached[i][j]:
            cc = [0 for _ in range(2)]
            dfs(i, j)
            ans += cc[1]*cc[0]
print(ans)