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 numpy as np
from collections import deque
h, w = map(int, input().split())
s = [input() for _ in range(h)]

segment = [[0]*w for _ in range(h)]
idx = 1
dxy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
for y in range(h):
    for x in range(w):
        if segment[y][x] == 0:
            segment[y][x] = idx
            state = s[y][x]
            que = deque([[y, x, state]])
            while len(que) > 0:
                y_cur, x_cur, state = que.popleft()
                for dx, dy in dxy:
                    y_next = y_cur + dy
                    x_next = x_cur + dx
                    state_next = '.' if state == '
                    if x_next < 0 or y_next < 0 or x_next >= w or y_next >= h:
                        continue
                    elif s[y_next][x_next] != state_next:
                        continue
                    elif segment[y_next][x_next] == 0:
                        segment[y_next][x_next] = idx
                        que.append((y_next, x_next, state_next))
            idx += 1


idx_max = idx
nbw = [[0, 0] for _ in range(idx_max+1)]
for y in range(h):
    for x in range(w):
        idx = segment[y][x]
        if s[y][x] == '
            nbw[idx][0] += 1
        else:
            nbw[idx][1] += 1
ans = 0
for nb, nw in nbw:
    ans += nb*nw
print(ans)

Solution (Python):
def solve(H, W, Ss):
    d = [[-1 for __ in range(W)] for _ in range(H)]

    index = 0
    for (sh, sw) in [(h, w) for h in range(0, H) for w in range(0, W)]:
        if d[sh][sw] == -1:
            que = [(sh, sw)]
            index += 1
            d[sh][sw] = index

            while len(que):
                h, w = que.pop()
                for (hi, wi) in [(h + 1, w), (h - 1, w), (h, w - 1), (h, w + 1)]:
                    if 0 <= hi < H and 0 <= wi < W:
                        if Ss[hi][wi] != Ss[h][w] and d[hi][wi] == -1:
                            que.append((hi, wi))
                            d[hi][wi] = index
    c = [[0, 0] for _ in range(index + 1)]
    for h in range(0, H):
        for w in range(0, W):
            if Ss[h][w] == ".":
                c[d[h][w]][0] += 1
            elif Ss[h][w] == "
                c[d[h][w]][1] += 1
    ans = sum([b * w for (w, b) in c])
    return ans

if __name__ == "__main__":
    H, W = tuple(map(int, input().split(" ")))
    Ss = list([input() for l in range(H)])
    print(solve(H, W, Ss))

Solution (Python):
import sys
sys.setrecursionlimit(400*400*1000)
from collections import Counter
def rec(union_id, i, j):
    symbol = S[i][j]
    if union_white[i][j] != 0:
        return
    if symbol == '.':
        union_white[i][j] = union_id
        next_symbol = '
    else:
        union_white[i][j] = -1
        next_symbol = '.'
        union_black[union_id] += 1

    if i >= 1 and S[i-1][j] == next_symbol:
        rec(union_id, i-1, j)
    if i < H-1 and S[i+1][j] == next_symbol:
        rec(union_id, i+1, j)
    if j >= 1 and S[i][j-1] == next_symbol:
        rec(union_id, i, j-1)
    if j < W-1 and S[i][j+1] == next_symbol:
        rec(union_id, i, j+1)

    return
H, W = map(int, input().split())
S = [input() for h in range(H)]
ans = 0
union_white = [[0 for w in range(W)]for h in range(H)]
union_black = Counter()
count_black = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '.' or union_white[i][j] != 0:
            continue
        count_black += 1
        rec(count_black, i, j)

counter = Counter([x for Si in union_white for x in Si])
ans = 0



for i in union_black.keys():
    ans += counter[i] * union_black[i]

print(ans)

Solution (Python):
import itertools
import sys
sys.setrecursionlimit(1000000)
h, w = map(int, input().split())
s_list = []
for i in range(h):
  s_list.append(list(input()))
res = 0
check_list = set()

def rec_create_area(point, tmp_area, current_str):
  new_point_list = []
  new_point_list.append((point[0] + 1, point[1]))
  new_point_list.append((point[0], point[1] + 1))
  new_point_list.append((point[0] - 1, point[1]))
  new_point_list.append((point[0], point[1] - 1))
  for new_point in new_point_list:
    if new_point[0] >= h or new_point[1] >= w or new_point[0] < 0 or new_point[1]  < 0:
      continue
    if new_point in check_list:
      continue
    new_str = s_list[new_point[0]][new_point[1]]
    if new_str == current_str:
      continue
    if new_str == "
      tmp_area[0] += 1
    else:
      tmp_area[1] += 1
    check_list.add(new_point)
    rec_create_area(new_point, tmp_area, new_str)
  
for a, b in itertools.product(range(h), range(w)):
  check_point = (a, b)
  if check_point in check_list:
    continue
  check_list.add(check_point)
  current_str = s_list[check_point[0]][check_point[1]]
  if current_str == "
    tmp_area = [1, 0]
  else:
    tmp_area = [0, 1]
  rec_create_area(check_point, tmp_area, current_str)
  res += tmp_area[0] * tmp_area[1]
  
print(res)

Solution (Python):
import sys
sys.setrecursionlimit(400*400*400)

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

mask = ["".join(["

masked_S = [[1 if S[i][j] == mask[i][j] else 0 for j in range(W)] for i in range(H)]

S_colored = [[-1 for j in range(W)] for i in range(H)]

color_count = dict()


def fill(i, j, color):
    S_colored[i][j] = color

    if S[i][j] == "
        color_count[color][0] += 1
    else:
        color_count[color][1] += 1

    for yx in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
        dy, dx = yx
        i2, j2 = i + dy, j + dx

        if i2 < 0 or i2 >= H or j2 < 0 or j2 >= W:
            continue

        if S_colored[i2][j2] != -1:
            continue

        if masked_S[i2][j2] != masked_S[i][j]:
            continue

        fill(i2, j2, color)


def main():
    color = -1
    for i in range(H):
        for j in range(W):
            if S_colored[i][j] != -1:
                continue
            color += 1
            color_count[color] = [0, 0]
            fill(i, j, color)

    result = 0
    for k in color_count.keys():
        result += color_count[k][0] * color_count[k][1]

    print(result)

if __name__ == '__main__':
    main()

Solution (Python):
class UnionFind(object):
 
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]
 
    def find(self, x):
        if self.table[x] < 0:
            return x
        self.table[x] = self.find(self.table[x])
        return self.table[x]
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 == s2:
            return False
        if self.table[s1] > self.table[s2]:
            s1, s2 = s2, s1
        self.table[s1] += self.table[s2]
        self.table[s2] = s1
        return True

H, W = list(map(int, input().split()))
S = list(input() for _ in range(H))
uf = UnionFind(H*W)

def get(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 (h + dh) >= H or (w + dw) >= W:
                continue
            if S[h][w] != S[h+dh][w+dw]:
                uf.union(get(h, w), get(h+dh, w+dw))


from itertools import product

C1 = []
C2 = []

for h in range(H):
    for w in range(W):
        if S[h][w] == ".":
            C1.append((h, w))
        else:
            C2.append((h, w))

white = [0] * (H * W)
black = [0] * (H * W)

for h in range(H):
    for w in range(W):
        n = get(h, w)
        par = uf.find(n)
        
        if par < 0:
            par = n
        if S[h][w] == ".":
            white[par] += 1
        else:
            black[par] += 1
            
ans = 0


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

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

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

INF = int(1e12)

def dfs(h, w, p):
    b_cnt = 0
    w_cnt = 0
    if h < 0 or h >= H or w < 0 or w >= W:
        return 0, 0
    if S[h][w] == p or S[h][w] == 'x':
        return 0, 0
    if S[h][w] == '
        b_cnt += 1
    elif S[h][w] == '.':
        w_cnt += 1
    t = S[h][w]
    S[h][w] = 'x'

    for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
        res = dfs(h + dh, w + dw, t)
        b_cnt += res[0]
        w_cnt += res[1]

    return (b_cnt, w_cnt)

ans = 0

for h in range(H):
    for w in range(W):
        if S[h][w] == '
            b_cnt, w_cnt = dfs(h, w, '.')
            ans += b_cnt * w_cnt

print(ans)

Solution (Python):
from collections import deque
h, w = map(int, input().split())
s = [list(input()) for i in range(h)]

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

usedall = set()
ans = 0

for j in range(h):
    for i in range(w):
        if (i, j) in usedall:
            continue

        used = {(i, j)}
        usedall.add((i, j))
        q = deque([(i, j)])

        while q:
            ii, jj = q.popleft()
            cur = s[jj][ii]

            for k in range(4):
                if not (0 <= ii + dx[k] < w):
                    continue
                if not (0 <= jj + dy[k] < h):
                    continue

                if s[jj + dy[k]][ii + dx[k]] == cur:
                    continue
                if (ii + dx[k], jj + dy[k]) in used:
                    continue

                used.add((ii + dx[k], jj + dy[k]))
                usedall.add((ii + dx[k], jj + dy[k]))
                q.append((ii + dx[k], jj + dy[k]))

        black = 0
        white = 0
        for m, n in used:
            if s[n][m] == "
                black += 1
            else:
                white += 1

        ans += black * white

print(ans)

Solution (Python):
class UnionFind():
    
    
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    
    def find(self, x):
        while self.table[x] >= 0:
            
            x = self.table[x]
        return x

    
    def union(self, x, y):
        s1 = self.find(x)  
        s2 = self.find(y)
        if s1 != s2:  
            if self.table[s1] != self.table[s2]:  
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                else:
                    self.table[s1] = s2
            else:
                
                
                self.table[s1] += -1
                self.table[s2] = s1
        return


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

union = UnionFind(h * w)

for i in range(h):
    for j in range(w):
        if i > 0 and s[i][j] != s[i - 1][j]:
            union.union(w * i + j, w * (i - 1) + j)
        if j > 0 and s[i][j] != s[i][j - 1]:
            union.union(w * i + j, w * i + (j - 1))
out = [[0, 0] for _ in range(h * w)]
for i in range(h):
    for j in range(w):
        if s[i][j] == "
            out[union.find(w * i + j)][0] += 1
        else:
            out[union.find(w * i + j)][1] += 1
count = 0
for _out in out:
    count += _out[0] * _out[1]
print(count)

Solution (Python):
H,W = map(int,input().split())
class UnionFind:
    def __init__(self, size):
        
        
        self.table = [-1 for _ in range(size)]

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

    
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False


S = [input() for i in range(H)]
u = UnionFind(H*W)
d = [(-1,0),(1,0),(0,-1),(0,1)]
for x in range(H):
    for y in range(W):
        for dx,dy in d:
            if x+dx<0 or x+dx>=H or y+dy<0 or y+dy>=W:
                continue
            if S[x+dx][y+dy] == S[x][y]:
                continue
            u.union(x+H*y,x+dx+H*(y+dy))

from collections import defaultdict
d = defaultdict(lambda:[[],[]])

for x in range(H):
    for y in range(W):
        if S[x][y] == '
            d[u.find(x+H*y)][0].append((x,y))
        else:
            d[u.find(x+H*y)][1].append((x,y))

ans = 0
for key in d:
    ans += len(d[key][0])*len(d[key][1])
print(ans)

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

def trace(i, j, S, col, num_color):
    next_col = 1 - col
    num_color[col] += 1
    S[i][j] = 2
    if S[i-1][j] == next_col:
        trace(i-1, j, S, next_col, num_color)
    if S[i][j-1] == next_col:
        trace(i, j-1, S, next_col, num_color)
    if S[i+1][j] == next_col:
        trace(i+1, j, S, next_col, num_color)
    if S[i][j+1] == next_col:
        trace(i, j+1, S, next_col, num_color)
    return num_color[0] * num_color[1]

def main():
    H, W = map(int, input().split())
    
    S = [[2] * (W+2)]
    for _ in range(H):
        S.append([2] + [0 if s == '
    S.append([2] * (W+2))
    num_comb = 0
    for i in range(1, H+1):
        for j in range(1, W+1):
            if S[i][j] == 0:
                num_color = [0, 0]
                num_comb += trace(i, j, S, 0, num_color)
    print(num_comb)

main()

Solution (Python):
import collections
H,W=map(int,input().split())
S=[input() for i in [0]*H]
M=[[-1]*W for _ in [0]*H]
k=0
for y in range(H):
    for x in range(W):
        if M[y][x]!=-1:continue 
        M[y][x]=k
        Q=collections.deque()
        Q.append((y,x))
        while len(Q)>0:
            i,j=Q.popleft()
            s=S[i][j]
            if i+1<H and M[i+1][j]==-1 and s!=S[i+1][j]:
                M[i+1][j]=k
                Q.append((i+1,j))
            if i-1>=0 and M[i-1][j]==-1 and s!=S[i-1][j]:
                M[i-1][j]=k
                Q.append((i-1,j))
            if j+1<W and M[i][j+1]==-1 and s!=S[i][j+1]:
                M[i][j+1]=k
                Q.append((i,j+1))
            if j-1>=0 and M[i][j-1]==-1 and s!=S[i][j-1]:
                M[i][j-1]=k
                Q.append((i,j-1))
            
        k+=1
ds={}
dd={}
for i in range(H):
    for j in range(W):
        m=M[i][j]
        if S[i][j]=='
        else:dd[m]=dd.get(m,0)+1
r=0
for i in range(k):
    r += ds.get(i,0)*dd.get(i,0)
print(r)

Solution (Python):
import sys

sys.setrecursionlimit(2000000)


def update(M, S, i, j, H, W, cluster):
    for i_n in [i - 1, i, i + 1]:
        for j_n in [j - 1, j, j + 1]:
            if i_n >= H or i_n < 0:
                continue
            if j_n >= W or j_n < 0:
                continue

            if i_n == i and j_n == j:
                continue
            if abs(i - i_n) + abs(j - j_n) == 2:
                continue

            if S[i][j] != S[i_n][j_n] and M[i_n][j_n] == 0:
                
                M[i_n][j_n] = cluster
                update(M, S, i_n, j_n, H, W, cluster)


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

cluster = 1
counts_B = {}
counts_W = {}
M = [[0 for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        if M[i][j] == 0:
            M[i][j] = cluster
            update(M, S, i, j, H, W, cluster)
            cluster = cluster + 1
        counts_B[M[i][j]] = 0
        counts_W[M[i][j]] = 0


for i in range(H):
    for j in range(W):
        if S[i][j] == '
            counts_B[M[i][j]] += 1
        else:
            counts_W[M[i][j]] += 1

    
    

total = 0
for k in counts_B.keys():
    if k in counts_W:
        total += counts_B[k] * counts_W[k]
    

print(total)

Solution (Python):


import itertools
import sys


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


class UnionFind(object):

    def __init__(self, number_of_nodes):
        self.par = list(range(number_of_nodes))
        self.rank = [0] * number_of_nodes
        self.groups = [{i} for i in range(number_of_nodes)]

    def root(self, node):
        if self.par[node] == node:
            return node
        else:
            r = self.root(self.par[node])
            self.par[node] = r
            return r

    def in_the_same_set(self, node1, node2):
        return self.root(node1) == self.root(node2)

    def elements_of_group(self, node):
        return self.groups[self.root(node)]

    def unite(self, node1, node2):
        x = self.root(node1)
        y = self.root(node2)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            self.par[y] = x
            self.groups[x].update(self.groups[y])
            self.groups[y].clear()
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


def solve(h, w, stage):
    n = h * w
    uf = UnionFind(n)
    for r0, c0 in itertools.product(range(h), range(w)):
        x0 = w * r0 + c0
        ib = stage[r0][c0]
        for dr, dc in DELTAS:
            r, c = r0 + dr, c0 + dc
            if 0 <= r < h and 0 <= c < w and ib != stage[r][c]:
                x = w * r + c
                uf.unite(x0, x)
    res = 0
    is_black = [None] * n
    for r0, c0 in itertools.product(range(h), range(w)):
        x0 = w * r0 + c0
        is_black[x0] = stage[r0][c0]
    for x1 in range(n):
        eg = uf.groups[x1]
        
        total = len(eg)
        num_black = sum(is_black[x] for x in eg)
        res += (total - num_black) * num_black
    return res


def main():
    h, w = (int(z) for z in input().split())
    stage = [[c == "
    res = solve(h, w, stage)
    print(res)


if __name__ == "__main__":
    main()

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):
from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)
H,W=map(int,input().split())
Map=[input() for i in range(H)]
G=[[[] for i in range(W)] for i in range(H)]
for i in range(H):
  for j in range(W):
    if i>=1:
      if Map[i-1][j]!=Map[i][j]:
        G[i][j].append((i-1,j))
    if j>=1:
      if Map[i][j-1]!=Map[i][j]:
        G[i][j].append((i,j-1))
    if i<=H-2:
      if Map[i+1][j]!=Map[i][j]:
        G[i][j].append((i+1,j))
    if j<=W-2:
      if Map[i][j+1]!=Map[i][j]:
        G[i][j].append((i,j+1))
Visited=[[False]*W for i in range(H)]
def dfs(x,y):
  w,b=0,0
  if Visited[x][y]:
    return (0,0)
  Visited[x][y]=True
  if Map[x][y]==".":
    w+=1
  else:
    b+=1
  for p,q in G[x][y]:
    if not Visited[p][q]:
      w_,b_=dfs(p,q)
      w+=w_
      b+=b_
  return (w,b)
ans=0
for i in range(H):
  for j in range(W):
    p,q=dfs(i,j)
    ans+=p*q
print(ans)

Solution (Python):




import sys


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

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

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

t = 1


def f(h, w):
    cb = cw = 0
    dh = [1, -1, 0, 0]
    dw = [0, 0, 1, -1]

    for i in range(4):
        h2 = h + dh[i]
        w2 = w + dw[i]
        if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
            
            if T[h2][w2] == 0:
                if S[h][w] != S[h2][w2]:
                    T[h2][w2] = 1
                    if S[h2][w2] == "
                        cb += 1
                    if S[h2][w2] == ".":
                        cw += 1
                    cb2, cw2 = f(h2, w2)
                    cb += cb2
                    cw += cw2
    return cb, cw


area = []
for h in range(H):
    for w in range(W):
        if S[h][w] == "
            tmp = f(h, w)
            if tmp[0]*tmp[1] != 0:
                area.append(tmp)

ans = 0
for a in area:
    ans += a[0]*a[1]

print(ans)

Solution (Python):

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

def candidate(hi,wi):
    for d in [[1,0],[0,1],[-1,0],[0,-1]]:
        dh = hi+d[0]
        dw = wi+d[1]
        if h>dh>=0 and w>dw>=0 and sf[hi][wi]!=sf[dh][dw]:
            return True
    return False

csf = [[False for _ in range(w)] for _ in range(h)]
for hi in range(h):
    for wi in range(w):
        csf[hi][wi] = candidate(hi,wi)
res = 0
used = [[False for _ in range(w)] for _ in range(h)]
for hi in range(h):
    for wi in range(w):
        if used[hi][wi]:
            continue
        st = [(hi,wi,sf[hi][wi])]
        nb = 0
        nw = 0
        
        while len(st)>0:
            s = st.pop()
            
            if csf[s[0]][s[1]] and not used[s[0]][s[1]]:
                used[s[0]][s[1]] = True
                if s[2] == "
                    nb += 1
                else:
                    nw += 1
                for d in [[1,0],[0,1],[-1,0],[0,-1]]:
                    dh = s[0]+d[0]
                    dw = s[1]+d[1]
                    if h>dh>=0 and w>dw>=0 and csf[dh][dw] and not used[dh][dw] and sf[s[0]][s[1]]!=sf[dh][dw]:
                        st.append((dh,dw,sf[dh][dw]))
        res += nb*nw
print(res)

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

def dfs(h,w,i,c):
    
    V[h][w] = i
    
    if h>0 and V[h-1][w]==0:
        if c=="
            dfs(h-1,w,i,".")
        elif c=="." and S[h-1][w]=="
            dfs(h-1,w,i,"
    
    if w>0 and V[h][w-1]==0:
        if c=="
            dfs(h,w-1,i,".")
        elif c=="." and S[h][w-1]=="
            dfs(h,w-1,i,"
    
    if h<H-1 and V[h+1][w]==0:
        if c=="
            dfs(h+1,w,i,".")
        elif c=="." and S[h+1][w]=="
            dfs(h+1,w,i,"
    
    if w<W-1 and V[h][w+1]==0:
        if c=="
            dfs(h,w+1,i,".")
        elif c=="." and S[h][w+1]=="
            dfs(h,w+1,i,"

V = [[0 for _ in range(W)] for _ in range(H)]
ans = 0
i = 0
for h in range(H):
    for w in range(W):
        if S[h][w]=="
            i += 1
            dfs(h,w,i,"


cnt_b = [0]*i
cnt_w = [0]*i

for h in range(H):
    for w in range(W):
        group = V[h][w]
        if group != 0:
            if S[h][w]=="
                cnt_b[group-1] += 1
            else:
                cnt_w[group-1] += 1

ans = 0
for i in range(len(cnt_b)):
    ans += cnt_b[i]*cnt_w[i]

print(ans)

Solution (Python):
import sys

def 解():
    input = sys.stdin.readline
    H,W = [int(_) for _ in input().split()]
    aM = [""]*H
    for i in range(H):
        aM[i] = input().rstrip()

    adxy=[(0,1),(1,0),(-1,0),(0,-1)]
    dsVBs=set()

    def bfsM(i,j):
        aS = [(i,j)]
        dsV = set()
        dsVB = set()
        iC = 0
        while aS:
            th,tw = aS[0]
            del aS[0]
            if aM[th][tw] == ".":
                iC += 1
                for dh,dw in adxy:
                    nh,nw=dh+th,dw+tw
                    nP = (nh,nw)
                    if 0 <= nh < H and 0 <= nw < W:
                        if aM[nh][nw] == "
                            aS.append(nP)
                            dsV.add(nP)
                            dsVB.add(nP)
            else:
                for dh,dw in adxy:
                    nh,nw=dh+th,dw+tw
                    nP = (nh,nw)
                    if 0 <= nh < H and 0 <= nw < W:
                        if aM[nh][nw] == "." and nP not in dsV:
                            aS.append(nP)
                            dsV.add(nP)
        iB = len(dsVB)
        for nP in dsVB:
            dsVBs.add(nP)
        return iC*iB

    iAns = 0
    for i in range(H):
        for j in range(W):
            if aM[i][j] == "
                iAns += bfsM(i,j)
    print(iAns)
解()

Solution (Python):



import sys


def main():
    h,w = map(int, sys.stdin.readline().rstrip().split(' '))
    s = []
    for _ in range(h):
        s.append(sys.stdin.readline().rstrip())

    taboo = set()
    flg = True
    c = 0
    while flg:
        flg = True
        for i in range(h*w):
            x, y = i%h, i//h
            if (x,y) in taboo:
                continue
            flg = False
            q = [(x,y)]
            taboo.add((x,y))
            
            white, black = 0,0
            while len(q) > 0:
                x, y = q.pop()
                color = s[x][y]
                if color == ".":
                    white +=1
                else:
                    black += 1
                for v in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):
                    if v[0] >= 0 and v[0] < h and v[1] >= 0 and v[1] < w:
                        newcolor = s[v[0]][v[1]]
                        if color == newcolor or (v[0], v[1]) in taboo:
                            continue
                        q.append((v[0], v[1]))
                        taboo.add((v[0], v[1]))
                        
            
            c += white * black
    print(c)



    
if __name__=="__main__":
    main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, S):
    g = defaultdict(dict)
    for i, r in enumerate(S):
        for j, c in enumerate(r):
            if i > 0 and S[i-1][j] != c:
                g[(i, j)][(i-1, j)] = 1
                g[(i-1, j)][(i, j)] = 1
            if i < H-1 and S[i+1][j] != c:
                g[(i, j)][(i+1, j)] = 1
                g[(i+1, j)][(i, j)] = 1
            if j > 0 and S[i][j-1] != c:
                g[(i, j)][(i, j-1)] = 1
                g[(i, j-1)][(i, j)] = 1
            if j < W-1 and S[i][j+1] != c:
                g[(i, j)][(i, j+1)] = 1
                g[(i, j+1)][(i, j)] = 1
    
    done = set([])
    ans = 0
    ac = {}
    for k in g:
        
        i, j = k
        if S[i][j] != '
            continue
        
        if k in ac:
            ans += ac[k]
            continue
        s = [k]
        done = set([k])
        w = set([])
        count = 0
        while s:
            
            k = s.pop()
            for n in g[k]:
                if n not in done:
                    s.append(n)
                    done.add(n)
            i, j = k
            if S[i][j] == '.':
                count += 1
            else:
                w.add(k)
        for l in w:
            ac[l] = count
        ans += count
        

    return ans


def main():
    H, W = read_int_n()
    S = []
    for _ in range(H):
        S.append(read_str())
    
    
    
    
    
    
    
    

    print(slv(H, W, S))


if __name__ == '__main__':
    main()

Solution (Python):

from itertools import product
import sys

sys.setrecursionlimit(200000)

H, W = map(int, input().split())
S = [input() for _ in range(H)]
color = [[None] * W for _ in range(H)]
memo = [[0, 0] for _ in range(H * W + 1)]
cnt = 1


def dfs(p, c):
    x, y = p
    color[x][y] = c
    memo[cnt][c] += 1
    for dx, dy in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and color[nx][ny] is None and c != (S[nx][ny] == '
            dfs([nx, ny], not c)


for i, j in product(range(H), range(W)):
    if color[i][j] is None:
        dfs([i, j], S[i][j] == '
        cnt += 1

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