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



Sample input:
3 3
.#.
..#
#..


Sample output:
10

Submission status: Accepted

Solution code:
import sys,bisect,heapq

mod = 10**9+7

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return(list(sys.stdin.readline())[:-1])

def GCD(a,b):
    while(a%b != 0):
        a,b = b,a%b
    return b

def LCM(a,b):
    return a*b//GCD(a,b)

def main():
    H,W = LI()
    a = [[c=="#" for c in S()] for _ in range(H)]
    b = [[True for _ in range(W)] for _ in range(H)]

    r = 0
    for h in range(H):
        for w in range(W):
            if b[h][w]:
                q = []
                T = 0
                F = 0
                q.append([a[h][w],h,w])
                while(q):
                    flag,h_s,w_s = q.pop()
                    if b[h_s][w_s] and a[h_s][w_s] == flag:
                        if flag:
                            T += 1
                        else:
                            F += 1
                        b[h_s][w_s] = False
                        for i in [[-1,0],[1,0],[0,-1],[0,1]]:
                            if 0<=h_s+i[0]<=H-1 and 0<=w_s+i[1]<=W-1 and b[h_s+i[0]][w_s+i[1]]:
                                q.append([not(flag),h_s+i[0],w_s+i[1]])
                r += T*F
    return r




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

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
S = []
for i in range(H):
  ss = input()
  S.append(ss)
UF = list(range(H*W))
def par(m):
  if UF[m] == m:
    return m
  r = par(UF[m])
  UF[m] = r
  return r
def unite(m, n):
  i = par(m)
  j = par(n)
  UF[i] = j
for i in range(H):
  for j in range(W):
    if i+1 < H and S[i][j] != S[i+1][j]:
      unite(i*W+j, (i+1)*W+j)
    if j+1 < W and S[i][j] != S[i][j+1]:
      unite(i*W+j, i*W+j+1)
nsb = [0]*(H*W)
nsw = [0]*(H*W)
for i in range(H):
  for j in range(W):
    p = par(i*W+j)
    if S[i][j] == "#":
      nsb[p] += 1
    if S[i][j] == ".":
      nsw[p] += 1
r = 0
for p in range(H*W):
  r += nsb[p]*nsw[p]
print(r)
#  print(UF[i*W:(i+1)*W])

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
import collections
import itertools
import operator


class UnionFind:
    def __init__(self, x):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)
        self.size = collections.defaultdict(lambda: 1)
        if x is not None:
            for elem in range(x+1):
                _, _, _ = self.parent[elem], self.rank[elem],self.size[elem]

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if not self.are_same(x,y):
            xx = self.size[x]
            yy = self.size[y]
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += xx
            else:
                self.parent[y] = x
                self.size[x] += yy
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

    def Size(self,x):
        return self.size[self.find(x)]

    def are_same(self, x, y):
        '''print(x,y,self.find(x),self.find(y),self.find(x) == self.find(y))'''
        return self.find(x) == self.find(y)

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield [x for x, _ in group]


h,w = m()
uf = UnionFind(h*w-1)
s = [list(input()) for i in range(h)]


for i in range(h):
    for j in range(w):
        if i == h - 1 and j == w - 1:
            continue
        elif i == h - 1:
            if s[i][j] != s[i][j+1]:
                uf.unite(i*w + j,i*w + j+1)
        elif j == w - 1:
            if s[i][j] != s[i+1][j]:
                uf.unite(i*w + j,(i+1)*w + j)
        else:
            if s[i][j] != s[i+1][j]:
                uf.unite(i*w + j,(i+1)*w + j)
            if s[i][j] != s[i][j+1]:
                uf.unite(i*w + j,i*w + j+1)
kkk = list(uf.grouper())
ans = 0

for i in range(len(kkk)):
    black = 0
    white = 0
    for j in kkk[i]:
        if s[j//w][j%w] == ".":
            white += 1
        else:
            black += 1
    ans += black*white
print(ans)

Submission status: Accepted

Solution code:
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 _ in range(H)]

ans = 0
for i in range(H):
    for j in range(W):
        if checked[i][j]:
            continue
        checked[i][j] =  True
        cnt_b = 0
        cnt_w = 0
        if S[i][j] == "#":
            cnt_b += 1
        else:
            cnt_w += 1
        stack = es[(i,j)]

        while True:
            ns = []
            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
                    ns.extend(es[(p,q)])

                
            if len(ns) == 0:
                break
            else:
                stack = ns
        ans += cnt_b * cnt_w

print(ans)

Submission status: Accepted

Solution code:
"""
prd_xxxさんの解答に自分向けにコメントを付けただけ
https://atcoder.jp/contests/aising2019/submissions/3986546
"""

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

# マス目分のUnionFind木を用意
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)

c1 = Counter()
c2 = Counter()

for i in range(H):
    for j in range(W):
        k = i*W + j
        # uf.root(k)は連結成分の番号（ユニオンの番号）を表していて、それらにつながっている黒と白の個数を求める
        if S[i][j] == ".":
            c1[uf.root(k)] += 1
        else:
            c2[uf.root(k)] += 1

ans = 0
for k in c1.keys():
    # それぞれの連結成分について、出発地点となる黒とゴールとなる白の組み合わせの分だけ足していく
    ans += c1[k] * c2[k]

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def unite(node_a, node_b):
    root_a, depth_a = node_a.root()
    root_b, depth_b = node_b.root()
    if root_a == root_b:# すでに連結成分
        return
    elif depth_a >= depth_b:# aの方が深い
        root_b.is_root = False
        root_b.parent = root_a
        root_a.white += root_b.white
        root_a.black += root_b.black
    else:# bの方が深い
        root_a.is_root = False
        root_a.parent = root_b
        root_b.white += root_a.white
        root_b.black += root_a.black

class Node:
    def __init__(self, color):# color: 0:white, 1:black
        self.parent = None
        self.is_root = True
        self.white = 1 if color == 0 else 0
        self.black = 1 if color == 1 else 0
    
    def root(self):
        node = self
        depth = 0
        while not node.is_root:
            node = node.parent
            depth += 1
        return node, depth

def main():
    H, W = map(int, input().split())
    s = [input().strip() for i in range(H)]
    
    nodes = [[Node(0 if s[j][i] == "." else 1) for i in range(W)] for j in range(H)]

    for y in range(H):
        for x in range(W):
            now = s[y][x]
            for nx, ny in [(x, y-1), (x+1, y), (x, y+1), (x-1, y)]:
                if 0 <= nx and nx < W and 0 <= ny and ny < H:
                    if s[ny][nx] != now:
                        unite(nodes[y][x], nodes[ny][nx])
    
    ans = 0
    # count_roots = 0
    for y in range(H):
        for x in range(W):
            if nodes[y][x].is_root:
                # count_roots += 1
                node = nodes[y][x]
                ans += node.white * node.black
    print(ans)
    # print(count_roots)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

def find(tab, a):
    if tab[a] == -1: return a
    tab[a] = find(tab, tab[a])
    return tab[a]

def union(tab, a, b):
    pa, pb = (find(tab, a), find(tab, b))
    if pa!=pb:
        tab[pb] = pa

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

for y in range(H):
    for x in range(W):
        for dx,dy in [(-1,0),(1,0),(0,1),(0,-1)]:
            xx=x+dx
            yy=y+dy
            if xx < 0 or xx>=W or yy<0 or yy>=H:
                continue
            src = W*y+x
            dst = W*yy+xx
            if S[y][x]!=S[yy][xx]:
                union(tab, src, dst)
dic = defaultdict(lambda: {"#":0,".":0})
for i in range(N):
    p = find(tab, i)
    t = S[i//W][i%W]
    dic[p][t]+=1

ans = 0
for d in dic.values():
    ans += (d["#"]*d["."])
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from collections import defaultdict

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

class UnionFind :
    def __init__(self, size) :
        """
        Parameters
        ---
        size : int
            頂点数
        """
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        """
        親のインデックスの取得

        Parameters
        ---
        index : int
            取得する頂点のインデックス

        Returns
        ---
        rootIndex : int
            指定した頂点の根のインデックス
        """
        if self.parent[index] == index :  # 根の場合
            return index
        rootIndex = self.root(self.parent[index])  # 葉の場合親の根を取得
        self.parent[index] = rootIndex  # 親の付け直し
        return rootIndex

    def union(self, index1, index2) :  # 結合
        """
        木の結合

        Parameters
        ---
        index1 : int
        index2 : int
            結合する頂点のインデックス
        """
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  # 連結されている場合
            return

        self.component -= 1  # 連結成分を減らす

        if self.height[root1] < self.height[root2] :
            self.parent[root1] = root2  # root2に結合
            self.size[root2] += self.size[root1]
        else :
            self.parent[root2] = root1  # root1に結合
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2] :
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2) :
        """
        同じ木に属するかを判定する

        Parameters
        ---
        index1 : int
        index2 : int

        Returns
        ---
        boolean
        """
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        """
        指定した頂点の属する木の大きさを取得する
        """
        return self.size[self.root(index)]

    def getComponent(self) :
        """
        連結成分数を取得する
        """
        return self.component

tree = UnionFind(H * W)
visited = [[False] * W for _ in range(H)]

def f(h, w):
    return h * W + w

def search(h, w):
    que = deque([(h, w)])

    while que:
        nh, nw = que.popleft()
        if visited[nh][nw]:
            continue
        visited[nh][nw] = True
        tree.union(f(h, w), f(nh, nw))
        if nh > 0 and chart[nh][nw] != chart[nh - 1][nw]:
            que.append((nh - 1, nw))
        if nh < H - 1 and chart[nh][nw] != chart[nh + 1][nw]:
            que.append((nh + 1, nw))
        if nw > 0 and chart[nh][nw] != chart[nh][nw - 1]:
            que.append((nh, nw - 1))
        if nw < W - 1 and chart[nh][nw] != chart[nh][nw + 1]:
            que.append((nh, nw + 1))

cntBW = defaultdict(lambda : [0, 0])

for h in range(H):
    for w in range(W):
        if tree.root(f(h, w)) == f(h, w) and chart[h][w] == '#':
            search(h, w)

for h in range(H):
    for w in range(W):
        if chart[h][w] == '#':
            cntBW[tree.root(f(h, w))][0] += 1
        else:
            cntBW[tree.root(f(h, w))][1] += 1

ans = 0

for black, white in cntBW.values():
    ans += black * white

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
h,w = map(int,input().split())
S = [input() for _ in range(h)]


avail = [[True]*w for _ in range(h)]


def search(i,j,data):
    if S[i][j] == "#":
        data[0] += 1
    else:
        data[1] += 1
    avail[i][j] = False

    if i+1 < h and S[i+1][j] != S[i][j] and avail[i+1][j]:
        search(i+1,j,data)
    if j+1 < w and S[i][j+1] != S[i][j] and avail[i][j+1]:
        search(i,j+1,data)
    if i > 0 and S[i][j] != S[i-1][j] and avail[i-1][j]:
        search(i-1,j,data)
    if j > 0 and S[i][j] != S[i][j-1] and avail[i][j-1]:
        search(i,j-1,data)

ans = 0
for i in range(h):
    for j in range(w):
        if avail[i][j]:
            data = [0,0]
            search(i,j,data)
            ans+= data[0]*data[1]
            #print(data,i,j)

print(ans)

Submission status: Accepted

Solution code:

from collections import deque, defaultdict
import copy
import bisect
#sys.setrecursionlimit(10 ** 9)
import math
import heapq


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

H, W = list(map(int, input().split()))
S = []
for i in range(H):
	S.append(list(input()))
for i in range(H):
	for j in range(W):
		if S[i][j] == '#':
			S[i][j] = 0
		else:
			S[i][j] = 1

judge = [[0]*W for i in range(H)]
dxy = [[0,1],[1,0],[-1,0],[0,-1]]

total = 0
for i in range(H):
	for j in range(W):
		if judge[i][j] == 0:
			black = 0
			white = 0
			que = deque()
			que.append([i, j])
			judge[i][j] = 1
			black += S[i][j] ^ 1
			white += S[i][j]
			#print(i, j,black, white)
			while len(que) > 0:
				loc = que.popleft()
				for n in range(4):
					loc_new = [loc[0] + dxy[n][0], loc[1] + dxy[n][1]]
					if loc_new[0] >= 0 and loc_new[0] < H and loc_new[1] >= 0 and loc_new[1] < W:
						if judge[loc_new[0]][loc_new[1]] == 0 and S[loc[0]][loc[1]] ^ S[loc_new[0]][loc_new[1]] == 1:
							judge[loc_new[0]][loc_new[1]] = 1
							black += S[loc_new[0]][loc_new[1]] ^ 1
							white += S[loc_new[0]][loc_new[1]]
							que.append(loc_new)
			total += black * white
			#print(total)

print(total)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#エイシングプログラミングコンテスト2019 C

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


dx,dy = [1,0,-1,0],[0,1,0,-1]
h,w = LI()
s = [input() for _ in range(h)]
que = deque()
ch = [[-1]*w for _ in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            if ch[i][j] < 0:
                ch[i][j] = 0
                que = deque()
                que.append((i,j))
                #a:= ルールを守りながら行ける#の数
                #b:= ルールを守りながら行ける.の数
                a,b = 1,0
                while que:
                    y,x = que.popleft()
                    for k in range(4):
                        nx,ny = x + dx[k], y + dy[k]
                        if 0 <= nx < w and 0 <= ny < h and ch[ny][nx] < 0:
                            if s[y][x] != s[ny][nx]:
                                if s[ny][nx] == '#':
                                    a += 1
                                else:
                                    b += 1
                                ch[ny][nx] = 0
                                que.append((ny,nx))
                ans += a*b
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

H,W = map(int,input().split())
grid = '*' * (W+2)
for _ in range(H):
    grid += '*' + input().rstrip() + '*'
grid += '*' * (W+2)

move = [1,-1,W+2,-(W+2)]

root = [None if x == '*' else -1 for x in grid]

answer = 0
for i in range((H+2)*(W+2)):
    if root[i] != -1:
        continue
    q = [i]
    root[i] = i
    counter = defaultdict(int)
    while q:
        x = q.pop()
        counter[grid[x]] += 1 
        for dx in move:
            y = x + dx
            if root[y] != -1:
                continue
            if grid[x] == grid[y]:
                continue
            root[y] = i
            q.append(y)
    answer += counter['.'] * counter['#']

print(answer)

Submission status: Accepted

Solution code:
from collections import deque

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

ret = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != '?':
            q = deque()
            q.appendleft((i, j))
            white = 0
            black = 0
            while q:
                h, w= q.pop()
                color = S[h][w]
                if color == '?':
                    continue
                elif color == '#':
                    black += 1
                else:
                    white += 1
                S[h][w] = '?'
                cand = [(h+1, w), (h-1, w), (h, w+1), (h, w-1)]
                for hc, wc in cand:
                    if 0 <= hc < H and 0 <= wc < W and (S[hc][wc] not in [color, '?']):
                        q.appendleft((hc, wc))

            ret += black * white

print(ret)

Submission status: Accepted

Solution code:
import itertools
import itertools
import os
import sys
from collections import deque

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

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

H, W = list(map(int, sys.stdin.readline().split()))
S = [list(sys.stdin.readline().rstrip()) for _ in range(H)]
seen = np.zeros((H, W), dtype=bool)

ans = 0
for h, w in itertools.product(range(H), range(W)):
    if seen[h][w]:
        continue
    que = deque()
    que.append((h, w))
    black = white = 0
    while que:
        h, w = que.popleft()
        if seen[h][w]:
            continue
        seen[h][w] = True
        if S[h][w] == '#':
            black += 1
        else:
            white += 1
        for dh, dw in zip((h + 1, h - 1, h, h), (w, w, w + 1, w - 1)):
            if 0 <= dh < H and 0 <= dw < W and not seen[dh][dw]:
                if S[h][w] != S[dh][dw]:
                    que.append((dh, dw))
    ans += black * white
print(ans)

Submission status: Accepted

Solution code:
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np
from scipy.misc import comb

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

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

H, W = list(map(int, sys.stdin.readline().split()))
S = [list(sys.stdin.readline().rstrip()) for _ in range(H)]
seen = np.zeros((H, W), dtype=bool)


def dfs(h, w):
    if seen[h][w]:
        return 0, 0
    seen[h][w] = True
    black = int(S[h][w] == '#')
    white = int(S[h][w] == '.')
    for dh, dw in zip([h, h, h + 1, h - 1], [w + 1, w - 1, w, w]):
        if 0 <= dh < H and 0 <= dw < W:
            if S[h][w] != S[dh][dw]:
                counts = dfs(dh, dw)
                black += counts[0]
                white += counts[1]
    return black, white


ans = 0
for h, w in itertools.product(range(H), range(W)):
    black, white = dfs(h, w)
    ans += black * white
print(ans)

Submission status: Accepted

Solution code:
import sys;sys.setrecursionlimit(9**9);h,w=map(int,input().split());b=[[0]*(w+1)]
for i in range(h):
  b.append([0])
  for j in input():b[-1].append(1+(j=="#"))
  b[-1].append(0)
b.append([0]*(w+1));d=[[0,1],[0,-1],[1,0],[-1,0]];a=0
def s(i,j):
  global B;B[b[i][j]-1]+=1;v=b[i][j];b[i][j]=0
  for k in d:
    if v^3==b[i+k[0]][j+k[1]]:s(i+k[0],j+k[1])
for i in range(1,h+1):
  for j in range(1,w+1):B=[0,0];s(i,j);a+=B[0]*B[1]
print(a)

Submission status: Accepted

Solution code:
import sys;sys.setrecursionlimit(10**9);h,w=map(int,input().split());b=[[0]*(w+1)]
for i in range(h):
  b.append([0])
  for j in input():
    if j==".":b[-1].append(1)
    else:b[-1].append(2)
  b[-1].append(0)
b.append([0]*(w+1));d=[[0,1],[0,-1],[1,0],[-1,0]];a=0
def s(i,j):
  global B;B[b[i][j]-1]+=1;v=b[i][j];b[i][j]=0
  for k in d:
    if v^3!=b[i+k[0]][j+k[1]]:continue
    s(i+k[0],j+k[1])
for i in range(1,h+1):
  for j in range(1,w+1):B=[0,0];s(i,j);a+=B[0]*B[1]
print(a)

Submission status: Accepted

Solution code:
import sys;sys.setrecursionlimit(10**9)
h,w=map(int,input().split())
b=[[0]*(w+1)]
for i in range(h):
  b.append([0])
  for j in input():
    if j==".":b[-1].append(1)
    else:b[-1].append(2)
  b[-1].append(0)
b.append([0]*(w+1))
d=[[0,1],[0,-1],[1,0],[-1,0]]
a=0
def bfs(i,j):
  global br,wh
  if b[i][j]==0:return
  if b[i][j]==1:wh+=1
  elif b[i][j]==2:br+=1
  v=b[i][j]
  b[i][j]=0
  for k in d:
    if v^3!=b[i+k[0]][j+k[1]]:continue
    bfs(i+k[0],j+k[1])
for i in range(1,h+1):
  for j in range(1,w+1):
    br=wh=0
    bfs(i,j)
    a+=br*wh
print(a)

Submission status: Accepted

Solution code:
f=lambda x:x if p[x]<0else f(p[x])
def u(x,y):
  x,y=f(x),f(y)
  if x!=y:
    if p[x]>p[y]:x,y=y,x
    p[x]+=p[y]
    p[y]=x
h,*s=open(0)
h,w=map(int,h.split())
r=range(h*w)
p=[-1]*h*w
for i in r:
  j,k=i//w,i%w
  h>j+1and s[j][k]!=s[j+1][k]and u(i,i+w)or w>k+1and s[j][k]!=s[j][k+1]and u(i,i+1)
d=[[0,0]for _ in r]
for i in r:d[f(i)][s[i//w][i%w]<'.']+=1
print(sum(i*j for i,j in d))

Submission status: Accepted

Solution code:
def root(x):
  if data[x]<0:return x
  else:
    data[x]=root(data[x])
    return data[x]
def unite(x,y):
  x,y=root(x),root(y)   
  if x!=y:
    if data[x]>data[y]:x,y=y,x
    data[x]+=data[y]
    data[y]=x
from collections import*
r=range
h,*s=open(0)
h,w=map(int,h.split())
data=[-1]*h*w
for i in r(h):
  for j in r(w):
    if i+1<h and s[i][j]!=s[i+1][j]:
      unite(i*w+j,-~i*w+j)
    if j+1<w and s[i][j]!=s[i][j+1]:
      unite(i*w+j,i*w+j+1)
d=defaultdict(lambda:[0,0])
for i in r(h*w):d[root(i)][s[i//w][i%w]<'.']+=1
print(sum(i*j for i,j in d.values()))

Submission status: Accepted

Solution code:
import collections
import sys
sys.setrecursionlimit(1000000)


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


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

q = collections.deque()


def bfs(i, j):
    b, w = 0, 0
    seen[i][j] = True
    q.append((i, j))

    while q:
        ci, cj = q.popleft()

        if S[ci][cj] == '#':
            b += 1
        else:
            w += 1

        for di, dj in move:
            ni = ci+di
            nj = cj+dj
            if 0 <= ni < H and 0 <= nj < W:
                if seen[ni][nj] is False and S[ci][cj] != S[ni][nj]:
                    seen[ni][nj] = True
                    q.append((ni, nj))

    return b*w


ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#' and seen[i][j] is False:
            ans += bfs(i, j)

print(ans)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
#  --*-coding:utf-8-*--


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()