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):
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())
g=[list(input()) for _ in range(h)]
uf=UnionFind(h*w)
dyx=[(1,0),(-1,0),(0,1),(0,-1)]
for i in range(h):
    for j in range(w):
        if g[i][j]==".":
            continue
        p=i*w+j
        for dy,dx in dyx:
            y=i+dy
            x=j+dx
            if 0<=y<h and 0<=x<w:
                if g[y][x]==".":
                    np=y*w+x
                    uf.Unite(p,np)

rt=[0]*(h*w)
for i in range(h*w):
    rt[i]=uf.Find_Root(i)

m=min(rt)
rt=list(map(lambda x:x-m, rt))
m=max(rt)
a=[[0,0] for _ in range(m+1)]
for i in range(h*w):
    y=i//w
    x=i%w
    if g[y][x]=="
        a[rt[i]][0]+=1
    else:
        a[rt[i]][1]+=1
ans=0
for i,j in a:
    ans+=i*j

print(ans)

Solution (Python):
import itertools

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

diffs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
t = [[0] * w for _ in range(h)]
group = 1
for i, j in itertools.product(range(h), range(w)):
    if t[i][j] != 0:
        continue

    stack = [(i, j)]
    while stack:
        x, y = stack.pop()
        t[x][y] = group
        for dx, dy in diffs:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < h and 0 <= ny < w and t[nx][ny] == 0 and s[x][y] != s[nx][ny]:
                stack.append((nx, ny))
    group += 1

d = [[0] * 2 for _ in range(group)]
for i, j in itertools.product(range(h), range(w)):
    d[t[i][j]][0 if s[i][j] == '.' else 1] += 1

ans = sum(d[i][0] * d[i][1] for i in range(len(d)))
print(ans)

Solution (Python):
def main():

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

    ans = 0
    visited = set()
    for i in range(H):
        for j in range(W):
            if (i, j) not in visited:
                visited.add((i, j))
                b, w = 0, 0
                if A[i][j] == "
                    b += 1
                    c = "."
                else:
                    w += 1
                    c = "
                cur = [[i, j]]
                while cur:
                    temp = []
                    for k1, l1 in cur:
                        for dk, dl in [[1,0],[-1,0],[0,1],[0,-1]]:
                            k, l = k1+dk, l1+dl
                            if 0<=k<H and 0<=l<W and (k,l) not in visited and A[k][l] == c:
                                visited.add((k,l))
                                temp.append([k, l])

                    if c == "
                        b += len(temp)
                        c = "."
                    else:
                        w += len(temp)
                        c = "
                    cur = temp
                ans += b*w
    return ans

if __name__ == '__main__':
    print(main())

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
inf=float("inf")
h,w=map(int,input().split())
s=[input() for i in range(h)]
class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.weight = [0] * (n+1)


    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

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

    def diff(self, x, y):
        return self.weight[x] - self.weight[y]
uf = WeightedUnionFind(h*w)
for i in range(h):
    for j in range(w):
        if (i+1)+1<=h and s[i][j]!=s[i+1][j]:
            uf.union(i*w+j+1,(i+1)*w+j+1,0)
        if (j+1)+1<=w and s[i][j]!=s[i][j+1]:
            uf.union(i*w+j+1,i*w+j+2,0)
        if (i+1)-1>=1 and s[i][j]!=s[i-1][j]:
            uf.union(i*w+j+1,(i-1)*w+j+1,0)
        if (j+1)-1>=1 and s[i][j]!=s[i][j-1]:
            uf.union(i*w+j+1,i*w+j,0)
li=[[0,0] for i in range(h*w+1)]
for i in range(h):
    for j in range(w):
        if s[i][j]=="
            li[uf.find(i*w+j+1)][0]+=1
        else:
            li[uf.find(i*w+j+1)][1]+=1

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

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

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

def dfs(th,tw):
    global flag,h,w,s
    flag[th][tw] = True
    tblack = 0
    twhite = 0
    if s[th][tw] == "
        tblack += 1
    else:
        twhite += 1 
    for x,y in ([0,1],[0,-1],[1,0],[-1,0]):
        nth = th + x
        ntw = tw + y
        if nth >= 0 and nth < h and ntw >= 0 and ntw < w:
            if not flag[nth][ntw] and s[th][tw] != s[nth][ntw]:
                ttb,ttw = dfs(nth,ntw)
                tblack += ttb
                twhite += ttw
    return [tblack,twhite]
                
def main():
    global flag,h,w,s
    res = 0
    for i in range(h):
        for j in range(w):
            if not flag[i][j]:
                black,white = dfs(i,j)
                res += black * white 

    return res
print(main())

Solution (Python):
from collections import defaultdict
import sys
sys.setrecursionlimit(1000000)
d=defaultdict(int)
dw=defaultdict(int)
n,m=map(int,input().split())
l=[]
for i in range(n):
  l.append(list(input()))
lb=[[0 for i in range(m)]for j in range(n)]
move=[[1,0],[-1,0],[0,1],[0,-1]]
def dfs(n1,n2,w,n3):
  if lb[n1][n2]!=0:
    return None
  else:
    lb[n1][n2]=n3
    if w==".":
      w1="
    else:
      w1="."
    for j in move:
      dx=j[0]
      dy=j[1]
      x=dx+n1
      y=dy+n2
      if 0>x or x>n-1 or y<0 or y>m-1:
        pass
      else:
        if w1!=l[x][y]:
          pass
        else:
          dfs(x,y,w1,n3)
    return None
dfs(0,0,l[0][0],1)
num=1
for i in range(n):
  for j in range(m):
    dfs(i,j,l[i][j],num)
    num+=1
for i in range(n):
  for j in range(m):
    d[lb[i][j]]+=1
    if l[i][j]=="
      dw[lb[i][j]]+=1
ans=0
for i in d:
  ans+=dw[i]*(d[i]-dw[i])
print(ans)

Solution (Python):
from collections import deque

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

S = []

for i in range(H):

    s = input()

    S.append(s)

lis = [ [True] * W for i in range(H) ]

ans = 0

for h in range(H):

    for w in range(W):

        if not lis[h][w]:
            continue
        
        q = deque([[h,w]])
        lis[h][w] = False

        if S[h][w] == "
            bnum = 1
            wnum = 0
        else:
            bnum = 0
            wnum = 1

        while len(q) > 0:

            now = q.popleft()
            nh = now[0]
            nw = now[1]

            if S[nh][nw] == "

                if nh > 0 and S[nh-1][nw] == "." and lis[nh-1][nw]:

                    wnum += 1
                    lis[nh-1][nw] = False
                    q.append([nh-1,nw])

                if nh < H-1 and S[nh+1][nw] == "." and lis[nh+1][nw]:

                    wnum += 1
                    lis[nh+1][nw] = False
                    q.append([nh+1,nw])

                if nw > 0 and S[nh][nw-1] == "." and lis[nh][nw-1]:

                    wnum += 1
                    lis[nh][nw-1] = False
                    q.append([nh,nw-1])

                if nw < W-1 and S[nh][nw+1] == "." and lis[nh][nw+1]:

                    wnum += 1
                    lis[nh][nw+1] = False
                    q.append([nh,nw+1])

            if S[nh][nw] == ".":

                if nh > 0 and S[nh-1][nw] == "

                    bnum += 1
                    lis[nh-1][nw] = False
                    q.append([nh-1,nw])

                if nh < H-1 and S[nh+1][nw] == "

                    bnum += 1
                    lis[nh+1][nw] = False
                    q.append([nh+1,nw])

                if nw > 0 and S[nh][nw-1] == "

                    bnum += 1
                    lis[nh][nw-1] = False
                    q.append([nh,nw-1])

                if nw < W-1 and S[nh][nw+1] == "

                    bnum += 1
                    lis[nh][nw+1] = False
                    q.append([nh,nw+1])
                    
        ans += wnum * bnum


print (ans)

Solution (Python):
from collections import deque
H,W = map(int,input().split())
S = [input() for i in range(H)]
ans = 0
flag = [[0]*W for i in range(H)]
for i in range(H*W):
    x,y = i%W,i//W
    if flag[y][x] == 1:
        continue
    flag[y][x] = 1
    bw = [0,0]
    bw[[".","
    queue = deque([[x,y]])
    while queue:
        x,y = queue.popleft()
        for a,b in [[-1,0],[1,0],[0,1],[0,-1]]:
            if 0<=x+a<W and 0<=y+b<H and flag[y+b][x+a] == 0 and S[y][x] != S[y+b][x+a]:
                queue.append([x+a,y+b])
                flag[y+b][x+a] = 1
                bw[[".","
    ans += bw[0]*bw[1]
print(ans)

Solution (Python):
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)

from math import factorial
import heapq, bisect
import math
import itertools

import queue
from collections import deque

def check(x, y, now_add, color, high, width):
    global data
    move_dic = [(1, 0), (0, 1)]
    for move_x, move_y in move_dic:
        next_x = x + move_x
        next_y = y + move_y
        if 0 <= next_x < high and 0 <= next_y < width:
            if data[next_x][next_y] == 0:
                continue
            if data[next_x][next_y] != data[x][y]:
                now_add.add((i, j))
                color[data[next_x][next_y]] += 1
                check(next_x, next_y, now_add, color, high, width)


def main():
    high, width = map(int, input().split())
    data = [list(input()) for i in range(high)]

    ans = 0
    move_dic = [[1, 0], [0, 1], [-1, 0], [0, -1]]

    for i in range(high):
        for j in range(width):
            if data[i][j] == 0:
                continue

            all_ele = set()
            now_ele = set()
            next_ele = set()
            count = defaultdict(int)

            now_ele.add((i, j))
            all_ele.add((i, j))
            count[data[i][j]] += 1

            while len(now_ele) > 0:
                for x, y in now_ele:
                    for move_x, move_y in move_dic:
                        next_x = x + move_x
                        next_y = y + move_y
                        if 0 <= next_x < high and 0 <= next_y < width:
                            if data[next_x][next_y] == 0 or (next_x, next_y) in all_ele:
                                continue
                            if data[next_x][next_y] != data[x][y]:
                                next_ele.add((next_x, next_y))
                                all_ele.add((next_x, next_y))
                                count[data[next_x][next_y]] += 1
                now_ele = next_ele
                next_ele = set()

            ans += count['.'] * count['
            for x, y in all_ele:
                data[x][y] = 0

    print(ans)




if __name__ == '__main__':
    main()

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

visited = [[0]*w for i in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        black = 0
        white = 0
        stack = [[i,j]]
        while stack:
            a,b = stack.pop()
            if visited[a][b]!=1:
                visited[a][b]+=1
                if s[a][b]=='
                    black+=1
                else:
                    white+=1
                for x,y in [[1,0],[-1,0],[0,1],[0,-1]]:
                    c = a+y
                    d = b+x
                    if 0<=c<h and 0<=d<w:
                        if s[a][b]!=s[c][d]:
                            stack.append([c,d])
        ans += black*white
print(ans)

Solution (Python):
H,W=map(int,input().split())
S=[[int(c=='
v=[[0]*W for i in range(H)]
r=0
def bfs(p,x,y,c,b):
    while 1:
        c^=1
        q=set()
        for h,w in p:
            v[h][w]=1
            if h>0 and not v[h-1][w] and S[h-1][w]==c:
                q.add((h-1,w))
            if w>0 and not v[h][w-1] and S[h][w-1]==c:
                q.add((h,w-1))
            if h<H-1 and not v[h+1][w] and S[h+1][w]==c:
                q.add((h+1,w))
            if w<W-1 and not v[h][w+1] and S[h][w+1]==c:
                q.add((h,w+1))
        if not q:
            return x*y
        if b:
            x+=len(q)
        else:
            y+=len(q)
        b^=1
        p=q
for h in range(H):
    for w in range(W):
        if v[h][w]==0:
            r+=bfs([(h,w)],1,0,S[h][w],0)
print(r)

Solution (Python):
from collections import Counter

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


 
class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

uf = UnionFind(H*W)

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

for i in range(H*W):
    uf.root(i)

black = Counter()
white = Counter()


for i in range(H):
    for j in range(W):
        k = i*W+j
        if S[i][j] == "
            black[uf.root(k)] += 1
        else:
            white[uf.root(k)] += 1


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

print(ans)

Solution (Python):
from collections import defaultdict

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

es = defaultdict(list)
for i in range(H):
    for j in range(W):
        
        if j != W-1 and S[i][j] != S[i][j+1]:
            es[(i,j)].append((i,j+1))
            es[(i,j+1)].append((i,j))

        
        if i != H-1 and S[i][j] != S[i+1][j]:
            es[(i,j)].append((i+1,j))
            es[(i+1,j)].append((i,j))


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

stack  = es.keys()
for i,j in stack:
    
    if checked[i][j]:
        continue
    
    if S[i][j] == "
        cnt_b = 1
        cnt_w = 0
    else:
        cnt_b = 0
        cnt_w = 1


    checked[i][j] = True
    ns = es[(i,j)]
    
    while ns:
        tmp = []
        for a,b in ns:
            if checked[a][b] == True: continue

            checked[a][b] = True
            if S[a][b] == "
                cnt_b += 1
            else:
                cnt_w += 1

            for c,d in es[(a,b)]:
                if not checked[c][d]:
                    tmp.append((c,d))
        if len(tmp) > 0:
            ns = tmp
        else:
            ns = []            
    ans += cnt_b * cnt_w


print(ans)

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

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

seen = [[False for _ in range(W)] for _ in range(H)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
numb = 0
numw = 0

def dfs(y,x):
  global numb
  global numw
  seen[y][x] = True
  if S[y][x] == '
    numb += 1
  if S[y][x] == '.':
    numw += 1
  for i in range(4):
    if not(0<=y+dy[i]<H) or not(0<=x+dx[i]<W):
      continue
    if seen[y+dy[i]][x+dx[i]]:
      continue
    if S[y][x] == S[y+dy[i]][x+dx[i]]:
      continue
    dfs(y+dy[i],x+dx[i])

ans = 0
for i in range(H):
  for j in range(W):
    numb = 0
    numw = 0
    if S[i][j] == '
      dfs(i,j)
      ans += numb * numw
print(ans)

Solution (Python):
from collections import deque

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

q=deque()
ans=0

def bfs(i,j):
    global ans
    white=0
    black=0
    q.append((i,j))
    while q:
        y,x=q.popleft()
        if s[y][x]=='
            black+=1
        if s[y][x]=='.':
            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 and s[y][x]!=s[ny][nx] and field[ny][nx]==False:
                field[ny][nx]=True
                q.append((ny,nx))
    ans+=(black*white)

field=[[False]*w for j in range(h)]                         
for i in range(h):
    for j in range(w):
        if s[i][j]=='.' and field[i][j]==False:
            field[i][j]=True
            bfs(i,j)

print(ans)

Solution (Python):

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

    ans = 0
    for h in range(H):
        for w in range(W):
            if checked[h][w]:   continue
            q = [(h, w)]
            score = [0, 0]
            checked[h][w] = True
            c = 0
            while q:
                score[c%2] += len(q)
                qq = []
                for ph, pw in q:
                    nexts = []
                    if ph != 0: nexts.append((ph-1, pw))
                    if ph != H-1: nexts.append((ph+1, pw))
                    if pw != 0: nexts.append((ph, pw-1))
                    if pw != W-1: nexts.append((ph, pw+1))
                    for nh, nw in nexts:
                        if state[nh][nw] != state[ph][pw] and not checked[nh][nw]:
                            checked[nh][nw] = True
                            qq.append((nh, nw))
                c += 1
                q = qq
            ans += score[0]*score[1]
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict

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

S = [input() for _ in range(H)]




es = defaultdict(list)

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

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


ans = 0
for i in range(H):
    for j in range(W):
        if checked[i][j] == True:
            continue
        
        cnt_b = 0
        cnt_w = 0

        if S[i][j] == "
            cnt_b += 1
        else:
            cnt_w += 1
        checked[i][j] = True
        stack = es[(i,j)]

        while stack:
            new_stack = []
            for p,q in stack:
                if checked[p][q] == False:
                    checked[p][q] = True
                    if S[p][q] == "
                        cnt_b += 1
                    else:
                        cnt_w += 1

                    new_stack.extend(es[(p,q)])
            if len(new_stack) == 0:
                break
            else:
                stack = new_stack
        
        ans += cnt_b * cnt_w

print(ans)

Solution (Python):
from collections import defaultdict

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

S = [input() for _ in range(H)]




es = defaultdict(list)
for i in range(H):
    for j in range(W):

        
        if i == 0 and H != 1:
            if S[i][j] != S[i+1][j]:
                es[(i,j)].append((i+1,j))
                es[(i+1,j)].append((i,j))
        elif 0 < i < H-1:
                if S[i][j] != S[i+1][j]:
                    es[(i,j)].append((i+1,j))
                    es[(i+1,j)].append((i,j))
                if S[i][j] != S[i-1][j]:
                    es[(i,j)].append((i-1,j))
                    es[(i-1,j)].append((i,j))
        elif i == H-1 and H != 1:
                if S[i][j] != S[i-1][j]:
                    es[(i,j)].append((i-1,j))
                    es[(i-1,j)].append((i,j))

        
        if j == 0 and W != 1:
            if S[i][j] != S[i][j+1]:
                es[(i,j)].append((i,j+1))
                es[(i,j+1)].append((i,j))
        elif 0 < j < W-1:
            if S[i][j] != S[i][j+1]:
                es[(i,j)].append((i,j+1))
                es[(i,j+1)].append((i,j))
                if S[i][j] != S[i][j-1]:
                    es[(i,j)].append((i,j-1))
                    es[(i,j-1)].append((i,j))
        elif j == W-1 and W != 1:
                if S[i][j] != S[i][j-1]:
                    es[(i,j)].append((i,j-1))
                    es[(i,j-1)].append((i,j))

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


ans = 0
for i in range(H):
    for j in range(W):
        if checked[i][j] == True:
            continue
        
        cnt_b = 0
        cnt_w = 0

        if S[i][j] == "
            cnt_b += 1
        else:
            cnt_w += 1
        checked[i][j] = True
        stack = es[(i,j)]

        while stack:
            new_stack = []
            for p,q in stack:
                if checked[p][q] == False:
                    checked[p][q] = True
                    if S[p][q] == "
                        cnt_b += 1
                    else:
                        cnt_w += 1

                    new_stack.extend(es[(p,q)])
            if len(new_stack) == 0:
                break
            else:
                stack = new_stack
        
        ans += cnt_b * cnt_w

print(ans)

Solution (Python):

import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions

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

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

tansaku = [[0]*W for _ in range(H)]
total = 0
for i in range(H):
	for j in range(W):
		if tansaku[i][j] == 0 and G[i][j] == '
			tansaku[i][j] = 1
			black = 1
			white = 0
			que = deque([])
			que.append((i, j))
			delta = ((0, 1), (0, -1), (1, 0), (-1, 0))
			while len(que) > 0:
				loc = que.popleft()

				for d in range(4):
					x = loc[0] + delta[d][0]
					y = loc[1] + delta[d][1]
					if x >= H or y >= W or x < 0 or y < 0:
						continue

					if tansaku[x][y] == 0:
						if G[loc[0]][loc[1]] == '
							white += 1
							tansaku[x][y] = 1
							que.append((x, y))
							
						elif G[loc[0]][loc[1]] == '.' and G[x][y] == '
							black += 1
							tansaku[x][y] = 1
							que.append((x, y))
							
			total += black*white
			
print(total)

Solution (Python):

def dfs(sx: int, sy: int) -> None:
    color, stack = [0] * 2, [(sx, sy, S[sx][sy])]
    S[sx][sy] = 2  
    while stack:
        x, y, col = stack.pop()
        color[col] += 1
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == col ^ 1:
                stack.append((nx, ny, S[nx][ny]))
                S[nx][ny] = 2  
    return color[0] * color[1]


def main():
    
    global H, W, S, dxy
    H, W, *S = open(0).read().split()
    H, W = int(H), int(W)
    S = [[1 if i == "
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    ans = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] != 2:
                ans += dfs(i, j)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

def dfs(sx: int, sy: int) -> None:
    color = [0] * 2
    s_col = S[sx][sy]
    color[s_col] += 1
    S[sx][sy] = 2  
    stack = [(sx, sy, s_col)]
    while stack:
        x, y, col = stack.pop()
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == col ^ 1:
                stack.append((nx, ny, S[nx][ny]))
                color[S[nx][ny]] += 1
                S[nx][ny] = 2
    return color[0] * color[1]


def main():
    
    global H, W, S, dxy, blk, wht
    H, W, *S = open(0).read().split()
    H, W = int(H), int(W)
    S = [[1 if i == "
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    ans = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] != 2:
                ans += dfs(i, j)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

def dfs(sx: int, sy: int) -> None:
    color = [0] * 2
    s_col = S[sx][sy]
    color[s_col] += 1
    S[sx][sy] = 2  
    stack = [(sx, sy, s_col)]
    while stack:
        x, y, col = stack.pop()
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == col ^ 1:
                n_col = S[nx][ny]
                stack.append((nx, ny, n_col))
                color[n_col] += 1
                S[nx][ny] = 2
    return color[0] * color[1]


def main():
    
    global H, W, S, dxy, blk, wht
    H, W, *S = open(0).read().split()
    H, W = int(H), int(W)
    S = [[1 if i == "
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    ans = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] != 2:
                ans += dfs(i, j)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

import sys

sys.setrecursionlimit(10 ** 9)


def dfs(x: int, y: int) -> None:
    global blk, wht
    cur = S[x][y]
    S[x][y] = 2  
    if cur:
        blk += 1
    else:
        wht += 1
    for dx, dy in dxy:
        nx, ny = x + dx, y + dy
        if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == cur ^ 1:
            dfs(nx, ny)


def main():
    
    global H, W, S, dxy, blk, wht
    H, W, *S = open(0).read().split()
    H, W = int(H), int(W)
    S = [[1 if i == "
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    ans = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] != 2:
                blk, wht = 0, 0
                dfs(i, j)
                ans += blk * wht
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

import sys

sys.setrecursionlimit(10 ** 9)


def dfs(x: int, y: int) -> None:
    global blk, wht
    seen[x][y] = 1
    cur = S[x][y]
    if cur:
        blk += 1
    else:
        wht += 1
    for dx, dy in dxy:
        nx, ny = x + dx, y + dy
        if 0 <= nx < H and 0 <= ny < W and S[nx][ny] != cur and not seen[nx][ny]:
            dfs(nx, ny)


def main():
    
    global H, W, S, seen, dxy, blk, wht
    H, W, *S = open(0).read().split()
    H, W = int(H), int(W)
    S = [[1 if i == "
    seen = [[0] * W for _ in range(H)]
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    ans = 0
    for i in range(H):
        for j in range(W):
            if not seen[i][j]:
                blk, wht = 0, 0
                dfs(i, j)
                ans += blk * wht
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

import sys

sys.setrecursionlimit(10 ** 9)


def dfs(x: int, y: int) -> None:
    global blk, wht
    seen[x][y] = 1
    cur = S[x][y]
    if cur == "
        blk += 1
    else:
        wht += 1
    for dx, dy in dxy:
        nx, ny = x + dx, y + dy
        if 0 <= nx < H and 0 <= ny < W and S[nx][ny] != cur and not seen[nx][ny]:
            dfs(nx, ny)


def main():
    
    global H, W, S, seen, dxy, blk, wht
    H, W, *S = open(0).read().split()
    H, W = int(H), int(W)
    seen = [[0] * W for _ in range(H)]
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    ans = 0
    for i in range(H):
        for j in range(W):
            if not seen[i][j]:
                blk, wht = 0, 0
                dfs(i, j)
                ans += blk * wht
    print(ans)


if __name__ == "__main__":
    main()