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:
class UnionFind(object):
 
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]
 
    def find(self, x):
        if self.table[x] < 0:
            return x
        self.table[x] = self.find(self.table[x])
        return self.table[x]
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 == s2:
            return False
        if self.table[s1] > self.table[s2]:
            s1, s2 = s2, s1
        self.table[s1] += self.table[s2]
        self.table[s2] = s1
        return True

H, W = list(map(int, input().split()))
S = list(input() for _ in range(H))
uf = UnionFind(H*W)

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

for h in range(H):
    for w in range(W):        
        for dh, dw in zip((0, 1), (1, 0)):
            if (h + dh) >= H or (w + dw) >= W:
                continue
            if S[h][w] != S[h+dh][w+dw]:
                uf.union(get(h, w), get(h+dh, w+dw))


from itertools import product

C1 = []
C2 = []

for h in range(H):
    for w in range(W):
        if S[h][w] == ".":
            C1.append((h, w))
        else:
            C2.append((h, w))

white = [0] * (H * W)
black = [0] * (H * W)

for h in range(H):
    for w in range(W):
        n = get(h, w)
        par = uf.find(n)
        # print(h, w, n, par)
        if par < 0:
            par = n
        if S[h][w] == ".":
            white[par] += 1
        else:
            black[par] += 1
            
ans = 0
# print(white)
# print(black)
for h in range(H):
    for w in range(W):
        n = get(h, w)
        ans += white[n] * black[n]
print(ans)

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

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

INF = int(1e12)

def dfs(h, w, p):
    b_cnt = 0
    w_cnt = 0
    if h < 0 or h >= H or w < 0 or w >= W:
        return 0, 0
    if S[h][w] == p or S[h][w] == 'x':
        return 0, 0
    if S[h][w] == '#':
        b_cnt += 1
    elif S[h][w] == '.':
        w_cnt += 1
    t = S[h][w]
    S[h][w] = 'x'

    for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
        res = dfs(h + dh, w + dw, t)
        b_cnt += res[0]
        w_cnt += res[1]

    return (b_cnt, w_cnt)

ans = 0

for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            b_cnt, w_cnt = dfs(h, w, '.')
            ans += b_cnt * w_cnt

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
s = [list(input()) for i in range(h)]

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

usedall = set()
ans = 0

for j in range(h):
    for i in range(w):
        if (i, j) in usedall:
            continue

        used = {(i, j)}
        usedall.add((i, j))
        q = deque([(i, j)])

        while q:
            ii, jj = q.popleft()
            cur = s[jj][ii]

            for k in range(4):
                if not (0 <= ii + dx[k] < w):
                    continue
                if not (0 <= jj + dy[k] < h):
                    continue

                if s[jj + dy[k]][ii + dx[k]] == cur:
                    continue
                if (ii + dx[k], jj + dy[k]) in used:
                    continue

                used.add((ii + dx[k], jj + dy[k]))
                usedall.add((ii + dx[k], jj + dy[k]))
                q.append((ii + dx[k], jj + dy[k]))

        black = 0
        white = 0
        for m, n in used:
            if s[n][m] == "#":
                black += 1
            else:
                white += 1

        ans += black * white

print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    # 負の値はルートで集合の個数
    # 正の値は次の要素を返す
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    # 集合の代表を求める
    def find(self, x):
        while self.table[x] >= 0:
            # 根に来た時,self.table[根のindex]は負の値なのでx = 根のindexで値が返される。
            x = self.table[x]
        return x

    # 併合
    def union(self, x, y):
        s1 = self.find(x)  # 根のindex,table[s1]がグラフの高さ
        s2 = self.find(y)
        if s1 != s2:  # 根が異なる場合
            if self.table[s1] != self.table[s2]:  # グラフの高さが異なる場合
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                else:
                    self.table[s1] = s2
            else:
                # グラフの長さが同じ場合,どちらを根にしても変わらない
                # その際,グラフが1長くなることを考慮する
                self.table[s1] += -1
                self.table[s2] = s1
        return


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

union = UnionFind(h * w)

for i in range(h):
    for j in range(w):
        if i > 0 and s[i][j] != s[i - 1][j]:
            union.union(w * i + j, w * (i - 1) + j)
        if j > 0 and s[i][j] != s[i][j - 1]:
            union.union(w * i + j, w * i + (j - 1))
out = [[0, 0] for _ in range(h * w)]
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            out[union.find(w * i + j)][0] += 1
        else:
            out[union.find(w * i + j)][1] += 1
count = 0
for _out in out:
    count += _out[0] * _out[1]
print(count)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
class UnionFind:
    def __init__(self, size):
        # 負の値はルート (集合の代表) で集合の個数
        # 正の値は次の要素を表す
        self.table = [-1 for _ in range(size)]

    # 集合の代表を求める
    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    # 併合
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                # 小さいほうが個数が多い
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False


S = [input() for i in range(H)]
u = UnionFind(H*W)
d = [(-1,0),(1,0),(0,-1),(0,1)]
for x in range(H):
    for y in range(W):
        for dx,dy in d:
            if x+dx<0 or x+dx>=H or y+dy<0 or y+dy>=W:
                continue
            if S[x+dx][y+dy] == S[x][y]:
                continue
            u.union(x+H*y,x+dx+H*(y+dy))

from collections import defaultdict
d = defaultdict(lambda:[[],[]])

for x in range(H):
    for y in range(W):
        if S[x][y] == '#':
            d[u.find(x+H*y)][0].append((x,y))
        else:
            d[u.find(x+H*y)][1].append((x,y))

ans = 0
for key in d:
    ans += len(d[key][0])*len(d[key][1])
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)

def trace(i, j, S, col, num_color):
    next_col = 1 - col
    num_color[col] += 1
    S[i][j] = 2
    if S[i-1][j] == next_col:
        trace(i-1, j, S, next_col, num_color)
    if S[i][j-1] == next_col:
        trace(i, j-1, S, next_col, num_color)
    if S[i+1][j] == next_col:
        trace(i+1, j, S, next_col, num_color)
    if S[i][j+1] == next_col:
        trace(i, j+1, S, next_col, num_color)
    return num_color[0] * num_color[1]

def main():
    H, W = map(int, input().split())
    # 黒0，白1，padding2
    S = [[2] * (W+2)]
    for _ in range(H):
        S.append([2] + [0 if s == '#' else 1 for s in input()] + [2])
    S.append([2] * (W+2))
    num_comb = 0
    for i in range(1, H+1):
        for j in range(1, W+1):
            if S[i][j] == 0:
                num_color = [0, 0]
                num_comb += trace(i, j, S, 0, num_color)
    print(num_comb)

main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(2000000)


def update(M, S, i, j, H, W, cluster):
    for i_n in [i - 1, i, i + 1]:
        for j_n in [j - 1, j, j + 1]:
            if i_n >= H or i_n < 0:
                continue
            if j_n >= W or j_n < 0:
                continue

            if i_n == i and j_n == j:
                continue
            if abs(i - i_n) + abs(j - j_n) == 2:
                continue

            if S[i][j] != S[i_n][j_n] and M[i_n][j_n] == 0:
                # print(M)
                M[i_n][j_n] = cluster
                update(M, S, i_n, j_n, H, W, cluster)


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

cluster = 1
counts_B = {}
counts_W = {}
M = [[0 for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        if M[i][j] == 0:
            M[i][j] = cluster
            update(M, S, i, j, H, W, cluster)
            cluster = cluster + 1
        counts_B[M[i][j]] = 0
        counts_W[M[i][j]] = 0


for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            counts_B[M[i][j]] += 1
        else:
            counts_W[M[i][j]] += 1

    #     print(M[i][j], end=" ")
    # print("")

total = 0
for k in counts_B.keys():
    if k in counts_W:
        total += counts_B[k] * counts_W[k]
    # print(counts[k])

print(total)

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3

import itertools
import sys


DELTAS = [(1, 0), (-1, 0), (0, 1), (0, -1)]


class UnionFind(object):

    def __init__(self, number_of_nodes):
        self.par = list(range(number_of_nodes))
        self.rank = [0] * number_of_nodes
        self.groups = [{i} for i in range(number_of_nodes)]

    def root(self, node):
        if self.par[node] == node:
            return node
        else:
            r = self.root(self.par[node])
            self.par[node] = r
            return r

    def in_the_same_set(self, node1, node2):
        return self.root(node1) == self.root(node2)

    def elements_of_group(self, node):
        return self.groups[self.root(node)]

    def unite(self, node1, node2):
        x = self.root(node1)
        y = self.root(node2)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            self.par[y] = x
            self.groups[x].update(self.groups[y])
            self.groups[y].clear()
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


def solve(h, w, stage):
    n = h * w
    uf = UnionFind(n)
    for r0, c0 in itertools.product(range(h), range(w)):
        x0 = w * r0 + c0
        ib = stage[r0][c0]
        for dr, dc in DELTAS:
            r, c = r0 + dr, c0 + dc
            if 0 <= r < h and 0 <= c < w and ib != stage[r][c]:
                x = w * r + c
                uf.unite(x0, x)
    res = 0
    is_black = [None] * n
    for r0, c0 in itertools.product(range(h), range(w)):
        x0 = w * r0 + c0
        is_black[x0] = stage[r0][c0]
    for x1 in range(n):
        eg = uf.groups[x1]
        # print(x1, eg, file=sys.stderr)
        total = len(eg)
        num_black = sum(is_black[x] for x in eg)
        res += (total - num_black) * num_black
    return res


def main():
    h, w = (int(z) for z in input().split())
    stage = [[c == "#" for c in input()] for _ in range(h)]
    res = solve(h, w, stage)
    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)
H,W=map(int,input().split())
Map=[input() for i in range(H)]
G=[[[] for i in range(W)] for i in range(H)]
for i in range(H):
  for j in range(W):
    if i>=1:
      if Map[i-1][j]!=Map[i][j]:
        G[i][j].append((i-1,j))
    if j>=1:
      if Map[i][j-1]!=Map[i][j]:
        G[i][j].append((i,j-1))
    if i<=H-2:
      if Map[i+1][j]!=Map[i][j]:
        G[i][j].append((i+1,j))
    if j<=W-2:
      if Map[i][j+1]!=Map[i][j]:
        G[i][j].append((i,j+1))
Visited=[[False]*W for i in range(H)]
def dfs(x,y):
  w,b=0,0
  if Visited[x][y]:
    return (0,0)
  Visited[x][y]=True
  if Map[x][y]==".":
    w+=1
  else:
    b+=1
  for p,q in G[x][y]:
    if not Visited[p][q]:
      w_,b_=dfs(p,q)
      w+=w_
      b+=b_
  return (w,b)
ans=0
for i in range(H):
  for j in range(W):
    p,q=dfs(i,j)
    ans+=p*q
print(ans)

Submission status: Accepted

Solution code:
# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]

import sys

# input = sys.stdin.readline
sys.setrecursionlimit(400*400*10)
MOD = 10 ** 9 + 7

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

T = [[0] * W for _ in range(H)]

t = 1


def f(h, w):
    cb = cw = 0
    dh = [1, -1, 0, 0]
    dw = [0, 0, 1, -1]

    for i in range(4):
        h2 = h + dh[i]
        w2 = w + dw[i]
        if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
            # 未調査 かつ 色違い
            if T[h2][w2] == 0:
                if S[h][w] != S[h2][w2]:
                    T[h2][w2] = 1
                    if S[h2][w2] == "#":
                        cb += 1
                    if S[h2][w2] == ".":
                        cw += 1
                    cb2, cw2 = f(h2, w2)
                    cb += cb2
                    cw += cw2
    return cb, cw


area = []
for h in range(H):
    for w in range(W):
        if S[h][w] == "#" and T[h][w] == 0:
            tmp = f(h, w)
            if tmp[0]*tmp[1] != 0:
                area.append(tmp)

ans = 0
for a in area:
    ans += a[0]*a[1]

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
h,w = map(int, input().split())
sf = [input() for _ in range(h)]

def candidate(hi,wi):
    for d in [[1,0],[0,1],[-1,0],[0,-1]]:
        dh = hi+d[0]
        dw = wi+d[1]
        if h>dh>=0 and w>dw>=0 and sf[hi][wi]!=sf[dh][dw]:
            return True
    return False

csf = [[False for _ in range(w)] for _ in range(h)]
for hi in range(h):
    for wi in range(w):
        csf[hi][wi] = candidate(hi,wi)
res = 0
used = [[False for _ in range(w)] for _ in range(h)]
for hi in range(h):
    for wi in range(w):
        if used[hi][wi]:
            continue
        st = [(hi,wi,sf[hi][wi])]
        nb = 0
        nw = 0
        # print("===")
        while len(st)>0:
            s = st.pop()
            # print(s)
            if csf[s[0]][s[1]] and not used[s[0]][s[1]]:
                used[s[0]][s[1]] = True
                if s[2] == "#":
                    nb += 1
                else:
                    nw += 1
                for d in [[1,0],[0,1],[-1,0],[0,-1]]:
                    dh = s[0]+d[0]
                    dw = s[1]+d[1]
                    if h>dh>=0 and w>dw>=0 and csf[dh][dw] and not used[dh][dw] and sf[s[0]][s[1]]!=sf[dh][dw]:
                        st.append((dh,dw,sf[dh][dw]))
        res += nb*nw
print(res)

Submission status: Accepted

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

def dfs(h,w,i,c):
    # グループ分け
    V[h][w] = i
    # 上
    if h>0 and V[h-1][w]==0:
        if c=="#" and S[h-1][w]==".":
            dfs(h-1,w,i,".")
        elif c=="." and S[h-1][w]=="#":
            dfs(h-1,w,i,"#")
    # 左
    if w>0 and V[h][w-1]==0:
        if c=="#" and S[h][w-1]==".":
            dfs(h,w-1,i,".")
        elif c=="." and S[h][w-1]=="#":
            dfs(h,w-1,i,"#")
    # 下
    if h<H-1 and V[h+1][w]==0:
        if c=="#" and S[h+1][w]==".":
            dfs(h+1,w,i,".")
        elif c=="." and S[h+1][w]=="#":
            dfs(h+1,w,i,"#")
    # 右
    if w<W-1 and V[h][w+1]==0:
        if c=="#" and S[h][w+1]==".":
            dfs(h,w+1,i,".")
        elif c=="." and S[h][w+1]=="#":
            dfs(h,w+1,i,"#")

V = [[0 for _ in range(W)] for _ in range(H)]
ans = 0
i = 0
for h in range(H):
    for w in range(W):
        if S[h][w]=="#" and V[h][w]==0:
            i += 1
            dfs(h,w,i,"#")

# iグループに分割完了
cnt_b = [0]*i
cnt_w = [0]*i

for h in range(H):
    for w in range(W):
        group = V[h][w]
        if group != 0:
            if S[h][w]=="#":
                cnt_b[group-1] += 1
            else:
                cnt_w[group-1] += 1

ans = 0
for i in range(len(cnt_b)):
    ans += cnt_b[i]*cnt_w[i]

print(ans)

Submission status: Accepted

Solution code:
import sys

def 解():
    input = sys.stdin.readline
    H,W = [int(_) for _ in input().split()]
    aM = [""]*H
    for i in range(H):
        aM[i] = input().rstrip()

    adxy=[(0,1),(1,0),(-1,0),(0,-1)]
    dsVBs=set()

    def bfsM(i,j):
        aS = [(i,j)]
        dsV = set()
        dsVB = set()
        iC = 0
        while aS:
            th,tw = aS[0]
            del aS[0]
            if aM[th][tw] == ".":
                iC += 1
                for dh,dw in adxy:
                    nh,nw=dh+th,dw+tw
                    nP = (nh,nw)
                    if 0 <= nh < H and 0 <= nw < W:
                        if aM[nh][nw] == "#" and nP not in dsV:
                            aS.append(nP)
                            dsV.add(nP)
                            dsVB.add(nP)
            else:
                for dh,dw in adxy:
                    nh,nw=dh+th,dw+tw
                    nP = (nh,nw)
                    if 0 <= nh < H and 0 <= nw < W:
                        if aM[nh][nw] == "." and nP not in dsV:
                            aS.append(nP)
                            dsV.add(nP)
        iB = len(dsVB)
        for nP in dsVB:
            dsVBs.add(nP)
        return iC*iB

    iAns = 0
    for i in range(H):
        for j in range(W):
            if aM[i][j] == "#" and (i,j) not in dsVBs:
                iAns += bfsM(i,j)
    print(iAns)
解()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys


def main():
    h,w = map(int, sys.stdin.readline().rstrip().split(' '))
    s = []
    for _ in range(h):
        s.append(sys.stdin.readline().rstrip())

    taboo = set()
    flg = True
    c = 0
    while flg:
        flg = True
        for i in range(h*w):
            x, y = i%h, i//h
            if (x,y) in taboo:
                continue
            flg = False
            q = [(x,y)]
            taboo.add((x,y))
            #print(q, s[x][y])
            white, black = 0,0
            while len(q) > 0:
                x, y = q.pop()
                color = s[x][y]
                if color == ".":
                    white +=1
                else:
                    black += 1
                for v in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):
                    if v[0] >= 0 and v[0] < h and v[1] >= 0 and v[1] < w:
                        newcolor = s[v[0]][v[1]]
                        if color == newcolor or (v[0], v[1]) in taboo:
                            continue
                        q.append((v[0], v[1]))
                        taboo.add((v[0], v[1]))
                        #print(v, newcolor)
            #print(white, black)
            c += white * black
    print(c)



    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, S):
    g = defaultdict(dict)
    for i, r in enumerate(S):
        for j, c in enumerate(r):
            if i > 0 and S[i-1][j] != c:
                g[(i, j)][(i-1, j)] = 1
                g[(i-1, j)][(i, j)] = 1
            if i < H-1 and S[i+1][j] != c:
                g[(i, j)][(i+1, j)] = 1
                g[(i+1, j)][(i, j)] = 1
            if j > 0 and S[i][j-1] != c:
                g[(i, j)][(i, j-1)] = 1
                g[(i, j-1)][(i, j)] = 1
            if j < W-1 and S[i][j+1] != c:
                g[(i, j)][(i, j+1)] = 1
                g[(i, j+1)][(i, j)] = 1
    
    done = set([])
    ans = 0
    ac = {}
    for k in g:
        
        i, j = k
        if S[i][j] != '#':
            continue
        
        if k in ac:
            ans += ac[k]
            continue
        s = [k]
        done = set([k])
        w = set([])
        count = 0
        while s:
            # print(s)
            k = s.pop()
            for n in g[k]:
                if n not in done:
                    s.append(n)
                    done.add(n)
            i, j = k
            if S[i][j] == '.':
                count += 1
            else:
                w.add(k)
        for l in w:
            ac[l] = count
        ans += count
        

    return ans


def main():
    H, W = read_int_n()
    S = []
    for _ in range(H):
        S.append(read_str())
    # S = []
    # H = 400
    # W = 400
    # for i in range(H):
    #     if i%2 == 0:
    #         S.append('#.'*200)
    #     else:
    #         S.append('.#'*200)

    print(slv(H, W, S))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import product
import sys

sys.setrecursionlimit(200000)

H, W = map(int, input().split())
S = [input() for _ in range(H)]
color = [[None] * W for _ in range(H)]
memo = [[0, 0] for _ in range(H * W + 1)]
cnt = 1


def dfs(p, c):
    x, y = p
    color[x][y] = c
    memo[cnt][c] += 1
    for dx, dy in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and color[nx][ny] is None and c != (S[nx][ny] == '#'):
            dfs([nx, ny], not c)


for i, j in product(range(H), range(W)):
    if color[i][j] is None:
        dfs([i, j], S[i][j] == '#')
        cnt += 1

ans = 0
for i in range(H * W):
    ans += memo[i][0] * memo[i][1]
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
"""
This file is part of https://github.com/Cheran-Senthil/PyRival.

Copyright 2018 Cheran Senthilkumar all rights reserved,
Cheran Senthilkumar <hello@cheran.io>
Permission to use, modify, and distribute this software is given under the
terms of the MIT License.

"""
from __future__ import division, print_function

import cmath
import itertools
import math
import operator as op
# import random
import sys
from atexit import register
from bisect import bisect_left, bisect_right
# from collections import Counter, MutableSequence, defaultdict, deque
# from copy import deepcopy
# from decimal import Decimal
# from difflib import SequenceMatcher
# from fractions import Fraction
# from heapq import heappop, heappush

if sys.version_info[0] < 3:
    # from cPickle import dumps
    from io import BytesIO as stream
    # from Queue import PriorityQueue, Queue
else:
    # from functools import reduce
    from io import StringIO as stream
    # from pickle import dumps
    # from queue import PriorityQueue, Queue


if sys.version_info[0] < 3:
    class dict(dict):
        """dict() -> new empty dictionary"""
        def items(self):
            """D.items() -> a set-like object providing a view on D's items"""
            return dict.iteritems(self)

        def keys(self):
            """D.keys() -> a set-like object providing a view on D's keys"""
            return dict.iterkeys(self)

        def values(self):
            """D.values() -> an object providing a view on D's values"""
            return dict.itervalues(self)

    input = raw_input
    range = xrange

    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip


def sync_with_stdio(sync=True):
    """Set whether the standard Python streams are allowed to buffer their I/O.

    Args:
        sync (bool, optional): The new synchronization setting.

    """
    global input, flush

    if sync:
        flush = sys.stdout.flush
    else:
        sys.stdin = stream(sys.stdin.read())
        input = lambda: sys.stdin.readline().rstrip('\r\n')

        sys.stdout = stream()
        register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))


def gcd(x, y):
    """greatest common divisor of x and y"""
    while y:
        x, y = y, x % y
    return x


def connected_components(n, graph):
    components, visited = [], [False] * n

    def dfs(start):
        component, stack = [], [start]

        while stack:
            start = stack[-1]

            if visited[start]:
                stack.pop()
                continue
            else:
                visited[start] = True
                component.append(start)

            for i in graph[start]:
                if not visited[i]:
                    stack.append(i)

        return component

    for i in range(n):
        if not visited[i]:
            components.append(dfs(i))

    return components


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

    black, white = set(), set()
    for i in range(h):
        for j in range(w):
            if s[i][j] == '.':
                black.add(i*w + j)
            else:
                white.add(i*w + j)

    edges = []

    for i in range(h):
        for j in range(w):
            if s[i][j] == '.':
                if i > 0:
                    if s[i - 1][j] == '#':
                        edges.append((i*w + j, (i - 1)*w + j))
                        edges.append(((i - 1)*w + j, i*w + j))
                if i < h - 1:
                    if s[i + 1][j] == '#':
                        edges.append((i*w + j, (i + 1)*w + j))
                        edges.append(((i + 1)*w + j, i*w + j))
                if j > 0:
                    if s[i][j - 1] == '#':
                        edges.append((i*w + j, i*w + (j - 1)))
                        edges.append((i*w + (j - 1), i*w + j))
                if j < w - 1:
                    if s[i][j + 1] == '#':
                        edges.append((i*w + j, i*w + (j + 1)))
                        edges.append((i*w + (j + 1), i*w + j))

    graph = [[] for _ in range(h*w)]
    for edge in edges:
        x, y = edge
        graph[x].append(y)

    res = 0
    for comp in connected_components(h*w, graph):
        cnt1, cnt2 = 0, 0
        for j in comp:
            if j in black:
                cnt1 += 1
            else:
                cnt2 += 1
        res += cnt1 * cnt2

    print(res)


if __name__ == '__main__':
    sync_with_stdio(False)
    main()

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
S = [input() for i in range(H)]
B = [[0]*W for _ in range(H)]

for i, s in enumerate(S):
    for j, c in enumerate(s):
        if c=="#":
            B[i][j] = 1
        else:
            B[i][j] = 0
#B = [[False]*W for i in range(H)]
from itertools import product
Q = [t for t in product(range(H), range(W))]
Close = set()
from collections import deque
ans = 0
for q in Q:
    if q in Close:
        continue
    Open = deque()
    Open.append(q)
    #print(q)
    bw = [0, 0]
    while len(Open)>0:
        qq = Open.popleft()
        Close.add(qq)
        y, x = qq
        #print(y, x, bw)
        c = B[y][x]
        bw[c] += 1
        if x > 0 and (y, x-1) not in Close and c+B[y][x-1]==1:
            Open.append((y, x-1))
            Close.add((y, x-1))
        if x < W-1 and (y, x+1) not in Close and c+B[y][x+1]==1:
            Open.append((y, x+1))
            Close.add((y, x+1))
        if y > 0 and (y-1, x) not in Close and c+B[y-1][x]==1:
            Open.append((y-1, x))
            Close.add((y-1, x))
        if y < H-1 and (y+1, x) not in Close and c+B[y+1][x]==1:
            Open.append((y+1, x))
            Close.add((y+1, x))

    #print(bw)
    #print(Close)
    ans += bw[0] * bw[1]
print(ans)

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
from collections import Counter, defaultdict, deque

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()


H, W = LI()
B = [[1 if s == '#' else 0 for s in S()] for _ in range(H)]


dy = (0, -1, 0, 1)
dx = (1, 0, -1, 0)

def BFS(i, j):
    ans = 0
    queue = deque([(i, j)])
    visited = set()
    visited_b = set()
    while queue:
        y, x = queue.pop()
        color = B[y][x]
        if color == 0 and (y, x) not in visited:
            # print(y, x)
            ans += 1
        if color == 1:
            visited_b.add((y, x))
        visited.add((y, x))
        for k in range(4):
            ny = y + dy[k]
            nx = x + dx[k]
            if (ny, nx) in visited:
                continue

            if ny < 0 or ny >= H or nx < 0 or nx >= W:
                continue

            if B[ny][nx] == color:
                continue

            queue.append((ny, nx))

    return ans, visited_b


ans = 0
visited_b = set()
for h in range(H):
    for w in range(W):
        if B[h][w] == 1 and (h, w) not in visited_b:
            tmp, v = BFS(h, w)
            ans += tmp * len(v)
            visited_b |= v
            # print(ans, v)

print(ans)