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 *
import sys
sys.setrecursionlimit(10**6)

H, W = map(int, input().split())
mas = []
for i in range(H):
    mas.append(input())
    
color = []
for i in range(H):
    color.append([-1] * W)

def DFS(node, c_color):
    x = node[0]
    y = node[1]
    nb = [[x, y-1], [x, y+1], [x+1, y], [x-1, y]]
    deq = deque()
    for i in range(4):
        if(nb[i][0] >= 0 and nb[i][0] < H and nb[i][1] >= 0 and nb[i][1] < W):
            if(color[nb[i][0]][nb[i][1]] == -1):
                deq.append(nb[i])
    deq_ = deque()
    while(deq):
        next_node = deq.popleft()
        if(mas[next_node[0]][next_node[1]] != mas[node[0]][node[1]]):
            color[next_node[0]][next_node[1]] = c_color
            deq_.append(next_node)            
    while(deq_):
        next_node = deq_.popleft()
        DFS(next_node, c_color)
    return
        
current_color = 0
for i in range(H):
    for j in range(W):
        if(color[i][j] >= 0):
            continue
        else:
            color[i][j] = current_color
            DFS([i, j], current_color)
            current_color += 1

color_num = []
for i in range(current_color):
    color_num.append([0, 0])
for i in range(H):
    for j in range(W):
        if(mas[i][j] == '
            color_num[color[i][j]][0] += 1
        else:
            color_num[color[i][j]][1] += 1

ans = 0
for i in range(len(color_num)):
    ans += color_num[i][0] * color_num[i][1]
print(ans)

Solution (Python):
from collections import *
import sys
sys.setrecursionlimit(10**6)

H, W = map(int, input().split())
mas = []
for i in range(H):
    line = input()
    temp = []
    for j in range(W):
        temp.append(line[j])
    mas.append(temp)

color = []
for i in range(H):
    color.append([-1] * W)

def DFS(node, c_color):
    x = node[0]
    y = node[1]
    nb = [[x, y-1], [x, y+1], [x+1, y], [x-1, y]]
    deq = deque()
    for i in range(4):
        if(nb[i][0] >= 0 and nb[i][0] < H and nb[i][1] >= 0 and nb[i][1] < W):
            if(color[nb[i][0]][nb[i][1]] == -1):
                deq.append(nb[i])

    deq_ = deque()
    while(deq):
        next_node = deq.popleft()
        if(mas[next_node[0]][next_node[1]] != mas[node[0]][node[1]]):
            color[next_node[0]][next_node[1]] = c_color
            deq_.append(next_node)
            
    while(deq_):
        next_node = deq_.popleft()
        DFS(next_node, c_color)
    return
        
current_color = 0
for i in range(H):
    for j in range(W):
        if(color[i][j] >= 0):
            continue
        else:
            color[i][j] = current_color
            DFS([i, j], current_color)
            current_color += 1

color_num = []
for i in range(current_color):
    color_num.append([0, 0])


for i in range(H):
    for j in range(W):
        if(mas[i][j] == '
            color_num[color[i][j]][0] += 1
        else:
            color_num[color[i][j]][1] += 1

ans = 0
for i in range(len(color_num)):
    ans += color_num[i][0] * color_num[i][1]

print(ans)

Solution (Python):



def dsMakeSet(ds, x):
    ds[x] = x


def dsFind(ds, x):
    if ds[x] == x:
        return x

    x0 = x
    while ds[x] != x:
        x = ds[x]

    ds[x0] = x
    return x


def dsUnion(ds, x, y):
    xRoot = dsFind(ds, x)
    yRoot = dsFind(ds, y)
    
    if xRoot != yRoot:
        ds[yRoot] = xRoot
        return True

    return False



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

    ds = {}
    for i in range(H):
        s0 = S[i-1] if i > 0 else None
        s1 = S[i]

        for j in range(W):
            dsMakeSet(ds, (i, j))

            if j > 0 and s1[j-1] != s1[j]:
                dsUnion(ds, (i, j-1), (i, j))
                
            if i > 0 and s0[j] != s1[j]:
                dsUnion(ds, (i-1, j), (i, j))
            
    bCnt = {}
    wCnt = {}

    for x in ds:
        y = dsFind(ds, x)
        
        if not y in bCnt:
            bCnt[y] = 0
            wCnt[y] = 0

        if S[x[0]][x[1]] == '
            bCnt[y] += 1
        else:
            wCnt[y] += 1

    s = sum(bCnt[x]*wCnt[x] for x in bCnt)
    print(s)
                

    


if __name__ == '__main__':
    main()

Solution (Python):
H,W = map(int,input().split())
S = [[c==".
V = [[-1]*W for _ in [0]*H]
ans = 0
for si in range(H):
    for sj in range(W):
        if V[si][sj] != -1:continue
        V[si][sj] = 0
        cnt = [0,0]
        cnt[(S[si][sj]+si+sj)%2]+=1
        q = [[si,sj]]
        while q:
            i,j = q.pop()
            for di,dj in ((1,0),(-1,0),(0,1),(0,-1)):
                if (not (0<=i+di<H)) or (not (0<=j+dj<W)):continue
                if V[i+di][j+dj] != -1:continue
                if S[i][j] != S[i+di][j+dj]:continue
                V[i+di][j+dj] = V[i][j]
                q.append([i+di,j+dj])
                cnt[(S[i][j]+i+di+j+dj)%2] += 1
        ans += cnt[0]*cnt[1]
print(ans)

Solution (Python):
h,w=map(int,input().split())
s=["?"*(w+2)]+["?"+input()+"?" for _ in [0]*h]+["?"*(w+2)]
memo=[[None for _ in range(w)] for _ in range(h)]
cnt=0
for i in range(1,h+1):
    for j in range(1,w+1):
        if memo[i-1][j-1]==None:
            memo[i-1][j-1]=True
            maru=(s[i][j]==".")
            batsu=1-maru
            q=[(i,j)]
            while(q):
                qq=[]
                for k,l in q:
                    if s[k-1][l]!="?":
                        if memo[k-2][l-1]==None:
                            if s[k-1][l]!=s[k][l]:
                                memo[k-2][l-1]=True
                                qq.append((k-1,l))
                                if s[k-1][l]==".":
                                    maru+=1
                                else:
                                    batsu+=1
                    if s[k+1][l]!="?":
                        if memo[k][l-1]==None:
                            if s[k+1][l]!=s[k][l]:
                                memo[k][l-1]=True
                                qq.append((k+1,l))
                                if s[k+1][l]==".":
                                    maru+=1
                                else:
                                    batsu+=1
                    if s[k][l-1]!="?":
                        if memo[k-1][l-2]==None:
                            if s[k][l-1]!=s[k][l]:
                                memo[k-1][l-2]=True
                                qq.append((k,l-1))
                                if s[k][l-1]==".":
                                    maru+=1
                                else:
                                    batsu+=1
                    if s[k][l+1]!="?":
                        if memo[k-1][l]==None:
                            if s[k][l+1]!=s[k][l]:
                                memo[k-1][l]=True
                                qq.append((k,l+1))
                                if s[k][l+1]==".":
                                    maru+=1
                                else:
                                    batsu+=1
                q=qq
            cnt+=maru*batsu
print(cnt)

Solution (Python):
import sys
from sys import stdin
sys.setrecursionlimit(10**7)
dx = (1, 0, -1, 0)
dy = (0, 1, 0, -1)
H, W = [int(_) for _ in stdin.readline().rstrip().split()]
field = [list(stdin.readline().rstrip()) for _ in range(H)]
seen = [[False for i in range(400)] for j in range(400)]
num_b, num_w = 0, 0
ans = 0

def dfs(h, w):
    seen[h][w] = True
    if field[h][w] == '
        global num_b
        num_b += 1
    else:
        global num_w
        num_w += 1

    for direction in range(4):
        nh = h + dx[direction]
        nw = w + dy[direction]

        if nh < 0 or nh >= H or nw < 0 or nw >= W:
            continue
        if field[nh][nw] == field[h][w]:
            continue
        if seen[nh][nw]:
            continue

        dfs(nh, nw)

for i in range(H):
    for j in range(W):
        if field[i][j] == '.':
            continue
        if seen[i][j]:
            continue
        num_b, num_w = 0, 0
        dfs(i, j)
        ans += num_b * num_w 

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
h, w = [int(item) for item in input().split()]
field = []
for i in range(h):
    field.append(input().rstrip())

black = 0; white = 0
visited = [[0] * w for _ in range(h)]

def dfs(is_black, i, j):
    global black
    global white
    visited[i][j] = 1
    for x, y in [[1,0], [0,1], [0,-1], [-1,0]]:
        if i+x < 0 or i+x >= h or j+y < 0 or j+y >= w:
            continue
        if visited[i + x][j + y] != 0:
            continue
        if is_black:
            if field[i+x][j+y] == ".":
                white += 1
                dfs(False, i+x, j+y)
        if not is_black:
            if field[i+x][j+y] == "
                black += 1
                dfs(True, i+x, j+y)

ans = 0
for i in range(h):
    for j in range(w):
        if visited[i][j] != 0:
            continue
        if field[i][j] == "
            white = 0; black = 1
            dfs(True, i, j)
        else:
            white = 1; black = 0
            dfs(False, i, j)
        ans += white * black

print(ans)

Solution (Python):
from collections import deque


def bfs(y,x):
    global s
    global fl
    global h
    global w
    global ans
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    count = 1
    black = 0
    d = deque()
    
    d.append([y,x])
    fl[y][x] = 1
    if s[y][x]=='
        black+=1
    while len(d):
        p = d.pop()
        for k in range(4):
            if 0<=p[1]+dx[k] <w and 0<=p[0]+dy[k] <h and s[p[0]][p[1]]!=s[p[0]+dy[k]][p[1]+dx[k]]:
                if fl[p[0]+dy[k]][p[1]+dx[k]]:
                    continue
                d.append([p[0]+dy[k],p[1]+dx[k]])
                count += 1
                fl[p[0]+dy[k]][p[1]+dx[k]] = 1
                if s[p[0]+dy[k]][p[1]+dx[k]]=='
                    black+=1
    ans += black*(count-black)


h, w = map(int, input().split())
s = [input() for i in range(h)]
fl = [[0 for _ in range(w)] for _ in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if not fl[i][j]:
            bfs(i,j)
print(ans)

Solution (Python):
from itertools import product

direction = []
for i in range(4):
    dx = 5 % (i + 1) - 1
    dy = 5 % (i + 2) - 1
    direction.append((dx, dy))
H, W = map(int, input().split())
grid = [input() for _ in range(H)]
visited = [[False for _ in range(W)] for _ in range(H)]
ans = 0
for i, j in product(range(H), range(W)):
    if visited[i][j]: continue
    stack = [(i, j)]
    black = 0; white = 0;
    while stack:
        x, y = stack.pop()
        if visited[x][y]: continue
        visited[x][y] = True
        if grid[x][y] == '
        else: white += 1
        for dx, dy in direction:
            temp_x, temp_y = min(max(x + dx, 0), H-1), min(max(y + dy, 0), W-1)
            if visited[temp_x][temp_y]: continue
            if grid[x][y] != grid[temp_x][temp_y]: stack.append((temp_x, temp_y))
    ans += black * white
print(ans)

Solution (Python):











import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    H, W = MI()
    S =[":"*(W+2)]  + [":"+ST()+":" for _ in range(H)] + [":"*(W+2)]

    checked = set()
    d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    ans = 0
    for h in range(1, H + 1):
        for w in range(1, W + 1):
            if (h, w) in checked:
                continue
            queue = [(h,w)]
            black = 0
            white = 0
            while queue:
                from_h, from_w = queue.pop()
                if (from_h,from_w) in checked:
                    continue
                checked.add((from_h,from_w))
                if S[from_h][from_w] == "
                    black += 1
                else:
                    white += 1
                for dh, dw in d:
                    if S[from_h + dh][from_w + dw] != ":" and (from_h + dh, from_w + dw) not in checked and S[from_h + dh][from_w + dw] != S[from_h][from_w]:
                        queue.append((from_h + dh, from_w + dw))
            ans += black * white
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
def inpl(): return list(map(int, input().split()))

class UnionFind():
    def __init__(self, N):
        self.par = [-1]*(N)
        self.size = [1]*(N)

    def find(self, x):
        if self.par[x] == -1:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            if self.size[px] < self.size[py]:
                px, py = py, px
            self.size[px] += self.size[py]
            self.par[py] = px

H, W = inpl()
S = [[-1]*W for _ in range(H)]
for h in range(H):
    s = input()
    for w in range(W):
        S[h][w] = int(s[w] == "

UF = UnionFind(H*W)

for h in range(H):
    for w in range(W-1):
        if S[h][w] != S[h][w+1]:
            UF.unite(h*W+w, h*W+w+1)
for h in range(H-1):
    for w in range(W):
        if S[h][w] != S[h+1][w]:
            UF.unite(h*W+w, h*W+w+W)

ans = 0
for i in range(H*W):
    if UF.par[i] == -1:
        s = UF.size[i]
        ans += s*(s-1)//2

BC = [0]*(H*W)
WC = [0]*(H*W)

for h in range(H):
    for w in range(W):
        if S[h][w] == 1:
            BC[UF.find(h*W+w)] += 1
        else:
            WC[UF.find(h*W+w)] += 1
print(sum([BC[i]*WC[i] for i in range(H*W)]))

Solution (Python):
import collections

h,w=map(int,input().split())
color=[[0]*w for _ in range(h)]
for i in range(h):
  s=input()
  for j in range(w):
    if s[j]=='
      color[i][j]=1
used=[[0]*400 for _ in range(400)]
ans=0
bc=0
wc=0
for i in range(0,h):
  for j in range(0,w):
    if used[i][j]==1:
      continue
    bc=0
    wc=0
    q=collections.deque()
    used[i][j]=1
    q.append([i,j])
    while 1:
      if len(q)==0:
        break
      else:
        ti,tj=q.popleft()
        if color[ti][tj]==1:
          bc+=1
        else:
          wc+=1
        if ti-1>=0:
          if color[ti][tj]!=color[ti-1][tj]:
            if used[ti-1][tj]==0:
              used[ti-1][tj]=1
              q.append([ti-1,tj])
        if ti+1<=h-1:
          if color[ti][tj]!=color[ti+1][tj]:
            if used[ti+1][tj]==0:
              used[ti+1][tj]=1
              q.append([ti+1,tj])
        if tj-1>=0:
          if color[ti][tj]!=color[ti][tj-1]:
            if used[ti][tj-1]==0:
              used[ti][tj-1]=1
              q.append([ti,tj-1])
        if tj+1<=w-1:
          if color[ti][tj]!=color[ti][tj+1]:
            if used[ti][tj+1]==0:
              used[ti][tj+1]=1
              q.append([ti,tj+1])
    ans+=bc*wc
print(ans)

Solution (Python):
class UF():
  def __init__(self, N):
    self._parent=[n for n in range(0, N)]
    self._size=[1] * N

  def find_root(self, 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):
    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._size[gy]+=self._size[gx]
    else:
      self._parent[gy]=gx
      self._size[gx]+=self._size[gy]

  def size(self, x):
    return self._size[self.find_root(x)]

  def samegroup(self, x, y):
    return self.find_root(x)==self.find_root(y)

  def groupnum(self):
    N=len(self._parent)
    ans=0
    for i in range(N):
      if self.find_root(i)==i:
        ans+=1
    return ans

h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
UF=UF(h*w)
for i in range(h):
  for j in range(w):
    if i!=0:
      if s[i][j]!=s[i-1][j]:UF.unite(i*w+j,(i-1)*w+j)
    if i!=h-1:
      if s[i][j]!=s[i+1][j]:UF.unite(i*w+j,(i+1)*w+j)
    if j!=0:
      if s[i][j]!=s[i][j-1]:UF.unite(i*w+j,i*w+(j-1))
    if j!=w-1:
      if s[i][j]!=s[i][j+1]:UF.unite(i*w+j,i*w+(j+1))
listB=[0 for i in range(h*w)]
listW=[0 for i in range(h*w)]
for i in range(h):
  for j in range(w):
    if s[i][j]=='
      listB[UF.find_root(i*w+j)]+=1
    else:
      listW[UF.find_root(i*w+j)]+=1
ct=0
for i in range(h*w):
  ct+=listB[i]*listW[i]
print(ct)

Solution (Python):
class UF():
  def __init__(self, N):
    self._parent=[n for n in range(0, N)]
    self._size=[1] * N

  def find_root(self, 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):
    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._size[gy]+=self._size[gx]
    else:
      self._parent[gy]=gx
      self._size[gx]+=self._size[gy]

  def size(self, x):
    return self._size[self.find_root(x)]

  def samegroup(self, x, y):
    return self.find_root(x)==self.find_root(y)

  def groupnum(self):
    N=len(self._parent)
    ans=0
    for i in range(N):
      if self.find_root(i)==i:
        ans+=1
    return ans

from collections import defaultdict
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
UF=UF(h*w)
for i in range(h):
  for j in range(w):
    if i!=0:
      if s[i][j]!=s[i-1][j]:UF.unite(i*w+j,(i-1)*w+j)
    if i!=h-1:
      if s[i][j]!=s[i+1][j]:UF.unite(i*w+j,(i+1)*w+j)
    if j!=0:
      if s[i][j]!=s[i][j-1]:UF.unite(i*w+j,i*w+(j-1))
    if j!=w-1:
      if s[i][j]!=s[i][j+1]:UF.unite(i*w+j,i*w+(j+1))
listB=[0 for i in range(h*w)]
listW=[0 for i in range(h*w)]
for i in range(h):
  for j in range(w):
    if s[i][j]=='
      listB[UF.find_root(i*w+j)]+=1
    else:
      listW[UF.find_root(i*w+j)]+=1
ct=0
for i in range(h*w):
  ct+=listB[i]*listW[i]
print(ct)

Solution (Python):
h,w=map(int,input().split())
P=[]
for i in range(h):
  C=[str(_) for _ in input()]
  P+=C
par=[[-1,0,0] for _ in range(h*w)]
def find(x):
  if par[x][0]<0:
    return x
  else:
    par[x][0]=find(par[x][0])
    return par[x][0]
def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return False
  else:
    if par[x][0]>par[y][0]:
      x,y=y,x
    par[x][0]+=par[y][0]
    par[y][0]=x
    return True
def same(x,y):
  return find(x)==find(y)
def size(x):
  return -par[find(x)][0]
for i in range(h*w):
  if P[i]=="
    par[i][1]+=1
    if (i+1)%w!=0 and P[i+1]==".":
      unite(i,i+1)
    if (i+w)<(h*w) and P[i+w]==".":
      unite(i,i+w)
  else:
    par[i][2]+=1
    if (i+1)%w!=0 and P[i+1]=="
      unite(i,i+1)
    if (i+w)<(h*w) and P[i+w]=="
      unite(i,i+w)
ans=0
for p,x,y in par:
  if p>=0:
    par[find(p)][1]+=x
    par[find(p)][2]+=y
for p,x,y in par:
  if p<-1:
    ans+=x*y
print(ans)

Solution (Python):
h,w = map(int, input().split())
m = [input() for _ in range(h)]
seen = [[0]*w for _ in range(h)]
dxy =[(1,0),(0,1),(-1,0),(0,-1)]
cnt = 0
for i in range(h):
  for j in range(w):
    if not seen[i][j]:
      bcnt,wcnt = 0,0
      q = [(i,j)]
      while q:
        y,x = q.pop()
        if seen[y][x]:
          continue
        if m[y][x] == "
          bcnt += 1
        else:
          wcnt += 1
        seen[y][x] = 1
        for dx,dy in dxy:
          if 0<=x+dx<w and 0<=y+dy<h and not seen[y+dy][x+dx] and m[y+dy][x+dx] != m[y][x]:
            q.append((y+dy,x+dx))
      cnt += bcnt*wcnt
print(cnt)

Solution (Python):
class UnionFind():
    
    
    def __init__(self, n):
        self.n = n
        
        
        self.root = [-1]*(n+1)
        
        self.rnk = [0]*(n+1)

    
    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 isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]



H,W=map(int,input().split())
tree=UnionFind(H*W)
s=[input() for i in range(H)]

for i in range(H):
    for j in range(W):
        x=i*W+j+1
        if i>0 and s[i][j]!=s[i-1][j]: tree.Unite(x,x-W)
        if i<H-1 and s[i][j]!=s[i+1][j]: tree.Unite(x,x+W)
        if j>0 and s[i][j]!=s[i][j-1]: tree.Unite(x,x-1)
        if j<W-1 and s[i][j]!=s[i][j+1]: tree.Unite(x,x+1)

dicw={}


for i in range(H):
    for j in range(W):
        p=tree.Find_Root(i*W+j+1)
        if not p in dicw:
            dicw[p]=0
        if s[i][j]==".":
            dicw[p]+=1

ans=0
for i in dicw:
    n=tree.Count(i)

    ans+=dicw[i]*(n-dicw[i])
print(ans)

Solution (Python):
import sys

from collections import deque, defaultdict, Counter; from heapq import heappush, heappop



sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]
def mi(n): return [wi() for _ in range(n)]
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]


if __name__ == '__main__':
    h, w = wi()
    s = hs(h)
    flagli = [[0] * w for i in range(h)]
    stack = deque()
    black = 0
    white = 0
    for i in range(h):
        for j in range(w):
            if flagli[i][j] == 0:
                flagli[i][j] = 1
                white = 1 if s[i][j] == "." else 0
                black = 1 if s[i][j] == "
                stack.append([i, j])
                while stack != deque():
                    p, q = stack.pop()
                    k = 0 if s[p][q] == "." else 1
                    for dx, dy in dd:
                        nx = q + dx;
                        ny = p + dy
                        if 0 <= nx < w and 0 <= ny < h:
                            if flagli[ny][nx] == 0:
                                if k == 0 and s[ny][nx] == "
                                    flagli[ny][nx] = 1
                                    stack.append([ny, nx])
                                    black += 1
                                elif k == 1 and s[ny][nx] == ".":
                                    flagli[ny][nx] = 1
                                    stack.append([ny, nx])
                                    white += 1
                ans += black * white
                black = 0
                white = 0
    print(ans)

Solution (Python):
import sys

from collections import deque, defaultdict, Counter; from heapq import heappush, heappop



sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]
def mi(n): return [wi() for _ in range(n)]
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]



h, w = wi()
s = hs(h)
flagli = [[0] * w for i in range(h)]
stack = deque()
black = 0
white = 0
for i in range(h):
    for j in range(w):
        if flagli[i][j] == 0:
            flagli[i][j] = 1
            white = 1 if s[i][j] == "." else 0
            black = 1 if s[i][j] == "
            stack.append([i, j])
            while stack != deque():
                p, q = stack.pop()
                k = 0 if s[p][q] == "." else 1
                for dx, dy in dd:
                    nx = q + dx;
                    ny = p + dy
                    if 0 <= nx < w and 0 <= ny < h:
                        if flagli[ny][nx] == 0:
                            if k == 0 and s[ny][nx] == "
                                flagli[ny][nx] = 1
                                stack.append([ny, nx])
                                black += 1
                            elif k == 1 and s[ny][nx] == ".":
                                flagli[ny][nx] = 1
                                stack.append([ny, nx])
                                white += 1
            ans += black * white
            black = 0
            white = 0
print(ans)

Solution (Python):
import sys

from collections import deque, defaultdict, Counter; from heapq import heappush, heappop



sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]
def mi(n): return [wi() for _ in range(n)]
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]


if __name__ == '__main__':
    h, w = wi()
    s = hs(h)
    flagli = [[0] * w for i in range(h)]
    stack = deque()
    black = 0
    white = 0
    for i in range(h):
        for j in range(w):
            if flagli[i][j] == 0:
                flagli[i][j] = 1
                white = 1 if s[i][j] == "." else 0
                black = 1 if s[i][j] == "
                stack.append([i, j])
                while stack != deque():
                    p, q = stack.pop()
                    k = 0 if s[p][q] == "." else 1
                    for dx, dy in dd:
                        nx = q + dx;
                        ny = p + dy
                        if 0 <= nx < w and 0 <= ny < h:
                            if flagli[ny][nx] == 0:
                                if k == 0 and s[ny][nx] == "
                                    flagli[ny][nx] = 1
                                    stack.append([ny, nx])
                                    black += 1
                                elif k == 1 and s[ny][nx] == ".":
                                    flagli[ny][nx] = 1
                                    stack.append([ny, nx])
                                    white += 1
                ans += black * white
                black = 0
                white = 0
print(ans)

Solution (Python):
from itertools import*
import math
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

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

dirc = [(0,1),(1,0),(0,-1),(-1,0)]
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 dirc:
            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

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

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


def dfs(startx: int, starty: int) -> set:
    dxdy = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    stack = [(startx, starty, s[starty][startx] == '
    reached = set()
    reached.add((startx, starty))
    b, w = 0, 0
    while stack:
        d = stack.pop()
        if d[2]:
            b += 1
        else:
            w += 1
        for a in dxdy:
            x = d[0] + a[0]
            y = d[1] + a[1]
            if (x, y) not in reached and 0 <= x < W and 0 <= y < H and d[2] ^ (s[y][x] == '
                stack.append((x, y, s[y][x] == '
                reached.add((x, y))
    return (reached, b, w)


reach = set()
ans = 0
for i in range(H):
    for j in range(W):
        if (j, i) not in reach:
            res = dfs(j, i)
            reach |= res[0]
            ans += res[1] * res[2]
print(ans)