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):
h,w=[int(j) for j in input().split()]
s=[input()for i in range(h)]
par=[-1 for i in range(h*w)]    
def root(a):
    if par[a]<0:
        return a
    else:
        return root(par[a])

def size(a):
    return -par[root(a)]

def connect(a,b):
    a=root(a)
    b=root(b)
    if a==b:
        return False
    if size(a)<size(b):
        a,b=b,a
    par[a]+=par[b]
    par[b]=a
    return True

for i in range(h):
    for j in range(w):
        for x,y in [(1,0),(-1,0),(0,1),(0,-1)]:
            p,q=i+x,j+y
            if 0<=p<h and 0<=q<w:
                if s[p][q]!=s[i][j]:
                    if root(w*p+q)!=root(w*i+j):
                        connect(w*p+q,w*i+j)

from collections import Counter
c=Counter()
for i in range(h):
    for j in range(w):
        p=i*w+j
        q=root(p)
        if c[q]==0:
            c[q]=[0,0]
        if s[i][j]=="
            c[q][0]+=1
        else:
            c[q][1]+=1
ans=0
for i in c:
    ans+=c[i][0]*c[i][1]
print(ans)

Solution (Python):
h,w=map(int,input().split())
s=[]
for _ in range(h):
	s.append(input())
num=[[-1]*w for _ in range(h)]
stack=[]
def dfs():
	while stack:
		r=stack.pop()
		for x in ((1,0),(-1,0),(0,1),(0,-1)):
			a,b,c,d=r[0],r[1],x[0],x[1]
			if 0<=a+c<h and 0<=b+d<w:
				if s[a+c][b+d]!=s[a][b] and num[a+c][b+d]==-1:
					num[a+c][b+d]=num[a][b]
					stack.append((a+c,b+d))
color=0
for i in range(h):
	for j in range(w):
		if num[i][j]==-1:
			stack.append((i,j))
			num[i][j]=color
			dfs()
			color+=1
color_num=[[0,0]for _ in range(color)]
for i in range(h):
	for j in range(w):
		if s[i][j]==".":
			color_num[num[i][j]][0]+=1
		else:
			color_num[num[i][j]][1]+=1
ans=0
for x in color_num:
	ans+=x[0]*x[1]
print(ans)

Solution (Python):
from collections import deque

h,w = map(int, input().split())
s = ["0" * (w+2)]  + ["0"+input()+"0" for i in range(h)] + ["0" * (w+2)] 
not_visited = [[0] * (w+2)] + [[0] + [1] * w + [0] for i in range(h)] + [[0] * (w+2)]
ans = 0
for i in range(1,h+1):
  for j in range(1,w+1):
    if s[i][j] == ".":
      continue
    black, white = 1,0
    queue = deque([(i,j,1)])
    not_visited[i][j] = 0
    while queue:
      H,W,color = queue.popleft()
      if not_visited[H-1][W]:
        if color and s[H-1][W] == ".":
          not_visited[H-1][W] = 0
          white += 1
          queue.append((H-1,W,0))
        elif color == 0 and s[H-1][W] == "
          not_visited[H-1][W] = 0
          black += 1
          queue.append((H-1,W,1))
      if not_visited[H+1][W]:
        if color and s[H+1][W] == ".":
          not_visited[H+1][W] = 0
          white += 1
          queue.append((H+1,W,0))
        elif color == 0 and s[H+1][W] == "
          not_visited[H+1][W] = 0
          black += 1
          queue.append((H+1,W,1))
      if not_visited[H][W-1]:
        if color and s[H][W-1] == ".":
          not_visited[H][W-1] = 0
          white += 1
          queue.append((H,W-1,0))
        elif color == 0 and s[H][W-1] == "
          not_visited[H][W-1] = 0
          black += 1
          queue.append((H,W-1,1))
      if not_visited[H][W+1]:
        if color and s[H][W+1] == ".":
          not_visited[H][W+1] = 0
          white += 1
          queue.append((H,W+1,0))
        elif color == 0 and s[H][W+1] == "
          not_visited[H][W+1] = 0
          black += 1
          queue.append((H,W+1,1))
    ans += black * white
print(ans)

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

def dfs(y,x):
    visited[y][x]=True
    blk,wht=0,0
    for dy,dx in ((-1,0),(0,-1),(1,0),(0,1)):
      ny,nx=y+dy,x+dx
      if (not (0<=ny<h)) or (not (0<=nx<w)) or visited[ny][nx]: 
        continue
      if s[y][x]!=s[ny][nx]:
        nb,nw=dfs(ny,nx)
        blk+=nb
        wht+=nw
    if s[y][x]=="
      blk+= 1
    else:
      wht+= 1
    return blk,wht

ans=0
for i in range(h):
  for j in range(w):
    
    if not visited[i][j]:
      blk,wht=dfs(i,j)
      ans+=blk*wht
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10**7)

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

check = [-1]*(h*w)




vx = [0,1,0,-1]
vy = [1,0,-1,0]

def dfs(num,clr):
    
    
    
    
    y = num//w
    x = num%w
    for j in range(4):
        ny = y + vy[j]
        nx = x + vx[j]
        if ny >= 0 and ny < h and nx >= 0 and nx < w:
            new_num = ny*w+nx
            if check[new_num] != -1:
                continue
            
            if clr == '
                
                if si[ny][nx] == '.':
                    check[new_num] = check[num]
                    dfs(new_num,'.')
            else:
                    
                if si[ny][nx] == '
                    check[new_num] = check[num]
                    dfs(new_num,'
            

for i in range(h*w):
    
    y = i//w
    x = i%w
    if si[y][x] == '
        if check[i] != -1:
            continue
        check[i] = i
        dfs(i,'
        
        

ans = 0

li = [0]*(h*w+1)

for i in range(h):
    for j in range(w):
        if si[i][j] == '.':
            li[check[i*w+j]] += 1



for i in range(h):
    for j in range(w):
        if si[i][j] == '
            ans += li[check[i*w+j]]
            
print(ans)

Solution (Python):
import queue

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

q = queue.Queue()

check = [-1]*(h*w)

vx = [0,1,0,-1]
vy = [1,0,-1,0]

for i in range(h*w):
    y = i//w
    x = i%w
    if si[y][x] == '
        if check[i] != -1:
            continue
        q.put([i,'
        check[i] = i
        
        while not q.empty():
            num, clr = q.get()
            y = num//w
            x = num%w
            
            for j in range(4):
                ny = y + vy[j]
                nx = x + vx[j]
                if ny >= 0 and ny < h and nx >= 0 and nx < w:
                    new_num = ny*w+nx
                    if check[new_num] != -1:
                        continue
                    
                    if clr == '
                        if si[ny][nx] == '.':
                            q.put([new_num,'.'])
                            check[new_num] = check[num]
                    else:
                        if si[ny][nx] == '
                            q.put([new_num,'
                            check[new_num] = check[num]
    


ans = 0

li = [0]*(h*w+1)

for i in range(h):
    for j in range(w):
        if si[i][j] == '.':
            li[check[i*w+j]] += 1



for i in range(h):
    for j in range(w):
        if si[i][j] == '
            ans += li[check[i*w+j]]
            
print(ans)

Solution (Python):
import queue

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

q = queue.Queue()

check = [-1]*(h*w)

vx = [0,1,0,-1]
vy = [1,0,-1,0]

for i in range(h*w):
    y = i//w
    x = i%w
    if si[y][x] == '
        if check[i] != -1:
            continue
        q.put([i,'
        check[i] = i
        
        while not q.empty():
            num, clr = q.get()
            y = num//w
            x = num%w
            
            for j in range(4):
                ny = y + vy[j]
                nx = x + vx[j]
                if ny >= 0 and ny < h and nx >= 0 and nx < w:
                    new_num = ny*w+nx
                    if check[new_num] != -1:
                        continue
                    
                    if clr == '
                        if si[ny][nx] == '.':
                            q.put([new_num,'.'])
                            check[new_num] = check[num]
                    else:
                        if si[ny][nx] == '
                            q.put([new_num,'
                            check[new_num] = check[num]
    


ans = 0

li = [0]*(h*w+1)

for i in range(h):
    for j in range(w):
        if si[i][j] == '.':
            li[check[i*w+j]] += 1



for i in range(h):
    for j in range(w):
        if si[i][j] == '
            ans += li[check[i*w+j]]
            
print(ans)

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

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1 for _ in range(n+1)]
 
    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
 
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
 
    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
ki = UnionFind(h*w)

vx = [0,1,0,-1]
vy = [1,0,-1,0]

for i in range(h):
    for j in range(w):
        if si[i][j] == '
            for k in range(4):
                ny = i + vy[k]
                nx = j + vx[k]
                if ny >= 0 and ny < h and nx >= 0 and nx < w:
                    if si[ny][nx] == '.':
                        if ki.same_check(i*w+j,ny*w+nx) == True:
                            continue
                        ki.union(i*w+j,ny*w+nx)
ans = 0

li = [0]*(h*w+1)

for i in range(h):
    for j in range(w):
        if si[i][j] == '.':
            li[ki.find(i*w+j)] += 1

for i in range(h):
    for j in range(w):
        if si[i][j] == '
            ans += li[ki.find(i*w+j)]
            
print(ans)

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

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1 for _ in range(n+1)]
 
    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
 
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
 
    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
ki = UnionFind(h*w)

vx = [0,1,0,-1]
vy = [1,0,-1,0]

for i in range(h):
    for j in range(w):
        if si[i][j] == '
            for k in range(4):
                ny = i + vy[k]
                nx = j + vx[k]
                if ny >= 0 and ny < h and nx >= 0 and nx < w:
                    if si[ny][nx] == '.':
                        
                        
                        ki.union(i*w+j,ny*w+nx)
ans = 0

li = [0]*(h*w+1)

for i in range(h):
    for j in range(w):
        if si[i][j] == '.':
            li[ki.find(i*w+j)] += 1

for i in range(h):
    for j in range(w):
        if si[i][j] == '
            ans += li[ki.find(i*w+j)]
            
print(ans)

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

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1 for _ in range(n+1)]
 
    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
 
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
 
    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
ki = UnionFind(h*w)

vx = [0,1,0,-1]
vy = [1,0,-1,0]

for i in range(h):
    for j in range(w):
        if si[i][j] == '
            for k in range(4):
                ny = i + vy[k]
                nx = j + vx[k]
                if ny >= 0 and ny < h and nx >= 0 and nx < w:
                    if si[ny][nx] == '.':
                        
                        
                        ki.union(i*w+j,ny*w+nx)
ans = 0

li = [0]*(h*w+1)

for i in range(h):
    for j in range(w):
        if si[i][j] == '.':
            li[ki.find(i*w+j)] += 1

for i in range(h):
    for j in range(w):
        if si[i][j] == '
            ans += li[ki.find(i*w+j)]
            
print(ans)

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

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1 for _ in range(n+1)]
 
    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
 
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
 
    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
ki = UnionFind(h*w)

vx = [0,1,0,-1]
vy = [1,0,-1,0]

for i in range(h):
    for j in range(w):
        if si[i][j] == '
            
            for k in range(4):
                ny = i + vy[k]
                nx = j + vx[k]
                if ny >= 0 and ny < h and nx >= 0 and nx < w:
                    
                    if si[ny][nx] == '.':
                        
                        
                        if ki.same_check(i*w+j,ny*w+nx) == True:
                            continue
                        
                        ki.union(i*w+j,ny*w+nx)
                        
ans = 0





li = [0]*(h*w+1)
"""
for i in range(h):
    for j in range(w):
        
        ki.find(i*w+j)
"""

for i in range(h):
    for j in range(w):
        if si[i][j] == '.':
            li[ki.find(i*w+j)] += 1
            



for i in range(h):
    for j in range(w):
        if si[i][j] == '
            
            
            
            
            ans += li[ki.find(i*w+j)]
            
            
print(ans)

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

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1 for _ in range(n+1)]
 
    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
 
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
 
    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
ki = UnionFind(h*w)

vx = [0,1,0,-1]
vy = [1,0,-1,0]

for i in range(h):
    for j in range(w):
        if si[i][j] == '
            
            for k in range(4):
                ny = i + vy[k]
                nx = j + vx[k]
                if ny >= 0 and ny < h and nx >= 0 and nx < w:
                    
                    if si[ny][nx] == '.':
                        
                        
                        if ki.same_check(i*w+j,ny*w+nx) == True:
                            continue
                        
                        ki.union(i*w+j,ny*w+nx)
                        
ans = 0





li = [0]*(h*w+1)

for i in range(h):
    for j in range(w):
        
        ki.find(i*w+j)
        """
        if si[i][j] == '.':
            li[ki.find(i*w+h)] += 1
            print(ki.find(i*w+h))
        """

for i in range(h):
    for j in range(w):
        if si[i][j] == '.':
            li[ki.par[i*w+j]] += 1
            



for i in range(h):
    for j in range(w):
        if si[i][j] == '
            
            
            
            
            ans += li[ki.find(i*w+j)]
            
            
print(ans)

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

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1 for _ in range(n+1)]
 
    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
 
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
 
    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
ki = UnionFind(h*w)

vx = [0,1,0,-1]
vy = [1,0,-1,0]

for i in range(h):
    for j in range(w):
        if si[i][j] == '
            
            for k in range(4):
                ny = i + vy[k]
                nx = j + vx[k]
                if ny >= 0 and ny < h and nx >= 0 and nx < w:
                    
                    if si[ny][nx] == '.':
                        
                        
                        if ki.same_check(i*w+j,ny*w+nx) == True:
                            continue
                        
                        ki.union(i*w+j,ny*w+nx)
                        
ans = 0





li = [0]*(h*w+1)

for i in range(h):
    for j in range(w):
        
        ki.find(i*w+j)
        """
        if si[i][j] == '.':
            li[ki.find(i*w+h)] += 1
            print(ki.find(i*w+h))
        """

for i in range(h):
    for j in range(w):
        if si[i][j] == '.':
            li[ki.par[i*w+j]] += 1
            



for i in range(h):
    for j in range(w):
        if si[i][j] == '
            
            
            
            
            ans += li[ki.find(i*w+j)]
            
            
print(ans)

Solution (Python):

from collections import deque
h,w=map(int,input().split())
s=[]
for _ in range(h):
    s.append(input())
ans=0        
sc=[[0 for i in range(w)] for j in range(h)]

for x in range(h):
    for y in range(w):
        if s[x][y]=='.' or sc[x][y]==1:
            continue
        path = deque([[x,y]])
        sc[x][y]=1
        b=1
        wh=0
        while len(path)>0:
            p = path.popleft()
            i,j=p[0],p[1]
            tc = '.' if s[i][j] == '
            point = b if s[i][j] == '
            if i > 0 and s[i-1][j]==tc and sc[i-1][j]==0:
                sc[i-1][j]=1
                path.append([i-1,j])
                if s[i-1][j] == '
                    b += 1
                else:
                    wh += 1
                ans += point
            if j > 0 and s[i][j-1]==tc and sc[i][j-1]==0:
                sc[i][j-1]=1
                path.append([i,j-1])
                if s[i][j-1] == '
                    b += 1
                else:
                    wh += 1
                ans += point
            if i < h-1 and s[i+1][j]==tc and sc[i+1][j]==0:
                sc[i+1][j]=1
                path.append([i+1,j])
                if s[i+1][j] == '
                    b += 1
                else:
                    wh += 1
                ans += point
            if j < w-1 and s[i][j+1]==tc and sc[i][j+1]==0:
                sc[i][j+1]=1
                path.append([i,j+1])
                if s[i][j+1] == '
                    b += 1
                else:
                    wh += 1
                ans += point
print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


h, w = LI()
grid = SRL(h)
visited = [[0] * w for _ in range(h)]

def solve(sy, sx):
    dq = deque([(sy, sx)])
    visited[sy][sx] = 1
    bi = [0, 1]
    while dq:
        cy, cx = dq.popleft()
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            ny = cy + i
            nx = cx + j
            if 0 <= ny < h and 0 <= nx < w and not visited[ny][nx]:
                if grid[ny][nx] != grid[cy][cx]:
                    bi[int(grid[sy][sx] == grid[ny][nx])] += 1
                    dq += [(ny, nx)]
                    visited[ny][nx] = 1
    return bi[0] * bi[1]

ans = 0
for y in range(h):
    for x in range(w):
        if visited[y][x]:
            continue
        else:
            ans += solve(y, x)


print(ans)

Solution (Python):
from collections import deque,defaultdict
import sys
from collections import defaultdict
input = sys.stdin.readline

H, W = map(int, input().split())
C = [list(input()) for i in range(H)]
INF = 10 ** 9
go = [[1, 0], [0, 1], [-1, 0], [0, -1]]
que = deque()
ans  = -1

mass = ["
groups = [[-1 for _ in range(W)] for _ in range(H)]
group_num = -1
for sx in range(W):
    for sy in range(H): 
        if C[sy][sx] == "
            group_num += 1
            que.append((sy,sx))
            groups[sy][sx] = group_num
            while que: 
                y,x = que.popleft()
                for temp in go:
                    gx,gy = temp
                    nx = x + gx
                    ny = y + gy
                    should = abs(sx - nx) + abs(sy - ny) 
                    should %= 2
                    if 0<= nx < W and 0<= ny < H and C[ny][nx] == mass[should]:
                        if groups[ny][nx] == -1: 
                            groups[ny][nx] = group_num
                            que.append( (ny,nx))
ans = 0
di_sharp = defaultdict(lambda :0)
di_dot = defaultdict(lambda :0)
ma = -1
for sx in range(W):
    for sy in range(H):
        if groups[sy][sx] >= 0:
           color = groups[sy][sx]
           ma = max(ma,color)
           if C[sy][sx] =="
               di_sharp[color] += 1
           else:
               di_dot[color] += 1

for i in range(ma + 1):
    ans += di_dot[i]  * di_sharp[i]

print(ans)

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

def dfs(y,x):
    visited[y][x] = True
    blk, wht = 0,0
    for dy,dx in zip((-1,1,0,0),(0,0,-1,1)):
        ny,nx = y+dy, x+dx
        if (not (0<=ny<h)) or (not (0<=nx<w)) or visited[ny][nx]:
            continue
        if s[y][x]!=s[ny][nx]:
            nb,nw = dfs(ny,nx)
            blk += nb
            wht += nw
    if s[y][x]=='
        blk += 1
    else:
        wht += 1
    return blk, wht

ans = 0
for i in range(h):
    for j in range(w):
        if not visited[i][j]:
            blk, wht = dfs(i,j)
            ans += blk*wht
print(ans)

Solution (Python):
from collections import deque

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

def dfs(x, y):
  stack = deque()
  stack.append((x, y))
  num_w = 0
  num_b = 0
  while stack:
    cx, cy = stack.popleft()
    cc = S[cy][cx]
    for i, j in zip(dx, dy):
      nx = i + cx
      ny = j + cy
      if (0 <= nx < w and 0 <= ny < h) and not visited[ny][nx] and S[ny][nx] != cc:
        visited[ny][nx] = True
        stack.append((nx, ny))
        if cc == ".":
          num_w += 1
        else:
          num_b += 1
  else:
    return num_w, num_b

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

visited = [[False] * w for _ in range(h)]
  
ans = 0
for i in range(w):
  for j in range(h):
    if not visited[j][i]:
      num_w, num_b = dfs(i, j)
      ans += num_b * num_w
      
print(ans)

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

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

def dfs(y, x):
    visited[y][x] = True
    blk, wht = 0, 0

    for dy, dx in ((-1, 0), (0, -1), (1, 0), (0, 1)):
        ny, nx = y+dy, x+dx
        if (not (0 <= ny < h)) or (not (0 <= nx < w)) or visited[ny][nx]: continue
        if s[y][x] != s[ny][nx]:
            nb, nw = dfs(ny, nx)
            blk += nb; wht += nw
    
    if s[y][x] == "
    else: wht += 1

    return blk, wht

ans = 0
for i in range(h):
    for j in range(w):
        if not visited[i][j]:
            blk, wht = dfs(i, j)
            ans += blk * wht

print(ans)

Solution (Python):
H, W = map(int, input().split())
S = [0]*(H+2)
S[0] = '*'*(W+2)
S[H+1] = '*'*(W+2)
for h in range(1,H+1):
  S[h] = '*' + input() + '*'

import sys
sys.setrecursionlimit(10**8)

bw = ['

visited = [[False]*(W+2) for h in range(H+2)]
ans = 0
dh = [0,1,0,-1]
dw = [1,0,-1,0]

def dfs(h,w,c):
  
  for i in range(4):
    h0 = h+dh[i]
    w0 = w+dw[i]
    if S[h0][w0]==bw[c^1] and visited[h0][w0]==False:
      visited[h0][w0]=True
      bw_count[c^1]+=1
      dfs(h0,w0,c^1)
  
for h in range(H+2):
  for w in range(W+2):
    if S[h][w]=='
      bw_count = [1,0]
      visited[h][w]=True
      dfs(h,w,0)
      ans += bw_count[0]*bw_count[1]

print(ans)

Solution (Python):
from itertools import groupby

class UnionFindVerSize():
    def __init__(self, N):
        global S,H,W
        """ N個のノードのUnion-Find木を作成する """
        
        self._parent = [n for n in range(0, N)]
        
        self._size = [1] * N

        self._black=[0]*N
        self._white=[0]*N

        for i in range(0,H*W):
            h=i//W
            w=i%W
            if S[h][w]=='
                self._black[i]=1
                self._white[i]=0
            else:
                self._black[i]=0
                self._white[i]=1

    def find_root(self, x):
        """ xの木の根(xがどのグループか)を求める """
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x]) 
        return self._parent[x]

    def unite(self, x, y):
        """ xとyの属するグループを併合する """
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._black[gy]+=self._black[gx]
            self._white[gy]+=self._white[gx]
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._black[gx]+=self._black[gy]
            self._white[gx]+=self._white[gy]
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        """ xが属するグループのサイズ（個数）を返す """
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        """ グループ数を計算して返す """
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

    def calc_black(self,x):
        return self._black[self.find_root(x)]

    def calc_white(self,x):
        return self._white[self.find_root(x)]


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

uf=UnionFindVerSize(H*W)
for i in range(0,H*W):
    h=i//W
    w=i%W
    if W-1>=w+1:
        if S[h][w]!=S[h][w+1]:
            uf.unite(i,i+1)
    if H-1>=h+1:
        if S[h][w]!=S[h+1][w]:
            uf.unite(i,i+W)

root=[uf.find_root(i) for i in range(0,H*W)]
root.sort()

ans=0
root=groupby(root)
for key,group in root:
    black=uf.calc_black(key)
    white=uf.calc_white(key)
    ans+=black*white

print(ans)