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, 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, 1)])
		while q:
			
			y, x, color = q.popleft()
			for i in range(4):
				ny = y + dy[i]
				nx = x + dx[i]
				if 0 <= ny < H and 0 <= nx < W:
					if color == 1 and S[ny][nx] == "." and check[ny][nx] == 0:
						check[ny][nx] = 1
						
						cnt_white += 1
						q.append((ny, nx, 0))
					if color == 0 and S[ny][nx] == "
						check[ny][nx] = 1
						cnt_black += 1
						q.append((ny, nx, 1))
		ans += cnt_white*cnt_black
print(ans)

Solution (Python):



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

INF = -1
Gmap = [list(input()) for _ in range(H)]
Seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
init_q =[]

from collections import deque

def bfs(sth, stw):
    black = 1
    white = 0
    next_q = deque([])
    next_q.append((sth, stw))
    while len(next_q)!=0:
        
        h, w = next_q.popleft()
        Seen[h][w] = 0
        for d in direc:
            hs, ws = h + d[0], w + d[1]
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[h][w]=='
                Seen[hs][ws]=0
                next_q.append((hs, ws))
                white +=1
            if Gmap[h][w]=='.' and Gmap[hs][ws]=='
                Seen[hs][ws]=0
                next_q.append((hs, ws))
                black +=1

    return black * white


ret = 0
for sth in range(H):
    for stw in range(W):
        if Gmap[sth][stw]=='
            x = bfs(sth, stw)

            ret += x
print(ret)

Solution (Python):



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

INF = -1
Gmap = [list(input()) for _ in range(H)]
Seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
init_q =[]

from collections import deque

def bfs(sth, stw):
    black = 1
    white = 0
    next_q = deque([])
    next_q.append((sth, stw))
    while len(next_q)!=0:
        
        h, w = next_q.popleft()
        Seen[h][w] = 0
        for d in direc:
            hs, ws = h + d[0], w + d[1]
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[h][w]=='
                Seen[hs][ws]=0
                next_q.append((hs, ws))
                white +=1
            if Gmap[h][w]=='.' and Gmap[hs][ws]=='
                Seen[hs][ws]=0
                next_q.append((hs, ws))
                black +=1

    return black * white

def main():
    
    ret = 0
    for sth in range(H):
        for stw in range(W):
            if Gmap[sth][stw]=='
                x = bfs(sth, stw)

                ret += x
    print(ret)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque


def bfs(S):  
    que = deque([S])
    b, w = 0, 0
    while len(que) > 0:
        p, q = que.popleft()
        b += int(s[p][q] == '
        w += int(s[p][q] == '.')
        for i, j in near[p][q]:  
            if (i, j) in frag:  
                continue
            que.append((i, j)), frag.add((i, j))
    return b * w


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

near = [[set() for j in range(w)] for i in range(h)]
for i, si in enumerate(s):
    for j, sij in enumerate(si):
        for p, q in [(i - 1, j), (i, j - 1), (i + 1, j), (i, j + 1)]:
            if 0 <= p < h and 0 <= q < w and s[p][q] != sij:
                near[i][j].add((p, q))

ans, frag = 0,set()
for i in range(h):
    for j in range(w):
        if (i, j) not in frag:
            frag.add((i, j))
            ans += bfs((i, j))
print(ans)

Solution (Python):
from collections import deque


def bfs(S):  
    que = deque([S])
    b, w = 0, 0
    while len(que) > 0:
        p, q = que.popleft()
        b += int(s[p][q] == '
        w += int(s[p][q] == '.')
        for i, j in near[p][q]:  
            if (i, j) in frag:  
                continue
            if s[i][j] != s[p][q]:
                que.append((i, j)), frag.add((i, j))
    return b * w


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

near = [[set() for j in range(w)] for i in range(h)]
for i, si in enumerate(s):
    for j, sij in enumerate(si):
        for p, q in [(i - 1, j), (i, j - 1), (i + 1, j), (i, j + 1)]:
            if 0 <= p < h and 0 <= q < w and s[p][q] != sij:
                near[i][j].add((p, q))

ans, frag = 0,set()
for i in range(h):
    for j in range(w):
        if (i, j) not in frag:
            frag.add((i, j))
            ans += bfs((i, j))
print(ans)

Solution (Python):

import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]

H, W = read_values()
P = [[False for _ in range(W)] for _ in range(H)]
F = [input().strip() for i in range(H)]

def f(h, w):
    S = deque()
    S.append((h, w))
    P[h][w] = True
    T = [0, 1]
    while S:
        h, w = S.popleft()
        for hh, ww in [(h + 1, w), (h - 1, w), (h, w + 1), (h, w - 1)]:
            if not (0 <= hh < H and 0 <= ww < W):
                continue
            if P[hh][ww]:
                continue
            if F[hh][ww] == F[h][w]:
                continue
            P[hh][ww] = True
            t = 0 if F[hh][ww] == "." else 1
            T[t] += 1
            S.append((hh, ww))
    return T[0] * T[1]


def main():
    res = 0
    for h in range(H):
        for w in range(W):
            if P[h][w] or F[h][w] != "
                continue
            res += f(h, w)
    print(res)
    

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

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

mp = [[0]*W for _ in range(H)]
dxy = [[-1,0],[1,0],[0,-1],[0,1]]
lst = []

q = deque([])
num = 1
for i in range(H):
  for j in range(W):
    if mp[i][j] == 0:
      q.append((i,j))
      mp[i][j] = num
      dic = {'
      while q:
        t = q.popleft()
        dic[Ss[t[0]][t[1]]] += 1
        for k in range(4):
          if t[0] + dxy[k][0] >= 0 and t[0] + dxy[k][0] < H \
             and t[1] + dxy[k][1] >= 0 and t[1] + dxy[k][1] < W \
             and Ss[t[0]][t[1]] != Ss[t[0]+dxy[k][0]][t[1]+dxy[k][1]]\
             and mp[t[0]+dxy[k][0]][t[1]+dxy[k][1]] == 0:
            
            mp[t[0]+dxy[k][0]][t[1]+dxy[k][1]] = num
            q.append((t[0]+dxy[k][0],t[1]+dxy[k][1]))
      lst.append(dic)
      num += 1

rlt = 0
for d in lst:
  rlt += d['

print(rlt)

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


for i in range(H):
    for j in range(W-1):
        if S[i][j] != S[i][j+1]:
            edge.append((i*W+j,i*W+j+1))

for i in range(H-1):
    for j in range(W):
        if S[i][j] != S[i+1][j]:
            edge.append((i*W+j, (i+1)*W+j))

class UnionFind():
    '''
    UnionFindでグラフの状態を管理する
    '''
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def is_root(self, x):
        return self.root[x] < 0

    def find_root(self, x):
        '''
        ルートのノードを見つける
        '''
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]

    def unite(self, x, y):
        '''
        ノード同士を連結する
        '''
        x = self.find_root(x)
        y = self.find_root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    def is_same_group(self, x, y):
        '''
        同一のルーツを持つかどうか調査する
        '''
        return self.find_root(x) == self.find_root(y)

    def count(self, x):
        return -self.root[self.find_root(x)]

union = UnionFind(H*W)
for l, r in edge:
    union.unite(l, r)
cnt = [0] * (H*W)
for i in range(H*W):
    c = union.find_root(i)
    if S[i//W][i%W] == "
        cnt[c] += 1

ans = 0
for i in range(H*W):
    if union.is_root(i):
        r = union.find_root(i)
        c = union.count(i)
        ans += cnt[r] * (c-cnt[r])
print(ans)

Solution (Python):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from collections import deque
    input = sys.stdin.readline

    H, W = map(int, input().split())
    grid = []
    for _ in range(H):
        grid.append(input().rstrip('\n'))

    ans = 0
    seen = [[0] * W for _ in range(H)]
    d = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    for h0 in range(H):
        for w0 in range(W):
            if seen[h0][w0] == 0:
                que = deque([(h0, w0)])
                seen[h0][w0] = 1
                black = white = 0
                while que:
                    h, w = que.popleft()
                    if grid[h][w] == "
                        black += 1
                    else:
                        white += 1
                    for dh, dw in d:
                        h_new, w_new = h+dh, w+dw
                        if 0 <= h_new < H and 0 <= w_new < W:
                            if seen[h_new][w_new] == 0:
                                if grid[h][w] != grid[h_new][w_new]:
                                    que.append((h_new, w_new))
                                    seen[h_new][w_new] = 1
                ans += black * white
    print(ans)


if __name__ == '__main__':
    main()

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

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

move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
seen = [[0] * W for _ in range(H)]




def dfs(sy, sx):
    seen[sy][sx] = 1
    b, w = 1, 0
    
    for dy, dx in move:
      ny = sy + dy
      nx = sx + dx
      if 0 <= ny < H and 0 <= nx < W and F[ny][nx] != F[sy][sx] and not seen[ny][nx]:
        p = dfs(ny, nx)
        b += p[1]  
        w += p[0]  
    return (b, w)
        
count = 0
for i in range(H):
    for j in range(W):
        if not seen[i][j]:
            b, w = dfs(i, j)
            count += b * w

print(count)

Solution (Python):
import sys
from collections import deque

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def bfs_grid(H, W, grid):

    d = [[False for _ in range(W)] for _ in range(H)]
    move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    ans = 0

    for sy in range(H):
        for sx in range(W):
            if d[sy][sx]:
                continue

            q = deque()
            q.append((sx, sy))
            d[sy][sx] = True
            black = 0
            white = 0
            while q:
                x, y = q.popleft()
                now_color = grid[y][x]
                if now_color:
                    white += 1
                else:
                    black += 1
                for m in move:
                    nx, ny = x + m[0], y + m[1]
                    if 0 <= nx < W and 0 <= ny < H:
                        if not d[ny][nx] and grid[ny][nx] != now_color:
                            d[ny][nx] = True
                            q.append((nx, ny))

            ans += black * white

    return ans


def main():
    H, W = in_nn()
    grid = in_map2(H)

    print(bfs_grid(H, W, grid))


if __name__ == '__main__':
    main()

Solution (Python):

h, w = map(int, input().split())
s = [input() for i in range(h)]
mx=[1, -1, 0, 0]
my=[0, 0, 1, -1]
vis=[[0]*w for i in range(h)]
import queue
q=queue.Queue()
ans=0
for i in range(h):
  for j in range(w):
    if vis[i][j]==0:
      white=0
      black=0
      q.put([i, j])
      vis[i][j]=1
      while not q.empty():
        y, x = q.get()
        if s[y][x]==".":
          white+=1
        else:
          black+=1
        
        for k in range(4):
          nx=x+mx[k]
          ny=y+my[k]
          if 0<=nx<=w-1 and 0<=ny<=h-1 and vis[ny][nx]==0:
            if s[y][x] != s[ny][nx]:
              q.put([ny, nx])
              vis[ny][nx]=1
      if white+black!=1:
        ans+=white*black
print(ans)

Solution (Python):
from collections import deque

H, W = map(int, input().split())
seen = [[False]*W for _ in range(H)]
dx,dy = [1, 0, -1, 0], [0, 1, 0, -1]
c,S = 0,[]
for _ in range(H):
	S.append(input())

for i in range(H):
	for j in range(W):
		if (S[i][j]=='
			d = deque()
			d.append((i, j))
			seen[i][j],b,w = True,1,0
			while d:
				px,py = d.popleft()
				for x,y in zip(dx,dy):
					nx, ny = px+x, py+y
					if nx < 0 or ny < 0 or nx >= H or ny >= W or seen[nx][ny]:
						continue
					if (S[px][py]=='
						d.append((nx, ny))
						seen[nx][ny] = 1
						if S[px][py] == '
							w += 1
						else:
							b += 1
			c += b*w

print(c)

Solution (Python):
from collections import deque

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

H, W = map(int, input().split())
seen = [[False]*W for _ in range(H)]
c,S = 0,[]
for _ in range(H):
	S.append(input())

for i in range(H):
	for j in range(W):
		if (S[i][j]=='
			d = deque()
			d.append((i, j))
			seen[i][j],b,w = True,1,0
			while d:
				px,py = d.popleft()
				for x,y in zip(dx,dy):
					nx, ny = px+x, py+y
					if nx < 0 or ny < 0 or nx >= H or ny >= W or seen[nx][ny]:
						continue
					if S[px][py]=='
						d.append((nx, ny))
						seen[nx][ny] = 1
						w += 1
					elif S[px][py]=='.' and S[nx][ny] == '
						d.append((nx, ny))
						seen[nx][ny] = 1
						b += 1
			c += b*w

print(c)

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



n = h*w

par = [0] * n
rank = [0] * n


for i in range(n):
    par[i] = i
    rank[i] = 0


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

def unite(x , y):
    rx = find(x)
    ry = find(y)
    
    if rx == ry:
        return
    
    if rank[rx] < rank[ry]:
        par[rx] = ry
    elif rank[rx] > rank[ry]:
        par[ry] = rx
    else:
        par[ry] = x
        rank[rx] += 1

for i in range(h):
    for j in range(w-1):
        if s[i][j] != s[i][j+1]:
            unite(i*w+j , i*w +j+1)
            
for i in range(h-1):
    for j in range(w):
        if s[i][j] != s[i+1][j]:
            unite(i*w+j , (i+1)*w +j)
            
uni = [[0]*2 for _ in range(n)]

for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            k = 0
        else:
            k = 1
        uni[find(i*w+j)][k] += 1
        
ans = 0
for i in uni:
    ans += i[0] * i[1]
    
print(ans)

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

ans=0
dif=[(-1,0),(1,0),(0,-1),(0,1)]

def solve(i,j):
    global ans 
    ans=ans
    black=0
    white=0
    if visited[i][j]==False:
        if lists[i][j]=="
            black+=1
        else:
            white+=1
        visited[i][j]=True
        
    d=deque()
    e=deque()
    d.append((i,j))
    while d:
        while d:
            p=d.popleft()
            x,y=p
            color=lists[x][y]
            for que in dif:
                dx,dy=que
                if 0<=dx+x<h and 0<=dy+y<w:
                    if visited[dx+x][dy+y]==False and lists[dx+x][dy+y]!=color:
                        visited[dx+x][dy+y]=True
                        e.append((dx+x,dy+y))
                        if color=="
                            white+=1
                        else:
                            black+=1
        if e:
            d=e
            e=deque()
    ans+=(white)*(black)
flag=True
while flag:
    sub=False
    for i in range(h):
        for j in range(w):
            if visited[i][j]==False:
                solve(i,j)
                sub=True
    if sub==False:
        flag=False
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15
Dy = (-1,0,1,0)
Dx = (0,1,0,-1)
def main():
    H,W = map(int,input().split())
    grid = [input() for _ in range(H)]
    grid = [[1 if g == '
    G = [[] for _ in range(H*W)]

    for i in range(H):
        for j in range(W):
            for dy,dx in zip(Dy,Dx):
                y = i + dy
                x = j + dx
                if y < 0 or y >= H or x < 0 or x >= W:
                    continue
                if grid[i][j]^grid[y][x] == 1:
                    G[i*W + j].append(y*W + x)
                    G[y*W + x].append(i*W + j)
    
    visited = [-1] * (H*W)
    ans = 0
    for i in range(W*H):
        if visited[i] >= 0:
            continue
        stack = [i]
        visited[i] = 0
        w = 1
        b = 0
        while stack:
            v = stack.pop()
            for e in G[v]:
                if visited[e] >= 0:
                    continue
                visited[e] = visited[v]^1
                if visited[e] == 1:
                    b += 1
                else:
                    w += 1
                stack.append(e)
        ans += b*w
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
H, W = map(int, input().split())
S = [input() for _ in range(H)]
seen = [[0]*W for _ in range(H)]


def rec(h,w,seen):
	if S[h][w] == '.':
		res = [1, 0]
	else:
		res = [0, 1]
	dh = [-1, 1, 0, 0]
	dw = [0, 0, -1, 1] 
	seen[h][w] = 1
	for i in range(4):
		nh = h+dh[i]
		nw = w+dw[i]
		if 0 <= nh <= H-1 and 0 <= nw <= W-1:
			if seen[nh][nw] == 0 and S[nh][nw] != S[h][w]:
				r0, r1 = rec(nh, nw, seen)
				res[0] += r0
				res[1] += r1
					
	return res

ans = 0
for h in range(H):
	for w in range(W):
		if seen[h][w] != 1:
			t0, t1 = rec(h, w, seen)
			ans += t0 * t1
print(ans)

Solution (Python):
from collections import deque
H,W=map(int,input().split())
S=[]
for _ in range(H):
    s=input()
    S.append(s)
m=[[0]*W for _ in range(H)]
def DFS(y,x,S):

    d=deque([])
    d.append((y,x,0))
    white=0
    black=0
    while d:
        p,q,n=d.popleft()
        if m[p][q]==1:
            continue
        else:
            if n%2==0 and S[p][q]=='
                black+=1
                m[p][q]=1
                if 0<=p+1<=H-1 and S[p+1][q]=='.':
                    d.append((p+1,q,n+1))
                if 0<=p-1<=H-1 and S[p-1][q]=='.':
                    d.append((p-1,q,n+1))
                if 0<=q+1<=W-1 and S[p][q+1]=='.':
                    d.append((p,q+1,n+1))
                if 0<=q-1<=W-1 and S[p][q-1]=='.':
                    d.append((p,q-1,n+1))
            
            elif n%2==1 and S[p][q]=='.':
                white+=1
                
                m[p][q]=1
                if 0<=p+1<=H-1 and S[p+1][q]=='
                    d.append((p+1,q,n+1))
                if 0<=p-1<=H-1 and S[p-1][q]=='
                    d.append((p-1,q,n+1))
                if 0<=q+1<=W-1 and S[p][q+1]=='
                    d.append((p,q+1,n+1))
                if 0<=q-1<=W-1 and S[p][q-1]=='
                    d.append((p,q-1,n+1))
    return white,black

total=0
for i in range(H):
    for j in range(W):
        if S[i][j]=='.':
            continue
        elif m[i][j]==1:
            continue
        else:
            w,b=DFS(i,j,S)
            total+=w*b

print(total)

Solution (Python):
from collections import deque


def BFS():
    color=[["white" for _ in range(w)] for _ in range(h)]
    queue=deque([])
    ans=0

    for i in range(h):
        for j in range(w):
            if color[i][j]=="white" and S[i][j]=="
                queue.append([i,j])
                color[i][j]="gray"
                black,white=0,0

                while len(queue)>0:
                    c,d=queue.popleft()
                    if S[c][d]=="
                    else:white +=1

                    sign="." if S[c][d]=="
                    for a,b in [[1,0],[-1,0],[0,1],[0,-1]]:
                        X,Y=c+a,d+b
                        if 0<=X<h and 0<=Y<w:
                            if S[X][Y]==sign and color[X][Y]=="white":
                                color[X][Y]="gray"
                                queue.append([X,Y])
                    color[c][d]="black"
                ans +=black*white

    return ans


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

Solution (Python):
def main():
    from collections import deque
    import sys
    input = sys.stdin.readline
    H, W = (int(i) for i in input().split())
    c = [[s for s in input()] for i in range(H)]
    dist = [[-1]*W for i in range(H)]

    def bfs(c, sy, sx, H, W):
        que = deque()

        dist[sy][sx] = 0
        que.append((sy, sx))
        d = ((1, 0), (0, 1), (-1, 0), (0, -1))
        flag = False  
        bla = 0
        whi = 0
        while que:
            uh, uw = que.popleft()
            if c[uh][uw] == "
                flag = True
                bla += 1
            else:
                flag = False
                whi += 1
            for dy, dx in d:
                next_h = uh + dy
                next_w = uw + dx
                if not(0 <= next_h < H and 0 <= next_w < W):
                    continue
                if dist[next_h][next_w] != -1:
                    continue
                if flag and c[next_h][next_w] == '
                    continue
                if not flag and c[next_h][next_w] == ".":
                    continue
                dist[next_h][next_w] = dist[uh][uw] + 1
                que.append((next_h, next_w))
        return bla * whi

    ans = 0
    for h in range(H):
        for w in range(W):
            if dist[h][w] != -1:
                continue
            if c[h][w] == "
                ans += bfs(c, h, w, H, W)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque, defaultdict


from collections import Counter

from itertools import accumulate,combinations,permutations,product

from heapq import heapify,heappop,heappush


from functools import reduce,lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
class unionfind:
    def __init__(self, elements=None):
        if elements is None:
            elements = ()
        self.parents = {}
        self.weights = {}
        for x in elements:
            self.weights[x] = 1
            self.parents[x] = x

    def __getitem__(self, i):
        
        if i not in self.parents:
            self.parents[i] = i
            self.weights[i] = 1
            return i
        path = [i]
        root = self.parents[i]
        while root != path[-1]:
            path.append(root)
            root = self.parents[root]
        for ancestor in path:
            self.parents[ancestor] = root
        return root

    def __iter__(self):
        return iter(self.parents)

    def union(self, *objects):
        roots = [self[x] for x in objects]
        heaviest = max(roots, key=lambda r: self.weights[r])
        for r in roots:
            if r != heaviest:
                self.weights[heaviest] += self.weights[r]
                self.parents[r] = heaviest

    def __len__(self):
        return len(self.parents)

def main():
    mod = 1000000007
    

    
    H,W = map(int, input().split())
    
    
    S = tuple(input() for i in range(H)) 
    uf=unionfind()
    for i in range(H):
        for j in range(W):
            x=i*W+j
            if i>0:
                if S[i][j]!=S[i-1][j]:
                    uf.union(x,(i-1)*W+j)
            if j>0:
                if S[i][j]!=S[i][j-1]:
                    uf.union(x,i*W+j-1)
    c=Counter()
    ps=set()
    for i in range(H*W):
        p=uf[i]
        ps.add(uf[i])
        if S[i//W][i%W]=="
            c[p*2]+=1
        else:
            c[p*2+1]+=1
        
    ans=0
    for p in ps:
        ans+=c[p*2]*c[p*2+1]
    print(ans)





if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict

H, W = map(int, input().split())
field = [[c == '
counted = [[False] * W for _ in range(H)]
detected = [[False] * W for _ in range(H)]

b_count = defaultdict(int)
w_count = defaultdict(int)
another_group = [(0, 0)]
group = 0
while another_group:
    i, j = another_group.pop()
    detected[i][j] = True
    if counted[i][j]:
        continue
    
    stack = [(i, j)]
    while stack:
        i, j = stack.pop()
        if field[i][j]:
            b_count[group] += 1
        else:
            w_count[group] += 1
        
        counted[i][j] = True
        for di, dj in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            if 0 <= i+di < H and 0 <= j+dj < W:
                if not detected[i+di][j+dj]:
                    if field[i+di][j+dj] == field[i][j]:
                        another_group.append((i+di, j+dj))
                    else:
                        detected[i+di][j+dj] = True
                        stack.append((i+di, j+dj))
                
    group += 1         

ans = 0
for bk, bv in b_count.items():
    ans += bv * w_count[bk]

print(ans)

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

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

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

group_w = [0]*(H*W)
group_k = [0]*(H*W)

def dfs(x,y,state):
    if S[x][y]=='.':
        group_w[idx] += 1
    else:
        group_k[idx] += 1
    visited[x][y] = True
    
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if nx<0 or nx>=H or ny<0 or ny>=W:
            continue
        if visited[nx][ny]:
            continue
        if state==0 and S[nx][ny]=='
            dfs(nx,ny,1)
        elif state==1 and S[nx][ny]=='.':
            dfs(nx,ny,0)
    return 


ans = 0
idx = 0
for i in range(H):
    for j in range(W):
        if not visited[i][j]:
            dfs(i,j,S[i][j]=='
            a = group_w[idx]
            b = group_k[idx]
            ans += a*b
            idx += 1
       
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline


def DFS(add,next,cnt):
    x,y=add
    for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
        X,Y=x+i,y+j
        if 0<=X<h and 0<=Y<w:
            if S[X][Y]==next and color[X][Y]=="white":
                color[X][Y]=str(cnt)
                DFS([X,Y],"." if next=="


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

color=[["white" for _ in range(w)] for _ in range(h)]
for i in range(h):
    for j in range(w):
        if S[i][j]=="
            cnt +=1
            DFS([i,j],".",cnt)

dictionary={str(i+1):[0,0] for i in range(cnt)}
for i in range(h):
    for j in range(w):
        if color[i][j]!="white":
            if S[i][j]==".":dictionary[color[i][j]][0] +=1
            else:dictionary[color[i][j]][1] +=1

ans=0
for v,m in dictionary.values():
    ans +=v*m
print(ans)

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

h,w=list(map(int,input().split()))
s=[[1 if c=='
g=[[] for _ in range(h*w)]

for i in range(w):
    for j in range(h):
        for di in [-1,0,1]:
            for dj in [-1,0,1]:
                if abs(di)+abs(dj)!=1:
                    continue
                if 0<=i+di<w and 0<=j+dj<h:
                    if s[j][i]!=s[j+dj][i+di]:
                        g[j*w+i].append(i+di+(j+dj)*w)

visit=[0]*(h*w)
black=[0]*(h*w)
white=[0]*(h*w)

def rec(j,i,rj,ri):
    if s[j][i]:
        black[rj*w+ri]+=1
    else:
        white[rj*w+ri]+=1
    
    for n in g[j*w+i]:
        if visit[n]:
            continue

        visit[n]=1

        rec(n//w,n%w,rj,ri)

ans=0

for i in range(w):
    for j in range(h):
        if visit[w*j+i]:
            continue
        visit[w*j+i]=1

        rec(j,i,j,i)
        
        ans+=black[w*j+i]*white[w*j+i]

print(ans)