Problem:
 Score : 300 points    Problem Statement There is a grid with H rows and W columns, where each square is painted black or white.  You are given H strings S_1, S_2, ..., S_H , each of length W .
If the square at the i -th row from the top and the j -th column from the left is painted black, the j -th character in the string S_i is # ; if that square is painted white, the j -th character in the string S_i is . .  Find the number of pairs of a black square c_1 and a white square c_2 that satisfy the following condition:   There is a path from the square c_1 to the square c_2 where we repeatedly move to a vertically or horizontally adjacent square through an alternating sequence of black and white squares: black, white, black, white...       Constraints  1 \leq H, W \leq 400  |S_i| = W ( 1 \leq i \leq H )  For each i ( 1 \leq i \leq H ), the string S_i consists of characters # and . .         Input Input is given from Standard Input in the following format:  H  W  S_1  S_2  :  S_H       Output Print the answer.        Sample Input 1 3 3
.#.
..#
#..      Sample Output 1 10  Some of the pairs satisfying the condition are ((1, 2), (3, 3)) and ((3, 1), (3, 2)) , where (i, j) denotes the square at the i -th row from the top and the j -th column from the left.       Sample Input 2 2 4
....
....      Sample Output 2 0       Sample Input 3 4 3
###
###
...
###      Sample Output 3 6

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
dx = (0, 0, 1, -1)
dy = (1, -1, 0, 0)
seen = [[False] * w for _ in range(h)]

numb = 0
numw = 0


def dfs(x, y):
    global numb, numw
    seen[x][y] = True
    if s[x][y] == '
        numb += 1
    else:
        numw += 1
    for di in range(4):
        nx = x + dx[di]
        ny = y + dy[di]
        if (nx < 0 or nx >= h or ny < 0 or ny >= w):
            continue
        if s[x][y] == s[nx][ny]:
            continue
        if seen[nx][ny]:
            continue
        dfs(nx, ny)


ans = 0
for x in range(h):
    for y in range(w):
        if seen[x][y]:
            continue
        if s[x][y] == '.':
            continue
        numb = 0
        numw = 0
        dfs(x, y)
        ans += numb * numw
print(ans)

Solution (Python):
from collections import deque

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

visited = [[False]*W for _ in range(H)]
ans = 0

for row in range(H):
    for col in range(W):
        if not visited[row][col]:
            visited[row][col] = True
            d = deque([[row, col]])
            if s[row][col] == ".":
                passed_black, passed_white = 0, 1
            else:
                passed_black, passed_white = 1, 0

            while d:
                now_row, now_col = d.popleft()
                visited[now_row][now_col] = True
                for new_row, new_col in [[now_row+1, now_col], [now_row-1, now_col], [now_row, now_col+1], [now_row, now_col-1]]:
                    if 0 <= new_row <= H-1 and 0 <= new_col <= W-1 and s[now_row][now_col] != s[new_row][new_col] and not visited[new_row][new_col]:
                        d.append([new_row, new_col])
                        visited[new_row][new_col] = True
                        if s[new_row][new_col] == ".":
                            passed_white += 1
                        else:
                            passed_black += 1

            ans += passed_black * passed_white

print(ans)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7






H, W = getNM()
maze = []
for i in range(H):
    m = list(input())
    maze.append(m)

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

memo = [[-1] * W for i in range(H)]

def counter(sx, sy):
    black_cnt = 0
    white_cnt = 0

    memo[sy][sx] = 1
    if maze[sy][sx] == "
        black_cnt += 1
    else:
        white_cnt += 1

    pos = deque([[sx, sy]])

    while len(pos) > 0:
        x, y = pos.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < W and 0 <= ny < H and maze[ny][nx] != maze[y][x] and memo[ny][nx] == -1:
                memo[ny][nx] = 1
                pos.append([nx, ny])
                if maze[ny][nx] == "
                    black_cnt += 1
                else:
                    white_cnt += 1
    return black_cnt * white_cnt

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

Solution (Python):
from collections import deque

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

d_i = [-1, 0, 1, 0]
d_j = [0, -1, 0, 1]

ans = 0
visited = [[False]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if visited[i][j]:
            continue
        b = 0
        wh = 0
        q = deque()
        q.append((i,j))
        visited[i][j] = True
        while len(q) > 0:
            c_h, c_w = q.pop()
            if s[c_h][c_w] == '
                b += 1
            else:
                wh += 1
            for dir in range(4):
                n_h = c_h+d_i[dir]
                n_w = c_w+d_j[dir]
                if n_h < 0 or h-1 < n_h or n_w < 0 or w-1 < n_w:
                    continue
                if visited[n_h][n_w]:
                    continue
                if s[c_h][c_w] == s[n_h][n_w]:
                    continue
                q.append((n_h, n_w))
                visited[n_h][n_w] = True
        ans += b*wh
print(ans)

Solution (Python):
from collections import deque
h, w = map(int, input().split())
s = []
for _ in range(h):
    s.append(input())
dxdy = [(-1,0), (0,-1), (0,1), (1,0)]
seen = [[False]*w for _ in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if seen[i][j]:
            continue
        q = deque([(j, i)])
        cnt = [0, 0]
        cnt[int(s[i][j]=='
        seen[i][j] = True
        while q:
            x, y = q.popleft()
            for dx, dy in dxdy:
                if not (0<=x+dx<w and 0<=y+dy<h):
                    continue
                if seen[y+dy][x+dx] or s[y][x]==s[y+dy][x+dx]:
                    continue
                cnt[int(s[y+dy][x+dx]=='
                seen[y+dy][x+dx] = True
                q.append((x+dx, y+dy))
        ans += cnt[0]*cnt[1]
print(ans)

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

h,w = map(int,input().split())
F = []
for i in range(h):
  F.append(list(input()))
  
V = [[False]*w for _ in range(h)]

def dfs(y,x,c):      
  V[y][x] = True
  black = 0
  white = 0
  if c =='
    black+=1
  else:
    white+=1
  for dy,dx in [(-1,0),(0,1),(1,0),(0,-1)]:
    ny = y + dy
    nx = x + dx
    if 0<=ny<h and 0<=nx<w:      
      if F[ny][nx]!=c and V[ny][nx] == False:
        nc = '
        if c =='
          nc = '.'
        bn,wn = dfs(ny,nx,nc)
        black += bn
        white += wn  
  return black,white
        
ans = 0
for i in range(h):
  for j in range(w):
    if F[i][j] == '
      black,white = dfs(i,j,'
      ans += black*white
      
print(ans)

Solution (Python):
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)
MOD = 10 ** 9 + 7
INF = float("inf")


def main():
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    seen = [[False] * W for _ in range(H)]
    black = [0]
    white = [0]

    def dfs(x, y):
        seen[x][y] = True
        if S[x][y] == "
            black[-1] += 1
        else:
            white[-1] += 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if not (0 <= nx < H and 0 <= ny < W):
                continue
            if S[x][y] == S[nx][ny]:
                continue
            if seen[nx][ny]:
                continue
            dfs(nx, ny)

    answer = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == ".":
                continue
            if seen[h][w]:
                continue
            black.append(0)
            white.append(0)
            dfs(h, w)

    for i in range(len(black)):
        answer += black[i] * white[i]
    print(answer)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

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


def dfs(maze, H, W, sh, sw, gh, gw):
    visited = [[False] * W for _ in range(H)]
    visited[sh][sw] = True
    q = deque([(sh, sw)])
    while q:
        h, w = q.pop()
        if h == gh and w == gw:
            return True
        for dh, dw in [(1, 0), (-1, 0), (0, -1), (0, 1)]:
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W:
                if not visited[nh][nw]:
                    if maze[nh][nw] == ".":
                        visited[nh][nw] = True
                        q.append((nh, nw))
    return False


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

    def dfs(x, y, black, white):
        q = deque([(x, y)])
        while q:
            X, Y = q.pop()
            if seen[X][Y]:
                continue
            seen[X][Y] = True
            if S[X][Y] == "
                black += 1
            else:
                white += 1
            for i in range(4):
                nx = X + dx[i]
                ny = Y + dy[i]
                if not (0 <= nx < H and 0 <= ny < W):
                    continue
                if S[X][Y] == S[nx][ny]:
                    continue
                if seen[nx][ny]:
                    continue
                q.append((nx, ny))
        return black, white

    answer = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == ".":
                continue
            if seen[h][w]:
                continue
            black = 0
            white = 0
            black, white = dfs(h, w, black, white)
            answer += black * white

    print(answer)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

    def dfs(sh, sw):
        q = deque([(sh, sw)])
        seen[sh][sw] = True
        black = 0
        white = 0
        if S[sh][sw] == "
            black += 1
        else:
            white += 1

        while q:
            h, w = q.popleft()

            for dh, dw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                nh = h + dh
                nw = w + dw

                if 0 <= nh < H and 0 <= nw < W:
                    if seen[nh][nw]:
                        continue
                    if S[h][w] == S[nh][nw]:
                        continue

                    seen[nh][nw] = True
                    q.append((nh, nw))
                    if S[nh][nw] == "
                        black += 1
                    else:
                        white += 1

        return black * white

    ans = 0
    for h in range(H):
        for w in range(W):
            if seen[h][w]:
                continue
            ans += dfs(h, w)

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]
dij=[(1,0),(0,1),(-1,0),(0,-1)]

def main():
    h,w=MI()
    ss=[SI() for _ in range(h)]

    def dfs(i,j):
        stack=[(i,j)]
        bc,wc=0,0
        while stack:
            i,j=stack.pop()
            if ss[i][j]=="
            else:wc+=1
            for di,dj in dij:
                ni,nj=i+di,j+dj
                if ni<0 or nj<0 or ni>=h or nj>=w:continue
                if fin[ni][nj] or ss[i][j]==ss[ni][nj]:continue
                fin[ni][nj]=True
                stack.append((ni,nj))
        return bc,wc

    ans=0
    fin=[[False]*w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if fin[i][j]:continue
            fin[i][j]=True
            bc,wc=dfs(i,j)
            ans+=bc*wc
    print(ans)

main()

Solution (Python):
from collections import deque

def main():
    H, W = map(int, input().split())
    S = list(list(input()) for _ in range(H))
    visited = [[False] * W for _ in range(H)]
    blacks = []
    ans = 0
    dh = [0,1,0,-1]
    dw = [1,0,-1,0]
    for h in range(H):
        for w in range(W):
            if S[h][w] == '
                blacks.append((h,w))

    for h, w in blacks:
        if not visited[h][w]:
            Q = deque([(h,w)])
            white = 0
            black = 1
            visited[h][w] = True
            while Q:
                i, j = Q.popleft()
                now = S[i][j]

                for n in range(4):
                    nh = i + dh[n]
                    nw = j + dw[n]

                    if 0 <= nh < H and 0 <= nw < W:
                        if not visited[nh][nw]:
                            if now != S[nh][nw]:
                                visited[nh][nw] = True
                                Q.append((nh,nw))
                                if S[nh][nw] == '.':
                                    white += 1
                                else:
                                    black += 1
            ans += white * black

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

def main():
    H, W = map(int, input().split())
    S = list(list(input()) for _ in range(H))
    visited = [[False] * W for _ in range(H)]
    blacks = []
    ans = 0
    dh = [0,1,0,-1]
    dw = [1,0,-1,0]
    for h in range(H):
        for w in range(W):
            if S[h][w] == '
                blacks.append((h,w))

    for h, w in blacks:
        if not visited[h][w]:
            Q = deque([(h,w)])
            white = 0
            black = 1
            visited[h][w] = True
            while Q:
                i, j = Q.pop()
                now = S[i][j]

                for n in range(4):
                    nh = i + dh[n]
                    nw = j + dw[n]

                    if 0 <= nh < H and 0 <= nw < W:
                        if not visited[nh][nw]:
                            if now != S[nh][nw]:
                                visited[nh][nw] = True
                                Q.append((nh,nw))
                                if S[nh][nw] == '.':
                                    white += 1
                                else:
                                    black += 1
            ans += white * black

    print(ans)


if __name__ == "__main__":
    main()

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

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

grid = [readline().rstrip() for i in range(H)]

visited = set()
ans = 0
from collections import deque
cases = ((0,1),(0,-1),(1,0),(-1,0))
for i in range(H):
  for j in range(W):
    if (i,j) in visited:
      continue
    if grid[i][j] == ".":
      continue
    q = deque()
    black = 0
    white = 0
    q.append([i,j,1])
    aim = ".
    while q:
      y,x,isblack = q.popleft()
      if (y,x) in visited:
        continue
      if aim[isblack] != grid[y][x]:
        continue
      visited.add((y,x))
      if isblack:
        black += 1
      else:
        white += 1
      isblack ^= 1
      for c in cases:
        if 0 <= y + c[0] < H and 0 <= x + c[1] < W:
          q.append([y + c[0],x + c[1],isblack])
    ans += black * white
print(ans)

Solution (Python):
from collections import deque
H,W = map(int, input().split())
S = [input() for _ in range(H)]

used = [[0]*W for _ in range(H)]
q = deque()
ans = 0
for i in range(H):
    for j in range(W):
        if used[i][j] == 1:
            continue
        if S[i][j] == ".":
            continue
        dic = {"
        q.append((i, j, "
        used[i][j] = 1
        while q:
            temp = q.popleft()
            k = temp[0]
            l = temp[1]
            f = temp[2]
            if f == "
                f = "."
            else:
                f = "
            if k > 0 and S[k-1][l] == f and used[k-1][l] == 0:
                used[k-1][l] = 1
                dic[f] += 1
                q.append((k-1, l, f))
            if k < H-1 and S[k+1][l] == f and used[k+1][l] == 0:
                used[k+1][l] = 1
                dic[f] += 1
                q.append((k+1, l, f))
            if l > 0 and S[k][l-1] == f and used[k][l-1] == 0:
                used[k][l-1] = 1
                dic[f] += 1
                q.append((k, l-1, f))
            if l < W-1 and S[k][l+1] == f and used[k][l+1] == 0:
                used[k][l+1] = 1
                dic[f] += 1
                q.append((k, l+1, f))
        ans += dic["

print(ans)

Solution (Python):

"""
s(
4近傍で
(但し、s,gが同一でそのような道が複数あっても、1つしかカウントしない)
各
ちなみに、その時に
を持つので、端折って良い。
"""
import sys
from collections import deque
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
H,W = map(int,readline().split())
maze = []
for _ in range(H):
    maze += [list(readline().rstrip().decode())]
used = [[0]*W for _ in range(H)]
def dfs(y,x):
    white = 0
    black = 1
    deq = deque([(y,x)])
    used[y][x] = 1
    while deq:
        fr = deq.pop()
        for go in [(0,1),(1,0),(0,-1),(-1,0)]:
            if 0 <= fr[0]+go[0] < H and 0 <= fr[1]+go[1] < W:
                if not used[fr[0]+go[0]][fr[1]+go[1]]:
                    if maze[fr[0]][fr[1]] != maze[fr[0]+go[0]][fr[1]+go[1]]:
                        deq.append((fr[0]+go[0],fr[1]+go[1]))
                        used[fr[0]+go[0]][fr[1]+go[1]] = 1
                        if maze[fr[0]+go[0]][fr[1]+go[1]] == ".":
                            white += 1
                        else:
                            black += 1
    
    return white * black
ans = 0
for i in range(H):
    for j in range(W):
        if not used[i][j] and maze[i][j] == "
            ans += dfs(i,j)

print(ans)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

from collections import defaultdict
rows, cols = map(int, input().split())
n = rows*cols
ns = defaultdict(set)
ss = [None] * rows
color = [None] * n
for i in range(rows):
    s = input()
    ss[i] = s
    for j,c in enumerate(s):
        u = i*cols+j
        color[u] = c
        if i>0:
            if c!=ss[i-1][j]:
                v = u - cols
                ns[u].add(v)
                ns[v].add(u)
        if j>0:
            if c!=s[j-1]:
                v = u - 1
                ns[u].add(v)
                ns[v].add(u)
seen = [False] * n
ans = 0
for u in range(n):
    if seen[u]:
        continue
    q = [u]
    s = set([u])
    while q:
        u = q.pop()
        for v in ns[u]:
            if seen[v]:
                continue
            seen[v] = True
            s.add(v)
            q.append(v)
    ans += sum(color[item]=="
print(ans)

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

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

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

def dfs(x,y):
    global cc
    global was
    was[x][y]=1
    if S[x][y]=="
        cc[1]+=1
    else:
        cc[0]+=1
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if nx>=0 and ny>=0 and nx<H and ny<W and S[nx][ny]!=S[x][y] and not was[nx][ny]:
            dfs(nx,ny)

for i in range(H):
    for j in range(W):
        if not was[i][j]:
            cc=[0]*2
            dfs(i,j)
            ans+= cc[1]*cc[0]

print(ans)

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

class Unionfind:
    def __init__(self, n):
        self.par = [-1]*n
        self.rank = [1]*n
    
    def root(self, x):
        r = x
        
        while not self.par[r]<0:
            r = self.par[r]
        
        t = x
        
        while t!=r:
            tmp = t
            t = self.par[t]
            self.par[tmp] = r
        
        return r
    
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        
        if rx==ry:
            return
        
        if self.rank[rx]<=self.rank[ry]:
            self.par[ry] += self.par[rx]
            self.par[rx] = ry
            
            if self.rank[rx]==self.rank[ry]:
                self.rank[ry] += 1
        else:
            self.par[rx] += self.par[ry]
            self.par[ry] = rx
    
    def is_same(self, x, y):
        return self.root(x)==self.root(y)
    
    def count(self, x):
        return -self.par[self.root(x)]

H, W = map(int, input().split())
S = [input()[:-1] for _ in range(H)]
uf = Unionfind(H*W)

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

wcnt = defaultdict(int)
bcnt = defaultdict(int)

for i in range(H):
    for j in range(W):
        r = uf.root(W*i+j)
        
        if S[i][j]=='
            wcnt[r] += 1
        else:
            bcnt[r] += 1

ans = 0

for k in wcnt:
    ans += wcnt[k]*bcnt[k]

print(ans)

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue
from decimal import *


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)

visited = None
S = None
H, W = None, None


def bfs(x, y):
    global visited
    if visited[y][x]:
        return 0
    q = []
    q.append((x, y))
    black = 0
    white = 0
    while q != []:
        x, y = q.pop()
        DIR = [(-1, 0), (1, 0), (0, 1), (0, -1)]
        for d in DIR:
            nx, ny = x + d[0], y + d[1]
            if 0 <= nx < W and 0 <= ny < H and S[y][x] != S[ny][nx] and not visited[ny][nx]:
                visited[ny][nx] = True
                if S[ny][nx] == '.':
                    white += 1
                else:
                    black += 1
                q.append((nx, ny))
    return black * white


def solve():
    global H, W
    global S
    global visited
    H, W = Scanner.map_int()
    S = Scanner.string_list(H)
    visited = [[False for _ in range(W)] for _ in range(H)]
    ans = 0
    for x in range(W):
        for y in range(H):
            ans += bfs(x, y)
    print(ans)


def main():
    
    
    solve()


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

H, W = map(int, 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 = map(int, input().split())
s_list = []
for _ in range(H):
    s = input()
    s_list.append(s)
ans = 0
visited = set({})
for h in range(H):
    for w in range(W):
        if s_list[h][w] == '.':
            if str(h) + '_' + str(w) not in visited:
                d = deque()
                d.append([h, w])
                plus = 1
                minus = 0
                while d:
                    i, j = d.pop()
                    visited.add(str(i) + '_' + str(j))
                    for ii, jj in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                        if (0 <= (i + ii) < H) & (0 <= (j + jj) < W):
                            if str(i + ii) + '_' + str(j + jj) not in visited:
                                if s_list[i][j] != s_list[i + ii][j + jj]:
                                    d.append([i + ii, j + jj])
                                    visited.add(str(i + ii) + '_' + str(j + jj))
                                    if s_list[i + ii][j + jj] == '.':
                                        plus += 1
                                    else:
                                        minus += 1                                
                ans += plus * minus
print(ans)

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

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

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

Solution (Python):
from collections import deque
h,w=map(int,input().split())
field=[["*" for i in range(w+2)]]+[["*"]+list(input())+["*"] for i in range(h)]+[["*"]*(w+2)]
dx=[-1,0,1,0]
dy=[0,-1,0,1]
visited=[[False for i in range(w+2)] for j in range(h+2)]
s={"
ans=0
def bfs(a,b):
    if visited[a][b] or field[a][b]=="*":return 0
    D=deque([(a,b)])
    visited[a][b]=True
    cnt=[0,0]
    while D:
        pos=D.popleft()
        cnt[s[field[pos[0]][pos[1]]]]+=1
        for i,j in zip(dx,dy):
            if field[pos[0]+i][pos[1]+j] == "*" or visited[pos[0]+i][pos[1]+j] or field[pos[0]+i][pos[1]+j]==field[pos[0]][pos[1]]:
                continue
            visited[pos[0]+i][pos[1]+j]=True
            D.append((pos[0]+i,pos[1]+j))
    return cnt[0]*cnt[1]
for i in range(h+2):
    for j in range(w+2):
        ans += bfs(i,j)
print(ans)

Solution (Python):
h, w = map(int, input().split())
s = [input() for _i in range(h)]
visit = [[-1 for _i in range(w)] for _j in range(h)]
r = 0
from collections import deque
for i in range(h):
    for j in range(w):
        if (s[i][j]=="
            q = deque([[i, j]])
            black = 1
            white = 0
            visit[i][j] = 1
            while q:
                x, y = q.popleft()
                for n, m in [[1,0], [0, 1], [-1,0], [0,-1]]:
                    if (0<=x+n) and (0<=y+m) and (x+n<h) and (y+m<w):
                        if (visit[x+n][y+m]<0) and (s[x][y]!=s[x+n][y+m]):
                            visit[x+n][y+m]=1
                            if s[x][y] == "
                                white += 1
                            else:
                                black += 1
                            q.append([x+n, y+m])
            r += black*white

print(r)

Solution (Python):
h, w = map(int, input().split())
s = [input() for _i in range(h)]
visit = [[-1 for _i in range(w)] for _j in range(h)]
r = 0
from collections import deque
for i in range(h):
    for j in range(w):
        if (s[i][j]=="
            q = deque([[i, j]])
            black = 1
            white = 0
            visit[i][j] = 1
            while q:
                x, y = q.popleft()
                for n, m in [[1,0], [0, 1], [-1,0], [0,-1]]:
                    if (0<=x+n) and (0<=y+m) and (x+n<h) and (y+m<w):
                        if (visit[x+n][y+m]<0) and (s[x][y]!=s[x+n][y+m]):
                            visit[x+n][y+m]=1
                            if s[x][y] == "
                                white += 1
                            else:
                                black += 1
                            q.append([x+n, y+m])
            r += black*white

print(r)