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 defaultdict
class UnionFind():
    def __init__(self, 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

h, w = map(int, input().split())
S = []
for i in range(h):
    s = input()
    S.append(s)

uf = UnionFind(h*w)

for i in range(h):
    for j in range(w):
        if i < h - 1 and S[i][j] != S[i+1][j]:
            uf.union(i*w+j, (i+1)*w+j)
        if j < w - 1 and S[i][j] != S[i][j+1]:
            uf.union(i*w+j, i*w+j+1)

ans = 0

d = defaultdict(int)

for i in range(h*w):
    if S[i//w][i%w] == '.':
        d[uf.find(i)] += 1

for i, x in enumerate(uf.parents):
    if x < 0:
        
        cnt = -x
        ans += d[uf.find(i)] * (cnt-d[i])

print(ans)

Solution (Python):
from collections import deque
def bfs(sl, visited, sy, sx, h, w):
    q = deque([(sy,sx,sl[sy][sx])])
    visited[sy][sx] = 0
    bh_cnt = {'
    bh_cnt[sl[sy][sx]] += 1
    while q:
        y, x, bh = q.popleft()
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            ny, nx = y+j, x+k
            if ny >= h or nx >= w or ny < 0 or nx < 0:
                continue
            if sl[ny][nx] != bh and visited[ny][nx] == -1:
                visited[ny][nx] = visited[y][x] + 1
                bh_cnt[sl[ny][nx]] += 1
                q.append((ny,nx,sl[ny][nx]))
    return bh_cnt['


h,w = map(int, input().split())
sl = []
for _ in range(h):
    row = list(input())
    sl.append(row)
visited = [ [-1]*w for i in range(h)]

ans = 0
for hi in range(h):
    for wi in range(w):
        if visited[hi][wi] != -1: continue
        ans += bfs(sl, visited, hi, wi, h, w)
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]
dij=[(1,0),(0,1),(-1,0),(0,-1)]

def dfs(i,j):
    cnt=[0]*2
    color=ss[i][j]
    ss[i][j]=2
    cnt[color]+=1
    for di,dj in dij:
        ni,nj=i+di,j+dj
        if ni<0 or ni>=h or nj<0 or nj>=w:continue
        if ss[ni][nj]!=1-color:continue
        ret=dfs(ni,nj)
        cnt[0]+=ret[0]
        cnt[1] += ret[1]
    return cnt

h,w=MI()
ss=[[c=="
ans=0
for i in range(h):
    for j in range(w):
        if ss[i][j]==2:continue
        black,white=dfs(i,j)
        
        ans+=black*white
print(ans)

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

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

seen = [[0] * w for _ in range(h)]

dxdy = [(-1, 0), (1, 0), (0, -1), (0, 1)]

global ans
def dfs(x, y):
    seen[y][x] = 1
    a, b = 1, 0
    for dx, dy in dxdy:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < w and 0 <= ny < h and not seen[ny][nx] and s[y][x] != s[ny][nx]:
            p = dfs(nx, ny)
            a += p[1]
            b += p[0]
    
    return (a, b)

ans = 0
for i in range(h):
    for j in range(w):
        if not seen[i][j]:
            p = dfs(j, i)
            ans += p[0] * p[1]
print(ans)

Solution (Python):


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    
    class UnionFind():
        """
        parents : 親要素(findしない場合は根ではないことの注意)，根の場合は"-(要素数）"
        find(x):要素xの属するグループの根を返す
        size(x):要素xの属するグループの要素数を返す
        same(x,y):x,yが同じグループに属しているか返す
        members(x):要素xが属するグループに属する要素をリストで返す
        roots:全ての根の要素を返す
        group_count():グループの数を返す
        all_group_members():{根要素：[そのグループに含まれる要素のリスト]}の辞書を返す
        """
        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=MI()
    S=[]
    for i in range(H):
        s=input()
        S.append(s)
    uf=UnionFind(H*W)
    
    dx=[0,1]
    dy=[1,0]
    
    def make(ii,jj):
        return ii*W+jj
    

    
    for i in range(H):
        for j in range(W):
            for k in range(2):
                ni=i+dx[k]
                nj=j+dy[k]
                if 0<=ni<H and 0<=nj<W:
                    if S[i][j]!=S[ni][nj]:
                        uf.union(make(i,j),make(ni,nj))
                        
    ans=0
    from collections import defaultdict
    ddb = defaultdict(int)
    ddh = defaultdict(int)
    
    for i in range(H):
        for j in range(W):
            v=make(i,j)
            root=uf.find(v)
            if S[i][j]=="
                ddb[root]+=1
            else:
                ddh[root]+=1
                
    for k,v in ddb.items():
        ans+=v*ddh[k]

        
        
    print(ans)
            
    
        
main()

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
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
sys.setrecursionlimit(4100000)

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

C = [[1 for i in range(W)] for j in range(H)]
L = ['.', '
D = {'.':0, '
tx = [1, 0, -1, 0]
ty = [0, 1, 0, -1]

def dfs(x, y, c, l):
    C[x][y] = 0
    l[c] += 1
    for i in range(4):
        nx = x + tx[i]
        ny = y + ty[i]
        if 0 <= nx < H and 0 <= ny < W and C[nx][ny] and L[c] != S[nx][ny]:
            l = dfs(nx, ny, 1 - c, l)
    return l

ans = 0
for i in range(H):
    for j in range(W):
        l = dfs(i, j, D[S[i][j]], [0, 0])
        ans += l[0] * l[1]

print(ans)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





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 = IL()
data = SLs(H)

U = UnionFind(H*W)
for j in range(H):
  for i in range(W-1):
    if data[j][i] != data[j][i+1]:
      U.union(j*W+i,j*W+i+1)
for j in range(H-1):
  for i in range(W):
    if data[j][i] != data[j+1][i]:
      U.union(j*W+i,j*W+i+W)
dic = DD(lambda:[0,0])
for j in range(H):
  for i in range(W):
    dic[U.find(j*W+i)][int(data[j][i]==".")]+=1
ans = 0
for k in dic:
    ans += dic[k][0]*dic[k][1]
print(ans)

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


def to_v(i, j):
    return i*w+j


def generate_v2(v):
    i, j = divmod(v, w)
    if 0 < i:
        yield v-w
    if i < h-1:
        yield v+w
    if 0 < j:
        yield v-1
    if j < w-1:
        yield v+1


def dfs(v, c=0):
    if visited[v]:
        return
    visited[v] = 1
    cnt[c] += 1
    for v2 in generate_v2(v):
        if fld[v] == fld[v2]:
            continue
        dfs(v2, c ^ 1)


visited = [0]*n
ans = 0
for v in range(n):
    if visited[v]:
        continue
    cnt = [0, 0]
    dfs(v)
    ans += cnt[0]*cnt[1]
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
h, w = map(int, input().split())
n = h*w
fld = ''.join([input().rstrip()for _ in range(h)])
edges = [set() for _ in range(n)]


def to_v(i, j):
    return i*w+j


for i in range(h):
    for j in range(w):
        v = to_v(i, j)
        dirc = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        for di, dj in dirc:
            x, y = i+di, j+dj
            if x < 0 or h <= x or y < 0 or w <= y:
                continue
            v2 = to_v(x, y)
            if fld[v] != fld[v2]:
                edges[v].add(v2)
                edges[v2].add(v)


def dfs(v, c=0):
    if visited[v]:
        return
    visited[v] = 1
    cnt[c] += 1
    for v2 in edges[v]:
        dfs(v2, c ^ 1)


visited = [0]*n
ans = 0
for v in range(n):
    if visited[v]:
        continue
    cnt = [0, 0]
    dfs(v)
    ans += cnt[0]*cnt[1]
print(ans)

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


def to_v(i, j):
    return i*w+j


for i in range(h):
    for j in range(w):
        v = to_v(i, j)
        dirc = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        for di, dj in dirc:
            x, y = i+di, j+dj
            if x < 0 or h <= x or y < 0 or w <= y:
                continue
            v2 = to_v(x, y)
            if fld[v] != fld[v2]:
                edges[v].append(v2)
                edges[v2].append(v)


def dfs(v, c=0):
    if visited[v]:
        return
    visited[v] = 1
    cnt[c] += 1
    for v2 in edges[v]:
        dfs(v2, c ^ 1)


visited = [0]*n
ans = 0
for v in range(n):
    if visited[v]:
        continue
    cnt = [0, 0]
    dfs(v)
    ans += cnt[0]*cnt[1]
print(ans)

Solution (Python):
from collections import deque

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

used = [[0]*w for i in range(h)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
ans = 0

for i in range(h):
    for j in range(w):
        if used[i][j]:
            continue
        cw = 0
        cb = 0
        q = deque([])
        q.append([i,j])
        used[i][j] = 1
        while q:
            x,y = q.popleft()
            if s[x][y] == "
                cb += 1
            else:
                cw += 1
            for k in range(4):
                nx = x+dx[k]
                ny = y+dy[k]
                if 0 <= nx < h and 0 <= ny < w:
                    if (not used[nx][ny]) and s[x][y] != s[nx][ny]:
                        used[nx][ny] = 1
                        q.append([nx,ny])
        ans += cw*cb
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10**7)
h,w = map(int,input().split())
s = [list(input()) for i in range(h)]

dp = [[-1]*w for i in range(h)]

co = [0]
dx = [0,0,1,-1]
dy = [1,-1,0,0]
def dfs(x,y,c):
    count = 0
    dp[x][y] = 1
    if s[x][y] == "
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] == "." and dp[nx][ny] == -1:
                count += 1
                count += dfs(nx,ny,c+1)
    elif s[x][y] == ".":
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] == "
                l.append((nx,ny))
                count += dfs(nx,ny,c+1)
    return count
            
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == "
            l = []
            count = dfs(i,j,0)
            ans += count*(len(l)+1)
            s[i][j] = "x"
            for x,y in l:
                s[x][y] = "x"
print(ans)

Solution (Python):
H, W = map(int, input().split())
S = [['.']*(W+2)] + [['.'] + list(input()) + ['.'] for _ in range(H)] + [['.']*(W+2)]
for i in range(1, H+1):
  S[i][0] = S[i][1]
  S[i][-1] = S[i][-2]
for i in range(1, W+1):
  S[0][i] = S[1][i]
  S[-1][i] = S[-2][i]
S[0][0] = S[0][1]
S[-1][0] = S[-2][0]
S[0][-1] = S[0][-2]
S[-1][-1] = S[-2][-1]
V = [[0 for _ in range(W+2)] for i in range(H+2)]
num = 0
for i in range(1, H+1):
  for j in range(1, W+1):
    if S[i][j] == '
      V[i][j] = 1
      p = [[i, j]]
      cnt = 1
      pnt = 0
      D = {'.': 0, '
      D[S[i][j]] = 1
      while pnt < cnt:
        n = cnt
        for k in range(pnt, cnt):
          x = p[k][:]
          y = S[x[0]][x[1]][:]
          if S[x[0]-1][x[1]] != y and V[x[0]-1][x[1]] == 0:
            V[x[0]-1][x[1]] = 1
            p.append([x[0]-1, x[1]])
            D[S[x[0]-1][x[1]]] += 1
            cnt += 1
          if S[x[0]+1][x[1]] != y and V[x[0]+1][x[1]] == 0:
            V[x[0]+1][x[1]] = 1
            p.append([x[0]+1, x[1]])
            D[S[x[0]+1][x[1]]] += 1
            cnt += 1
          if S[x[0]][x[1]-1] != y and V[x[0]][x[1]-1] == 0:
            V[x[0]][x[1]-1] = 1
            p.append([x[0], x[1]-1])
            D[S[x[0]][x[1]-1]] += 1
            cnt += 1
          if S[x[0]][x[1]+1] != y and V[x[0]][x[1]+1] == 0:
            V[x[0]][x[1]+1] = 1
            p.append([x[0], x[1]+1])
            D[S[x[0]][x[1]+1]] += 1
            cnt += 1
        pnt = n
      num += D['.'] * D['
print(num)

Solution (Python):
from collections import deque
def bfs(S,H,W,sh,sw):
    black,white=0,0
    d=deque()
    d.append([sh,sw])
    if S[sh][sw]=='
        black+=1
    elif S[sh][sw]=='.':
        white+=1
    seen[sh][sw]=1
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    while(len(d)!=0):
        h=d[0][0]
        w=d[0][1]
        d.popleft()
        for dir in range(4):
            nh=h+dx[dir]
            nw=w+dy[dir]
            if(nh>H-1 or nh<0 or nw>W-1 or nw<0):
                continue
            if(seen[nh][nw] or S[nh][nw]==S[h][w]):
                continue
            if S[nh][nw]=='
                black+=1
            else:
                white+=1
            seen[nh][nw]=1
            d.append([nh,nw])
    return white,black

H,W=map(int,input().split())
G=[list(input()) for i in range(H)]
seen=[[0]*W for i in range(H)]
ans=0

for i in range(H):
    for j in range(W):
        if not seen[i][j]:
            w,b=bfs(G,H,W,i,j)
            ans+=w*b
print(ans)

Solution (Python):
from collections import deque
h , w = map(int,input().split())
ma = [list(input()) for i in range(h)]
visit = [[False for i in range(w)] for j in range(h)]
ans = 0
muki = [(0,1),(0,-1),(1,0),(-1,0)]
for i in range(h):
    for j in range(w):
        if ma[i][j] == "
            visit[i][j] = True
            d = deque()
            d.append((i,j,1))
            kuro = 1
            siro = 0
            while d:
                nowx , nowy , p = d.popleft()
                for a,b in muki:
                    nex = nowx + a
                    ney = nowy + b
                    if 0 <= nex <= h-1 and 0 <= ney <= w-1:
                        if not visit[nex][ney]:
                            if p == 1 and ma[nex][ney] == ".":
                                d.append((nex,ney,0))
                                siro += 1
                                visit[nex][ney] = True
                            if p == 0 and ma[nex][ney] == "
                                d.append((nex,ney,1))
                                kuro += 1
                                visit[nex][ney] = True
            ans += kuro*siro
print(ans)

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

dct = {"


def f(c):
    return dct[c]


h, w = map(int, input().split())
s = [[2] * (w + 2)]
for _ in range(h):
    s.append([2] + list(map(f, input())) + [2])
s.append([2] * (w + 2))

d = [(-1, 0), (1, 0), (0, -1), (0, 1)]


def dfs(col, hh, ww):
    if s[hh][ww] != col:
        return

    cnt[col] += 1
    s[hh][ww] = 2

    for dh, dw in d:
        nh = hh + dh
        nw = ww + dw
        dfs(1-col, nh, nw)


ans = 0
for hi in range(1, h + 1):
    for wi in range(1, w + 1):
        cnt = [0, 0]
        if s[hi][wi] != 2:
            dfs(s[hi][wi], hi, wi)
        ans += cnt[0] * cnt[1]

print(ans)

Solution (Python):


import sys
sys.setrecursionlimit(10 ** 7)

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


def dfs(h, w, ph, pw):
    if M[h][w] == '.':
        bc, wc = 0, 1
    else:
        bc, wc = 1, 0
    for (dh, dw) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        nh, nw = h + dh, w + dw
        if nh < 0 or H <= nh or nw < 0 or W <= nw:
            continue
        if nh == ph and nw == pw:
            continue
        if seen[nh][nw]:
            continue
        if M[nh][nw] == M[h][w]:
            continue
        seen[nh][nw] = True
        b_add, w_add = dfs(nh, nw, h, w)
        bc += b_add
        wc += w_add
    return bc, wc

ans = 0
for h in range(H):
    for w in range(W):
        if seen[h][w] == False:
            seen[h][w] = True
            b, w = dfs(h, w, -1, -1)
            ans += b * w
print(ans)

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

def dfs(bx, by, sx, sy):
    if s[sx][sy] == '.':
        b_cnt, w_cnt = 0, 1
    else:
        b_cnt, w_cnt = 1, 0
    for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        px, py = sx + dx, sy + dy
        
        if bx == px and by == py:
            
            continue
        if px < 0 or h <= px or py < 0 or w <= py:
            
            continue
        if seen[px][py]:
            
            continue
        if s[sx][sy] == s[px][py]:
            
            continue
        seen[px][py] = True
        b_add, w_add = dfs(sx, sy, px, py)
        b_cnt += b_add
        w_cnt += w_add

    return b_cnt, w_cnt

ans = 0

for i in range(h):
    for j in range(w):
        if seen[i][j] == False:
            seen[i][j] = True
            b_cnt, w_cnt = dfs(-1, -1, i, j)
            ans += b_cnt * w_cnt

print(ans)

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

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

visited = set()
def dfs(x, y, c, white, black):
  global visited
  for dx, dy in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
    xx = x + dx; yy = y + dy
    if 0<=xx<H and 0<=yy<W and (xx, yy) not in visited and S[xx][yy]!=c:
      cc = S[xx][yy]
      if cc == '.':
        white += 1
      else:
        black += 1
      visited.add((xx, yy))
      white, black = dfs(xx, yy, cc, white, black)
  return white, black

ans = 0
for x in range(H):
  for y in range(W):
    if (x, y) not in visited:
      visited.add((x, y))
      c = S[x][y]
      if c == '.':
        white = 1; black = 0
      else:
        white = 0; black = 1
      white, black = dfs(x, y, c, white, black)
      ans += white * black

print(ans)

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

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

visited = set()
def dfs(x, y, c, white, black):
  global visited
  for dx, dy in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
    xx = x + dx; yy = y + dy
    if 0<=xx<H and 0<=yy<W and (xx, yy) not in visited and S[xx][yy]!=c:
      cc = S[xx][yy]
      if cc == '.':
        white.add((xx, yy))
      else:
        black.add((xx, yy))
      visited.add((xx, yy))
      white, black = dfs(xx, yy, cc, white, black)
  return white, black

ans = 0
for x in range(H):
  for y in range(W):
    if (x, y) not in visited:
      visited.add((x, y))
      c = S[x][y]
      if c == '.':
        white = set(((x, y), )); black = set()
      else:
        white = set(); black = set(((x, y), ))
      white, black = dfs(x, y, c, white, black)
      ans += len(white) * len(black)

print(ans)

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

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

visited = set()
def dfs(x, y, c, white, black):
  global visited
  for dx, dy in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
    xx = x + dx; yy = y + dy
    if 0<=xx<H and 0<=yy<W and (xx, yy) not in visited and S[xx][yy]!=c:
      cc = S[xx][yy]
      if cc == '.':
        white.add((xx, yy))
      else:
        black.add((xx, yy))
      visited.add((xx, yy))
      white, black = dfs(xx, yy, cc, white, black)
  return white, black

ans = 0
for x in range(H):
  for y in range(W):
    if (x, y) not in visited:
      visited.add((x, y))
      c = S[x][y]
      if c == '.':
        white = set(((x, y), )); black = set()
      else:
        white = set(); black = set(((x, y), ))
      white, black = dfs(x, y, c, white, black)
      ans += len(white) * len(black)

print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10**6)
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
dx = (0, 0, 1, -1)
dy = (1, -1, 0, 0)
seen = [[False] * w for _ in range(h)]

numb = 0
numw = 0


def dfs(x, y):
    global numb, numw
    seen[x][y] = True
    if s[x][y] == '
        numb += 1
    else:
        numw += 1
    for di in range(4):
        nx = x + dx[di]
        ny = y + dy[di]
        if (nx < 0 or nx >= h or ny < 0 or ny >= w):
            continue
        if s[x][y] == s[nx][ny]:
            continue
        if seen[nx][ny]:
            continue
        dfs(nx, ny)


ans = 0
for x in range(h):
    for y in range(w):
        if seen[x][y]:
            continue
        if s[x][y] == '.':
            continue
        numb = 0
        numw = 0
        dfs(x, y)
        ans += numb * numw
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
dx = (0, 0, 1, -1)
dy = (1, -1, 0, 0)
seen = [[False] * w for _ in range(h)]

numb = 0
numw = 0


def dfs(x, y):
    global numb, numw
    seen[x][y] = True
    if s[x][y] == '
        numb += 1
    else:
        numw += 1
    for di in range(4):
        nx = x + dx[di]
        ny = y + dy[di]
        if (nx < 0 or nx >= h or ny < 0 or ny >= w):
            continue
        if s[x][y] == s[nx][ny]:
            continue
        if seen[nx][ny]:
            continue
        dfs(nx, ny)


ans = 0
for x in range(h):
    for y in range(w):
        if seen[x][y]:
            continue
        if s[x][y] == '.':
            continue
        numb = 0
        numw = 0
        dfs(x, y)
        ans += numb * numw
print(ans)