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 deque

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


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


V=[ [ 0 for i in range(W) ] for j in range(H) ]


def dfs(x,y,current):
	bc=0	
	wc=0	
	q = deque([]) 
	V[x][y]=1
	q.append( (x,y,current) )

	while q:
		x,y,current=q.popleft()

		if current == "
		else:  wc+=1

		for dx,dy in D:
			if 0<=x+dx<H and 0<=y+dy<W:
				next=S[x+dx][y+dy] 
				if V[x+dx][y+dy]==0 and current !=next:
						V[x+dx][y+dy]=1
						q.append( (x+dx, y+dy,next) )

	return bc*wc




ans=0
for x in range(H):
	for y in range(W):
		if S[x][y]=="
			ans+=dfs(x,y, "

print ans

Solution (Python):
class DisjointSet:
    def __init__(self):
        self.rank = {}
        self.p = {}

    def makeSet(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def same(self, x, y):
        return self.findSet(x) == self.findSet(y)

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x, y):
        if(self.rank[x] > self.rank[y]):
            self.p[y] = x
        else:
            self.p[x] = y
            if(self.rank[x] == self.rank[y]):
                self.rank[y] += 1

    def findSet(self, x):
        if(x != self.p[x]):
            self.p[x] = self.findSet(self.p[x])
        return self.p[x]

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

ds = DisjointSet()
for i in range(H):
    for j in range(W):
        ds.makeSet((i,j))

for i in range(H):
    for j in range(W):
        if i + 1 < H and S[i][j] != S[i+1][j]:
            ds.unite((i,j), (i+1, j))
        if 0 <= i - 1 and S[i][j] != S[i-1][j]:
            ds.unite((i,j), (i-1, j))
        if j + 1 < W and S[i][j] != S[i][j+1]:
            ds.unite((i,j), (i, j+1))
        if 0 <= j - 1 and S[i][j] != S[i][j-1]:
            ds.unite((i,j), (i, j-1))

from collections import defaultdict

c1 = defaultdict(int)
c2 = defaultdict(int)

for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            c1[ds.findSet((i,j))] += 1
        else:
            c2[ds.findSet((i,j))] += 1
ans = 0
for i in c1.keys():
    ans += c1[i] * c2[i]
print(ans)

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

from collections import defaultdict

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

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

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def merge(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        elif self.rank[x] > self.rank[y]:
            self.parent[y] = x
        else:
            self.parent[x] = y
            self.rank[y] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

uf = UnionFind(h * w)
for i in range(h):
    for j in range(w):
        if j < w-1:
            if s[i][j] != s[i][j + 1]:
                uf.merge(i*w + j, i*w + j + 1)
        if i < h-1:
            if s[i][j] != s[i+1][j]:
                uf.merge(i*w + j, (i+1)*w + j)

d_w = defaultdict(int)
d_b = defaultdict(int)
for i in range(h):
    for j in range(w):
        parent = uf.find(i*w + j)
        if s[i][j] == ".":
            d_w[parent] += 1
        else:
            d_b[parent] += 1

ans = 0
for i in range(h):
    for j in range(w):
        ans += d_w[i*w + j] * d_b[i*w + j]

print(ans)

Solution (Python):
h, w = map(int, input().split())
s = [[''] * (w + 2)]
s += [[''] + list(input()) + [''] for _ in range(h)]
s += [[''] * (w + 2)]
m = [[1] * (w + 2)]
m += [[1] + [0] * w + [1] for _ in range(h)]
m += [[1] * (w + 2) for _ in range(h + 2)]
ans = 0
for i in range(1, h + 1):
    for j in range(1, w + 1):
        if m[i][j] == 1:
            continue
        m[i][j] = 1
        qs = [[i, j]]
        white = 0
        black = 0
        while len(qs) != 0:
            q = qs.pop(0)
            if s[q[0]][q[1]] == '.':
                white += 1
            else:
                black += 1
            m[q[0]][q[1]] = 1
            for k in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                if m[q[0] + k[0]][q[1] + k[1]] == 0 and s[q[0]][q[1]] != s[q[0] + k[0]][q[1] + k[1]]:
                    m[q[0] + k[0]][q[1] + k[1]] = 1
                    qs.append([q[0] + k[0], q[1] + k[1]])
        ans += black * white
print(ans)

Solution (Python):
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
m = [[0] * w for _ in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if m[i][j] == 1:
            continue
        m[i][j] = 1
        qs = [[i, j]]
        white = 0
        black = 0
        while len(qs) != 0:
            q = qs.pop(0)
            if s[q[0]][q[1]] == '.':
                white += 1
            else:
                black += 1
            m[q[0]][q[1]] = 1
            for k in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                if not (0 <= q[0] + k[0] <= h - 1) or not (0 <= q[1] + k[1] <= w - 1):
                    continue
                if m[q[0] + k[0]][q[1] + k[1]] == 0 and s[q[0]][q[1]] != s[q[0] + k[0]][q[1] + k[1]]:
                    m[q[0] + k[0]][q[1] + k[1]] = 1
                    qs.append([q[0] + k[0], q[1] + k[1]])
        ans += black * white
print(ans)

Solution (Python):
def main():
    from collections import defaultdict
    import sys
    sys.setrecursionlimit(10 ** 9)
    
    H, W = list(map(int, raw_input().split()))
    G = [list(raw_input()) for i in range(H)]
    
    Visited = [[0] * W for i in range(H)]
    direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    
    
    def dfs(ny, nx, color):
        for dy, dx in direction:
            if not ((0 <= ny + dy < H) and (0 <= nx + dx < W)):
                continue
    
            if G[ny + dy][nx + dx] == G[ny][nx]:
                continue
    
            if Visited[ny + dy][nx + dx] != 0:
                continue
    
            if G[ny + dy][nx + dx] == '
                Visited[ny + dy][nx + dx] = color
            else:
                Visited[ny + dy][nx + dx] = -color
    
            dfs(ny + dy, nx + dx, color)
    
    
    Color = 1
    for y in range(H):
        for x in range(W):
            if Visited[y][x] == 0:
                if G[y][x] == '
                    Visited[y][x] = Color
                else:
                    Visited[y][x] = -Color
                dfs(y, x, Color)
                Color += 1
    
    D = defaultdict(int)
    for i in range(1, Color + 1):
        D[i] = 0
        D[-i] = 0
    
    for row in Visited:
        for data in row:
            D[data] += 1
    
    ans = 0
    for key in D.keys():
        ans += D[key] * D[-key]
    
    print(ans // 2)
    
main()

Solution (Python):
def main():
    from collections import defaultdict
    import sys
    sys.setrecursionlimit(10 ** 9)
    
    H, W = list(map(int, input().split()))
    G = [list(input()) for i in range(H)]
    
    Visited = [[0] * W for i in range(H)]
    direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    
    
    def dfs(ny, nx, color):
        for dy, dx in direction:
            if not ((0 <= ny + dy < H) and (0 <= nx + dx < W)):
                continue
    
            if G[ny + dy][nx + dx] == G[ny][nx]:
                continue
    
            if Visited[ny + dy][nx + dx] != 0:
                continue
    
            if G[ny + dy][nx + dx] == '
                Visited[ny + dy][nx + dx] = color
            else:
                Visited[ny + dy][nx + dx] = -color
    
            dfs(ny + dy, nx + dx, color)
    
    
    Color = 1
    for y in range(H):
        for x in range(W):
            if Visited[y][x] == 0:
                if G[y][x] == '
                    Visited[y][x] = Color
                else:
                    Visited[y][x] = -Color
                dfs(y, x, Color)
                Color += 1
    
    D = defaultdict(int)
    for i in range(1, Color + 1):
        D[i] = 0
        D[-i] = 0
    
    for row in Visited:
        for data in row:
            D[data] += 1
    
    ans = 0
    for key in D.keys():
        ans += D[key] * D[-key]
    
    print(ans // 2)
    
main()

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


h, w = map(int, input().split())
s_array = ["+" * (w + 2)]
for i in range(h):
    s_array.append("+" + input() + "+")
else:
    s_array.append("+" * (w + 2))
moving = [[0, 1], [0, -1], [1, 0], [-1, 0]]
visit = [[False for x in range(w+2)] for x in range(h+2)]


def recursive(mark_point, mark_sharp, row, point):
    
    if visit[row][point]:
        return mark_point, mark_sharp
    else:
        visit[row][point] = True

    for x, y in moving:
        
        if s_array[row + x][point + y] != "+" and s_array[row + x][point + y] != s_array[row][point]:
            if visit[row+x][point+y]:
                continue
            
            if s_array[row + x][point + y] == "
                mark_sharp += 1
            else:
                mark_point += 1
            mark_point, mark_sharp = recursive(mark_point, mark_sharp, row + x, point + y)
    else:
        return mark_point, mark_sharp


res = 0
for row in range(1, h + 1):
    for point in range(1, w + 1):
        m, n = recursive(s_array[row][point].count("."), s_array[row][point].count("
        res += m*n
print(res)

Solution (Python):
from collections import deque

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

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


def bfs(i, j):
    
    
    if visited[i][j]:
        return 0
    else:
        cnt1, cnt2 = 0, 0
        que = deque([(i, j)])
        while que:
            
            i, j = que.popleft()
            
            if S[i][j] == '
                cnt1 += 1
            else:
                cnt2 += 1
            visited[i][j] = True
            
            

            
            for (dh, dw) in move:
                if ((-1 < (i + dh) < H) and (-1 < (j + dw) < W)):
                    
                    if not visited[i + dh][j + dw]:
                        if S[i][j] != S[i + dh][j + dw]:
                            visited[i + dh][j + dw] = True
                            que.append((i + dh, j + dw))

        return cnt1 * cnt2


ans = 0
for i in range(H):
    for j in range(W):
        ans += bfs(i, j)
        


print(ans)

Solution (Python):
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 9)
 
H, W = list(map(int, input().split()))
G = [list(input()) for i in range(H)]
 
Visited = [[0] * W for i in range(H)]
direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]
 
 
def dfs(ny, nx, color):
    for dy, dx in direction:
        if not ((0 <= ny + dy < H) and (0 <= nx + dx < W)):
            continue
 
        if G[ny + dy][nx + dx] == G[ny][nx]:
            continue
 
        if Visited[ny + dy][nx + dx] != 0:
            continue
 
        if G[ny + dy][nx + dx] == '
            Visited[ny + dy][nx + dx] = color
        else:
            Visited[ny + dy][nx + dx] = -color
 
        dfs(ny + dy, nx + dx, color)
 
 
Color = 1
for y in range(H):
    for x in range(W):
        if Visited[y][x] == 0:
            if G[y][x] == '
                Visited[y][x] = Color
            else:
                Visited[y][x] = -Color
            dfs(y, x, Color)
            Color += 1
 
 
D = defaultdict(int)
for row in Visited:
    for data in row:
        D[data] += 1
 
ans = 0
for key in D.keys():
    if -key in D.keys():
        ans += D[key] * D[-key]
 
print(ans // 2)

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

sys.setrecursionlimit(10**9)

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

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

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

def dfs(i, j, color):
    if not (0 <= i <= h-1 and 0 <= j <= w-1):
        return 0, 0
    if memo[i][j] == 1:
        return 0, 0
    if s[i][j] == color:
        return 0, 0
    memo[i][j] = 1
    white, black = 0, 0
    if s[i][j] == ".":
        white += 1
    else:
        black += 1
    for dx, dy in dir:
        cur_w, cur_b = dfs(i + dx, j + dy, s[i][j])
        white += cur_w
        black += cur_b
    return white, black

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            white, black = dfs(i, j, "
        else:
            white, black = dfs(i, j, ".")

        ans += white * black

print(ans)

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

sys.setrecursionlimit(10**9)

from collections import deque

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

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

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

def dfs(i, j, color):
    if not (0 <= i <= h-1 and 0 <= j <= w-1):
        return 0, 0
    if memo[i][j] == 1:
        return 0, 0
    if s[i][j] == color:
        return 0, 0
    memo[i][j] = 1
    white, black = 0, 0
    if s[i][j] == ".":
        white += 1
    else:
        black += 1
    for dx, dy in dir:
        cur_w, cur_b = dfs(i + dx, j + dy, s[i][j])
        white += cur_w
        black += cur_b
    return white, black

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            white, black = dfs(i, j, "
        else:
            white, black = dfs(i, j, ".")

        ans += white * black

print(ans)

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

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

board=[]
check=[[None]*W for i in range(H)]
answer=0

for i in range(H):
  S=list(input())
  board.append(S)
  
def dfs(i,j,color):
  if not (0<=i<H and 0<=j<W):
    return 0,0
  if board[i][j]==color:
    return 0,0
  if check[i][j]:
    return 0,0
  
  check[i][j]=True
  black,white=0,0
  
  if board[i][j]=='
  	black+=1
  else:
    white+=1
 
  tempblack,tempwhite=dfs(i+1,j,board[i][j])
  black+=tempblack
  white+=tempwhite
  
  tempblack,tempwhite=dfs(i-1,j,board[i][j])
  black+=tempblack
  white+=tempwhite
  
  tempblack,tempwhite=dfs(i,j+1,board[i][j])
  black+=tempblack
  white+=tempwhite

  tempblack,tempwhite=dfs(i,j-1,board[i][j])
  black+=tempblack
  white+=tempwhite
  return black,white

for i in range(H):
  for j in range(W):
    black,white=dfs(i,j,"!")
    answer+=black*white
print(answer)

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

from collections import deque

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

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

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

ans = 0
for i in range(h):
    for j in range(w):
        if memo[i][j] == 1:
            continue
        memo[i][j] = 1
        black = 0
        white = 0
        if s[i][j] == ".":
            white += 1
        else:
            black += 1
        q = deque([(i, j)])

        while q:
            x, y = q.popleft()
            for dx, dy in dir:
                if not ((0 <= x + dx <= h-1) and (0 <= y + dy <= w-1)):
                    continue
                if memo[x + dx][y + dy] == 0 and s[x][y] != s[x+dx][y+dy]:
                    memo[x + dx][y + dy] = 1
                    if s[x + dx][y + dy] == ".":
                        white += 1
                    else:
                        black += 1
                    q.append((x+dx, y+dy))

        ans += black * white

print(ans)

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

from collections import deque

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

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


ans = 0
for i in range(h):
    for j in range(w):
        if memo[i][j] == 1:
            continue
        memo[i][j] = 1
        black = 0
        white = 0
        if s[i][j] == ".":
            white += 1
        else:
            black += 1
        q = deque([(i, j)])

        while q:
            x, y = q.popleft()
            if x > 0:
                if memo[x - 1][y] == 0 and s[x - 1][y] != s[x][y]:
                    memo[x - 1][y] = 1
                    if s[x - 1][y] == ".":
                        white += 1
                    else:
                        black += 1
                    q.append((x - 1, y))
            if x < h - 1:
                if memo[x + 1][y] == 0 and s[x + 1][y] != s[x][y]:
                    memo[x + 1][y] = 1
                    if s[x + 1][y] == ".":
                        white += 1
                    else:
                        black += 1
                    q.append((x + 1, y))
            if y > 0:
                if memo[x][y - 1] == 0 and s[x][y - 1] != s[x][y]:
                    memo[x][y - 1] = 1
                    if s[x][y - 1] == ".":
                        white += 1
                    else:
                        black += 1
                    q.append((x, y - 1))
            if y < w - 1:
                if memo[x][y + 1] == 0 and s[x][y + 1] != s[x][y]:
                    memo[x][y + 1] = 1
                    if s[x][y + 1] == ".":
                        white += 1
                    else:
                        black += 1
                    q.append((x, y + 1))

        ans += black * white

print(ans)

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


par = [] 
rank = [] 


for i in range(h*w):
    
    par.append(i)
    rank.append(0)


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


def unite(x,y,par,rank):
    x = find(x,par)
    y = find(y,par)
    
    if x != y:
        
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x]==rank[y]:
                rank[x] += 1


def same(x,y,par):
    return find(x,par) == find(y,par)

for i in range(h*w):
    if i//w + 1 < h and s[i//w][i%w] != s[i//w+1][i%w]:
        unite(i,i+w,par,rank)
    if i%w +1 < w and s[i//w][i%w] != s[i//w][i%w+1]:
        unite(i,i+1,par,rank)

res = [[0,0] for i in range(w*h)] 
for i in range(h*w):
    r = find(i,par)
    if s[i//w][i%w] ==".":
        res[r][0]+=1
    else:
        res[r][1]+=1

ans = 0
for i in range(h*w):
    ans += res[i][0]*res[i][1]
print(ans)

Solution (Python):
from collections import deque
H,W = map(int, input().split())
s = [input() for _ in range(H)]
visited = [[False]*W for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        stk = deque([(i,j)]) 
        visited[i][j] = True
        black,white = 0,0
        while stk: 
            y,x = stk.popleft()
            
            from_ = s[y][x]
            if from_==".": white += 1
            else:          black += 1
            for dy,dx in ([1,0],[0,1],[-1,0],[0,-1]): 
                if not (0<=y+dy<H and 0<=x+dx<W):
                    continue
                to_   = s[y+dy][x+dx]
                if ((from_=="." and to_ == "
                 or (from_=="
                    if visited[y+dy][x+dx]: continue
                    stk.append([y+dy,x+dx])
                    visited[y+dy][x+dx] = True
        
        ans += black*white
print(ans)

Solution (Python):


import sys
sys.setrecursionlimit(1000000)

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


def dfs(i,j,color):

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

  
  tmp1,tmp2=dfs(i+1,j,s[i][j])
  wh,bl=wh+tmp1,bl+tmp2
 
  tmp1,tmp2=dfs(i-1,j,s[i][j])
  wh,bl=wh+tmp1,bl+tmp2
        
  tmp1,tmp2=dfs(i,j-1,s[i][j])
  wh,bl=wh+tmp1,bl+tmp2
 
  tmp1,tmp2=dfs(i,j+1,s[i][j])
  wh,bl=wh+tmp1,bl+tmp2
 
  return wh,bl
 
ans=0
for i in range(h):
  for j in range(w):
    a,b=dfs(i,j,"!")
    ans+=a*b
 
print(ans)

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

H, W = map(int, input().split())
S = []
for i in [0]*H:
    l = input()
    S.append([1 if x == "

bk = 0
wh = 0
def check(S, x, y):
    global bk, wh
    n = S[y][x]
    if n == 0:
        return 
    elif n == 1:
        bk += 1
    elif n == -1:
        wh += 1
    S[y][x] = 0
    if 0 < y and S[y-1][x] == -n:
        check(S, x, y-1)
    if 0 < x and S[y][x-1] == -n:
        check(S, x-1, y)
    if y < H-1 and S[y+1][x] == -n:
        check(S, x, y+1)
    if x < W-1 and S[y][x+1] == -n:
        check(S, x+1, y)
    return 

cnt = 0
for y in range(H):
    for x in range(W):
        if S[y][x] == 1:
            check(S, x, y)
            cnt += wh*bk
            wh = 0
            bk = 0
            
print(cnt)

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

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


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

used = [[False for _ in range(W)] for _ in range(H)]


def dfs(x, y):
    global nb, nw
    if S[y][x] == '
        nb += 1
    if S[y][x] == '.':
        nw += 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or nx >= W or ny < 0 or ny >= H:
            continue
        if used[ny][nx]:
            continue
        if S[y][x] == '
            continue
        if S[y][x] == '.' and S[ny][nx] == '.':
            continue
        used[ny][nx] = True
        dfs(nx, ny)

ans = 0
for i in range(H):
    for j in range(W):
        if not used[i][j]:
            used[i][j] = True
            nb = 0
            nw = 0
            dfs(j, i)
            ans += nb*nw
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 9)

H, W = map(int, input().split())
s_list = []
for i in range(H):
    s_list.append(input())
check = [[False for _ in range(W)] for _ in range(H)]
move_x = [1, 0, -1, 0]
move_y = [0, 1, 0, -1]


def dfs(i, j):
    check[i][j] = True

    if s_list[i][j] == "
        cnt[0] += 1
    else:
        cnt[1] += 1

    for m in range(4):
        next_i = i + move_y[m]
        next_j = j + move_x[m]
        if 0 <= next_i < H and 0 <= next_j < W and s_list[i][j] != s_list[next_i][next_j] \
                and not check[next_i][next_j]:
            dfs(next_i, next_j)


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

Solution (Python):
H, W = map(int, input().split())
s_list = []
for i in range(H):
    s_list.append(input())
check = [[False for _ in range(W)] for _ in range(H)]
move_x = [1, 0, -1, 0]
move_y = [0, 1, 0, -1]
import sys
sys.setrecursionlimit(10**9)

def dfs(i, j):
    check[i][j] = True

    if s_list[i][j] == "
        cnt[0] += 1
    else:
        cnt[1] += 1

    for m in range(4):
        next_i = i + move_y[m]
        next_j = j + move_x[m]
        if 0 <= next_i < H and 0 <= next_j < W  and s_list[i][j] != s_list[next_i][next_j] \
                and not check[next_i][next_j]:
            dfs(next_i, next_j)


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

Solution (Python):
from collections import deque

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

visited = []
for _ in [0]*H:
	visited.append([False] * W)

delta = [[1, 0], [0, 1], [-1, 0], [0, -1]]

ans = 0
for x in range(H):
	for y in range(W):
		if visited[x][y]: continue
		b = 0
		w = 0
		queue = deque()
		queue.append([x, y])
		visited[x][y] = True
		while len(queue) is not 0:
			px, py = queue[0]
			queue.popleft()
			if S[px][py] == '
			else: w += 1
			found = False
			for dx, dy in delta:
				nx = px + dx
				ny = py + dy
				if 0 <= nx < H and 0 <= ny < W and not visited[nx][ny]:
					if S[px][py] != S[nx][ny]:
						found = True
						visited[nx][ny] = True
						queue.append([nx, ny])

		ans += b * w

print(ans)

Solution (Python):
h,w = list(map(int, input().split())) 
s=list([]) 
foot = list([False for i in range(w)] for j in range(h))

def is_new_white(i,j):
    global h,w, s, foot
    if ((i<0) or (j<0) or (i>=h) or(j>=w)):
        return False
    elif (not foot[i][j] and (s[i][j] == ".")):
        return True
    else:
        return False

def is_new_black(i,j):
    global h,w, s, foot
    if ((i<0) or (j<0) or (i>=h) or(j>=w)):
        return False
    elif (not foot[i][j] and (s[i][j] == "
        return True
    else:
        return False

def check(i,j):
    global s, foot
    black = list([])
    white = list([])
    white_c = 0
    black_c = 0
    
    if foot[i][j] == True:
        return 0
    else:
        if s[i][j] == "
            black.append([i,j])
            foot[i][j] = True
            black_c += 1
        else:
            white.append([i,j])
            foot[i][j] = True
            white_c += 1

    while (bool(black) or bool(white)):
        while bool(black):
            pos = black.pop(0)
            tmp = [[pos[0]-1,pos[1]],[pos[0],pos[1]-1],[pos[0]+1,pos[1]],[pos[0],pos[1]+1]]
            for x in tmp:
                if is_new_white(x[0], x[1]):
                    white_c += 1
                    white.append([x[0],x[1]])
                    foot[x[0]][x[1]] = True

        while bool(white):
            pos = white.pop(0)
            tmp = [[pos[0]-1,pos[1]],[pos[0],pos[1]-1],[pos[0]+1,pos[1]],[pos[0],pos[1]+1]]
            for x in tmp:
                if is_new_black(x[0], x[1]):
                    black_c += 1
                    black.append([x[0],x[1]])
                    foot[x[0]][x[1]] = True
    return black_c * white_c


for i in range(h):
    s.append(input())

ans = 0
for i in range(h):
    for j in range(w):
        ans += check(i,j)

print(ans)

Solution (Python):
from collections import deque

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

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

def bfs(i, j):
    b, w = 0, 0
    visited[i][j] = True
    que = deque([(i, j)])

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

        for di, dj in move:
            ni, nj = ci + di, cj + dj
            if not (0 <= ni < H and 0 <= nj < W) or visited[ni][nj]:
                continue
            if S[ci][cj] != S[ni][nj]:
                visited[ni][nj] = True
                que.append((ni, nj))

    return b * w


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

Solution (Python):
from collections import deque

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

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

def bfs(i, j):
    b, w = 0, 0
    visited[i][j] = True
    que = deque([(i, j)])

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

        for di, dj in move:
            ni, nj = ci + di, cj + dj
            if not (0 <= ni < H and 0 <= nj < W) or visited[ni][nj]:
                continue
            if S[ci][cj] != S[ni][nj]:
                visited[ni][nj] = True
                que.append((ni, nj))

    return b * w


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

Solution (Python):


import sys
from collections import Counter, defaultdict, deque

INF = float('inf')
MOD = 10 ** 9 + 7
dy = (0, -1, 0, 1)
dx = (1, 0, -1, 0)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()


H, W = LI()
B = [[1 if s == '


def BFS(i, j):
    white = 0
    queue = deque([(i, j)])
    visited = set()
    visited_b = set()  
    while queue:
        y, x = queue.pop()
        color = B[y][x]

        if color == 0 and (y, x) not in visited:
            white += 1

        if color == 1:
            visited_b.add((y, x))
        visited.add((y, x))

        for k in range(4):
            ny = y + dy[k]
            nx = x + dx[k]
            if (ny, nx) in visited:
                continue

            if ny < 0 or ny >= H or nx < 0 or nx >= W:
                continue

            if B[ny][nx] == color:
                continue

            queue.append((ny, nx))

    return white, visited_b


ans = 0
visited_b = set()
for h in range(H):
    for w in range(W):
        if B[h][w] == 1 and (h, w) not in visited_b:
            tmp, v = BFS(h, w)
            ans += tmp * len(v)
            visited_b |= v

print(ans)

Solution (Python):


import sys
from collections import Counter, defaultdict

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()



class UnionFind:
    
    
    def __init__(self, size: int) -> None:
        self.nodes = [-1] * size  

    def get_root(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            self.nodes[x] = self.get_root(self.nodes[x])
            return self.nodes[x]

    def unite(self, x: int, y: int) -> None:
        root_x, root_y = self.get_root(x), self.get_root(y)
        if root_x != root_y:
            if self.nodes[root_x] != self.nodes[root_y]:  
                
                
                if self.nodes[root_x] < self.nodes[root_y]:
                    self.nodes[root_y] = root_x
                else:
                    self.nodes[root_x] = root_y
            else:
                
                
                self.nodes[root_x] += -1
                self.nodes[root_y] = root_x


H, W = LI()
B = [[1 if s == '

uf = UnionFind(H * W)

for h in range(H):
    for w in range(W):
        if w < W - 1 and B[h][w] != B[h][w + 1]:
            uf.unite(h * W + w, h * W + w + 1)
        if h < H - 1 and B[h][w] != B[h + 1][w]:
            uf.unite(h * W + w, (h + 1) * W + w)

black = defaultdict(int)
white = defaultdict(int)
for h in range(H):
    for w in range(W):
        i = h * W + w
        if B[h][w] == 1:
            black[uf.get_root(i)] += 1
        else:
            white[uf.get_root(i)] += 1

ans = 0
for n in black.keys():
    ans += black[n] * white[n]

print(ans)