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

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

import sys
sys.setrecursionlimit(2600000)

united_count = [ ]


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


def dfs(pos, c, now_k):
    
    
    
    
    y,x = pos
    for d in directions:
        try:
            if y+d[0] < 0 or x+d[1] < 0:
                continue
            content = S[y+d[0]][x+d[1]] 

            if c != content and (content == "
                S[y+d[0]][x+d[1]] = now_k
                inplace_tuple     = united_count[now_k]
                united_count[now_k]     = ( inplace_tuple[0] + 1, inplace_tuple[1]) if content == "
                                    ( inplace_tuple[0]    , inplace_tuple[1]+1) 

                dfs( (y+d[0], x+d[1]),  content,  now_k)  

            else:
                continue
        except:
            continue



now_k = 0
for y in range(H):
    for x in range(W):
        c = S[y][x]  
        if c == "
            united_count.append( (1,0) if  c == "
            S[y][x] = now_k  

            pos = (y,x)
            dfs(pos, c, now_k)
            now_k         += 1

        else:
            continue 


answer = 0
for uni in united_count:
    answer = ((uni[0]*uni[1]) + answer) 

print(answer)

Solution (Python):
h,w = map(int, input().split())
s = []
for i in range(h):
    s.append(input())
import sys
sys.setrecursionlimit(200000)
dy = [0,0,1,-1]
dx = [1,-1,0,0]
def dfs(y,x):
    global check
    global was
    was[y][x] = 1
    if s[y][x] == "
        check[0] += 1
    else:
        check[1] += 1
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if nx >= 0 and ny >= 0 and nx < w and ny < h and s[ny][nx] != s[y][x] and not was[ny][nx]:
            dfs(ny,nx)
ans = 0
was = [[0 for i in range(w)] for j in range(h)]
for i in range(w):
    for j in range(h):
        if not was[j][i]:
            check = [0,0]
            dfs(j,i)
            ans += check[0] * check[1]
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 9)

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

visited = [[False for _ in range(W)] for _ in range(H)]
vectors = [[0, -1], [-1, 0], [0, 1], [1, 0]]
ans = 0

def dfs(h, w):
    
    if visited[h][w]:
        return (0, 0)
    
    visited[h][w] = True

    if inputs[h][w] == '
        black, white = 1, 0 
    else:
        black, white = 0, 1

    for vector in vectors:
        next_h = h + vector[0]
        next_w = w + vector[1]
        if not (0 <= next_h < H and 0 <= next_w < W):
            continue
        next_color = inputs[next_h][next_w]
        if inputs[h][w] != next_color:
            p_black, p_white = dfs(next_h, next_w)
            black += p_black
            white += p_white

    return (black, white)

for h in range(H):
    for w in range(W):
        black, white = dfs(h, w)
        ans += black * white  

print(ans)

Solution (Python):




import sys
sys.setrecursionlimit(10000000)

H, W = [int(i) for i in raw_input().strip().split(' ')]
S = []
for _ in range(H):
    S.append(raw_input().strip())
C = '
CR = {'


def find(h, w, sumi):
    while True:
        if sumi[h][w] == False:
            return (h, w)
        w += 1
        if w >= W:
            w = 0
            h += 1
            if h >= H:
                return None
    return None


def chain((h, w), t, c, sumi):
    if 0 <= h < H and 0 <= w < W:
        pass
    else:
        return c
    if sumi[h][w]:
        return c
    if S[h][w] == C[t]:
        sumi[h][w] = True
        c[t] += 1
        for ptr in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
            c = chain((h+ptr[0], w+ptr[1]), 1-t, c, sumi)
        return c
    return c


def main():
    sumi = [[False for _ in range(W)] for _ in range(H)]
    h, w = 0, 0
    n = 0
    while True:
        c = [0, 0]
        
        result = find(h, w, sumi)
        if not result:
            break
        h, w = result[0], result[1]
        
        c = chain((h, w), CR[S[h][w]], c, sumi)
        
        n += c[0] * c[1]
    print n


if __name__ == '__main__':
    main()

Solution (Python):




C = '
CR = {'

H, W = [int(i) for i in raw_input().strip().split(' ')]
S = []
for _ in range(H):
    
    S.append([CR[c] for c in raw_input().strip()])


def find(h, w, sumi):
    while True:
        if sumi[h][w] == False:
            return (h, w)
        w += 1
        if w >= W:
            w = 0
            h += 1
            if h >= H:
                return None
    return None


'''
def chain((h, w), t, c, sumi):
    if 0 <= h < H and 0 <= w < W:
        pass
    else:
        return c
    if sumi[h][w]:
        return c
    if S[h][w] == t:
        sumi[h][w] = True
        c[t] += 1
        for ptr in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
            c = chain((h+ptr[0], w+ptr[1]), 1-t, c, sumi)
        return c
    return c
'''



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

def find_chain((hh, ww), t, sumi):
    
    chain_sumi = set()
    h, w = hh, ww
    sumi[h][w] = True
    chain_sumi.add((h, w))
    c = [0, 0]
    c[t] = 1
    d = 0
    stack = []
    while True:
        while True:
            if d >= 4:
                break
            hd = h + dd[d][0]
            wd = w + dd[d][1]
            d += 1
            if 0 <= hd < H and 0 <= wd < W:
                if (hd, wd) not in chain_sumi:
                    td = S[hd][wd]
                    if td == t-((hh+ww+hd+wd)&1):
                        sumi[hd][wd] = True
                        chain_sumi.add((hd, wd))
                        c[td] += 1
                        stack.append([h, w, d])
                        h , w, d = hd, wd, 0
        if len(stack) == 0:
            break
        h, w, d = stack.pop()
    
    
    return c


def main():
    sumi = [[False for _ in range(W)] for _ in range(H)]
    h, w = 0, 0
    n = 0
    while True:
        
        result = find(h, w, sumi)
        if not result:
            break
        h, w = result[0], result[1]
        
        c = find_chain((h, w), S[h][w], sumi)
        
        n += c[0] * c[1]
    print n


if __name__ == '__main__':
    main()

Solution (Python):


import collections
import itertools


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


class UnitDict(dict):

    def __init__(self, iterable=None, wrapper=lambda x: x):
        super().__init__(self)
        self.wrapper = wrapper
        if iterable is not None:
            self.update(iterable)

    def __missing__(self, key):
        self[key] = self.wrapper(key)
        return self[key]


class DisjointSetDataStructure(object):

    def __init__(self, nodes=None):
        self.par = UnitDict(wrapper=lambda x: x)
        self.rank = collections.defaultdict(int)
        self.groups = UnitDict(wrapper=lambda x: {x})
        if nodes is not None:
            for node in nodes:
                _, _, _ = self.par[node], self.rank[node], self.groups[node]
        
    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):
    dds = DisjointSetDataStructure()
    for r0, c0 in itertools.product(range(h), range(w)):
        cell0 = stage[r0][c0]
        for dr, dc in DELTAS:
            r, c = r0 + dr, c0 + dc
            if 0 <= r < h and 0 <= c < w and cell0 != stage[r][c]:
                dds.unite((r0, c0), (r, c))
    res = 0
    for nodes in dds.groups.values():
        num_total = len(nodes)
        num_black = sum(stage[r][c] for r, c in nodes)
        res += num_black * (num_total - num_black)
    return res


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


if __name__ == "__main__":
    main()

Solution (Python):

"""
Created on Sat Jan 12 18:50:46 2019
AIsingD
@author: maezawa
"""

h, w = list(map(int, input().split()))
a = [list('*'*(w+2))]
for _ in range(h):
    a.append(['*']+list(input())+['*'])
a.append(list('*'*(w+2)))
b = [[0]*(w+2) for _ in range(h+2)]


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

for i in range(1, h+1):
    for j in range(1, w+1):
        if a[i][j] == '
            stackb = [(i, j)]
            cntb = 0
            cntw = 0
            stackw = []
            while stackb:
                inext, jnext = stackb.pop(-1)
                if b[inext][jnext] != 0:
                    continue
                cntb += 1
                b[inext][jnext] = 1
                for direction in dirs:
                    inextb = inext + direction[0]
                    jnextb = jnext + direction[1]
                    if a[inextb][jnextb] == '.' and b[inextb][jnextb] == 0:
                        stackw.append((inextb,jnextb))
                while stackw:
                    inext, jnext = stackw.pop(-1)
                    if b[inext][jnext] != 0:
                        continue
                    cntw += 1
                    b[inext][jnext] = 1
                    for direction in dirs:
                        inextw = inext + direction[0]
                        jnextw = jnext + direction[1]
                        if a[inextw][jnextw] == '
                            stackb.append((inextw,jnextw))

            
            ans += cntb*cntw
print(ans)

Solution (Python):
import itertools
H, W = [int(_) for _ in input().split()]
S = [input() for _ in range(H)]
is_searched = [[False for _ in range(W)] for _ in range(H)]


def dfs(p, q):
    if is_searched[p][q] == 1:
        return 0
    count = {'
    stack = [[p, q]]
    while stack:
        x, y = stack.pop()
        if is_searched[x][y] != 1:
            is_searched[x][y] = 1
            count[S[x][y]] += 1
            dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]
            for dx, dy in dxy:
                nx, ny = x + dx, y + dy
                if 0 <= nx < H and 0 <= ny < W and S[x][y] != S[nx][ny]:
                    stack += [[nx, ny]]
    return count['


ans = 0
for i, j in itertools.product(range(H), range(W)):
    ans += dfs(i, j)
print(ans)

Solution (Python):
import itertools
H, W = [int(_) for _ in input().split()]
S = [input() for _ in range(H)]
is_searched = [[False for _ in range(W)] for _ in range(H)]


def dfs(p, q):
    if is_searched[p][q] == 1:
        return 0
    count = {'
    stack = [[p, q]]
    while stack:
        x, y = stack.pop()
        if is_searched[x][y] != 1:
            is_searched[x][y] = 1
            count[S[x][y]] += 1
            dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]
            for dx, dy in dxy:
                nx, ny = x + dx, y + dy
                if 0 <= nx < H and 0 <= ny < W and S[x][y] != S[nx][ny]:
                    stack += [[nx, ny]]
    return count['


print(sum([dfs(i, j) for i, j in itertools.product(range(H), range(W))]))

Solution (Python):
import itertools
H, W = [int(_) for _ in input().split()]
S = [input() for _ in range(H)]
is_searched = [[False for _ in range(W)] for _ in range(H)]


def dfs(p, q):
    if is_searched[p][q] == 1:
        return 0
    count = {'
    que = [[p, q]]
    while que:
        x, y = que.pop(0)
        if is_searched[x][y] != 1:
            is_searched[x][y] = 1
            count[S[x][y]] += 1
            dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]
            for dx, dy in dxy:
                nx, ny = x + dx, y + dy
                if 0 <= nx < H and 0 <= ny < W and S[x][y] != S[nx][ny]:
                    que += [[nx, ny]]
    return count['


print(sum([dfs(i, j) for i, j in itertools.product(range(H), range(W))]))

Solution (Python):
import itertools
H, W = [int(_) for _ in input().split()]
S = [input() for _ in range(H)]
A = [[0 for _ in range(W)] for _ in range(H)]


def dfs(p, q):
    if A[p][q] == 1:
        return 0
    count = {'
    stack = [[p, q]]
    while stack:
        x, y = stack.pop()
        if A[x][y] != 1:
            count[S[x][y]] += 1
            A[x][y] = 1
            dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]
            for dx, dy in dxy:
                nx, ny = x + dx, y + dy
                if 0 <= nx < H and 0 <= ny < W and S[x][y] != S[nx][ny]:
                    stack += [[nx, ny]]
    return count['


print(sum([dfs(i, j) for i, j in itertools.product(range(H), range(W))]))

Solution (Python):
import queue
H, W = map(int, input().split())
S = [list(map(int, input().replace(".", "0").replace("

Search = [(-1, 0), (0, -1), (1, 0), (0, 1)]
Total = 0
Visited = [[False for w in range(W)] for h in range(H)]
for h in range(H):
    for w in range(W):
        if not Visited[h][w]:
            Visited[h][w] = True
            Color = ([1, 0] if S[h][w] == 0 else [0, 1])
            Q = queue.Queue()
            Q.put((h, w, S[h][w]))
            while not Q.empty():
                nh, nw, nc = Q.get()
                for s in Search:
                    nexth, nextw = nh + s[0], nw + s[1]
                    if 0 <= nexth < H and 0 <= nextw < W:
                        if not Visited[nexth][nextw] and S[nexth][nextw] != nc:
                            nextc = S[nexth][nextw]
                            Visited[nexth][nextw] = True
                            Q.put((nexth, nextw, nextc))
                            Color[nextc] += 1
            Total += Color[0] * Color[1]

print(Total)

Solution (Python):
def main():
    """
    1 <= H, W <= 400
    |Si| = W  (
    """
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]

    ans = f(H, W, S)
    print(ans)


def f(H, W, S):
    ans1 = editorial(H, W, S)
    ans2 = f_rec(H, W, S)

    assert ans1 == ans2
    return ans1


def editorial(H, W, S):
    """
    ある地点からの黒と白のマスの数
    黒から白への行き方は
    黒の数から白の数
    """
    from collections import deque
    di = [1, 0, -1, 0]
    dj = [0, 1, 0, -1]
    color = [[S[i][j] == "
             for i in range(H)]
    used = [[False] * W for i in range(H)]

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

            b, w = 0, 0
            que = deque([(i, j)])
            while que:
                ci, cj = que.pop()
                if color[ci][cj]:
                    b += 1
                else:
                    w += 1

                for d in range(4):
                    ni = ci + di[d]
                    nj = cj + dj[d]
                    in_range = 0 <= ni < H and 0 <= nj < W
                    if not in_range:
                        continue
                    if used[ni][nj]:
                        continue
                    if color[ci][cj] == color[ni][nj]:
                        continue

                    used[ni][nj] = True
                    que.append((ni, nj))

            ans += b * w

    return ans


def f_rec(H, W, S):
    import sys
    sys.setrecursionlimit(10 ** 9)
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    def rec(h, w, vis):
        vis[h][w] = True
        bl, wh = 0, 0
        if S[h][w] == "
            bl += 1
        else:
            wh += 1

        for i in range(4):
            ny = h + dy[i]
            nx = w + dx[i]
            in_range = 0 <= ny < H and 0 <= nx < W
            if in_range and not vis[ny][nx] and S[ny][nx] != S[h][w]:
                n_bl, n_wh = rec(ny, nx, vis)
                bl += n_bl
                wh += n_wh

        return bl, wh

    vis = [[False] * W for _ in range(H)]
    ans = 0
    for h in range(H):
        for w in range(W):
            bl, wh = rec(h, w, vis)
            ans += bl * wh

    return ans


def TLE_pypy3(H, W, S):
    """
    c1 to c2:
        c1: black(
        c1 - not c1 - c1 - c2

    上下左右に隣り合うマスへの移動を繰り返し
    a to b: N * N = 400 ^ 2 = 1.6 * 10^5
    Nb to Nw == Nw to Nb

    あるマスからどこまで進めるか（直線）
    North <-> South
    West  <-> East

    a to b: ok
    b to c: ok
    a to c: ok (3段論法)

    """
    
    d = zip([0, 0, 1, -1],
            [1, -1, 0, 0])
    d = list(d)
    to = {"

    b = []
    for _ in range(H):
        b2 = []
        for _ in range(W):
            b2.append([None] * 4)
        b.append(b2)

    blacks = {}
    for y in range(H):
        for x in range(W):
            src = S[y][x]
            if src == "
                blacks[(y, x)] = -1

            for i, (dx, dy) in enumerate(d):
                nx = x + dx
                ny = y + dy

                valid = 0 <= nx < W and 0 <= ny < H
                if not valid:
                    continue

                if S[ny][nx] == to[src]:
                    b[y][x][i] = (ny, nx)

    ans = 0
    
    for (y, x), _ in blacks.items():
        
        bs = [(y, x)]
        
        used_bs = {}
        used_ws = {}
        while bs:
            by, bx = bs.pop()
            used_bs[(by, bx)] = None

            
            whites = []
            for pos in b[by][bx]:
                if pos and pos not in used_ws:
                    ans += 1
                    whites.append(pos)
                    used_ws[pos] = None

            
            for wy, wx in whites:
                for pos in b[wy][wx]:
                    if pos and pos not in used_bs:
                        bs.append(pos)

    return ans


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    """
    1 <= H, W <= 400
    |Si| = W  (
    """
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]

    ans = f(H, W, S)
    print(ans)


def f(H, W, S):
    ans1 = editorial(H, W, S)
    

    
    return ans1


def editorial(H, W, S):
    """
    ある地点からの黒と白のマスの数
    黒から白への行き方は
    黒の数から白の数
    """
    from collections import deque
    di = [1, 0, -1, 0]
    dj = [0, 1, 0, -1]
    color = [[S[i][j] == "
             for i in range(H)]
    used = [[False] * W for i in range(H)]

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

            b, w = 0, 0
            que = deque([(i, j)])
            while que:
                ci, cj = que.pop()
                if color[ci][cj]:
                    b += 1
                else:
                    w += 1

                for d in range(4):
                    ni = ci + di[d]
                    nj = cj + dj[d]
                    in_range = 0 <= ni < H and 0 <= nj < W
                    if not in_range:
                        continue
                    if used[ni][nj]:
                        continue
                    if color[ci][cj] == color[ni][nj]:
                        continue

                    used[ni][nj] = True
                    que.append((ni, nj))

            ans += b * w

    return ans


def f_rec(H, W, S):
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    def rec(h, w, vis):
        vis[h][w] = True
        bl, wh = 0, 0
        if S[h][w] == "
            bl += 1
        else:
            wh += 1

        for i in range(4):
            ny = h + dy[i]
            nx = w + dx[i]
            in_range = 0 <= ny < H and 0 <= nx < W
            if in_range and not vis[ny][nx] and S[ny][nx] != S[h][w]:
                n_bl, n_wh = rec(ny, nx, vis)
                bl += n_bl
                wh += n_wh

        return bl, wh

    vis = [[False] * W for _ in range(H)]
    ans = 0
    for h in range(H):
        for w in range(W):
            bl, wh = rec(h, w, vis)
            ans += bl * wh

    return ans


def TLE_pypy3(H, W, S):
    """
    c1 to c2:
        c1: black(
        c1 - not c1 - c1 - c2

    上下左右に隣り合うマスへの移動を繰り返し
    a to b: N * N = 400 ^ 2 = 1.6 * 10^5
    Nb to Nw == Nw to Nb

    あるマスからどこまで進めるか（直線）
    North <-> South
    West  <-> East

    a to b: ok
    b to c: ok
    a to c: ok (3段論法)

    """
    
    d = zip([0, 0, 1, -1],
            [1, -1, 0, 0])
    d = list(d)
    to = {"

    b = []
    for _ in range(H):
        b2 = []
        for _ in range(W):
            b2.append([None] * 4)
        b.append(b2)

    blacks = {}
    for y in range(H):
        for x in range(W):
            src = S[y][x]
            if src == "
                blacks[(y, x)] = -1

            for i, (dx, dy) in enumerate(d):
                nx = x + dx
                ny = y + dy

                valid = 0 <= nx < W and 0 <= ny < H
                if not valid:
                    continue

                if S[ny][nx] == to[src]:
                    b[y][x][i] = (ny, nx)

    ans = 0
    
    for (y, x), _ in blacks.items():
        
        bs = [(y, x)]
        
        used_bs = {}
        used_ws = {}
        while bs:
            by, bx = bs.pop()
            used_bs[(by, bx)] = None

            
            whites = []
            for pos in b[by][bx]:
                if pos and pos not in used_ws:
                    ans += 1
                    whites.append(pos)
                    used_ws[pos] = None

            
            for wy, wx in whites:
                for pos in b[wy][wx]:
                    if pos and pos not in used_bs:
                        bs.append(pos)

    return ans


if __name__ == '__main__':
    main()

Solution (Python):
H, W = [int(x) for x in input().strip().split(" ")]

import sys
sys.setrecursionlimit(1000000)
b = []
bset = set()
wset = set()
i = 0
j = 0
for line in sys.stdin:
    b.append(line.strip())
    for s in line.strip():
        if s == "
            bset.add((i, j))
        else:
            wset.add((i, j))
        j += 1
    j = 0
    i += 1

fbset = set()
fwset = set()

def it_b(i, j):
    fbset.add((i, j))
    totalb = 1
    totalw = 0
    bset.remove((i, j))
    
    if i - 1 >= 0:
        if b[i-1][j] == "." and (i-1, j) not in fwset:
            rb, rw = it_w(i-1, j)
            totalb += rb
            totalw += rw
    if j - 1 >= 0:
        if b[i][j-1] == "." and (i, j-1) not in fwset:
            rb, rw = it_w(i, j-1)
            totalb += rb
            totalw += rw
    if i + 1 <= H-1:
        if b[i+1][j] == "." and (i+1, j) not in fwset:
            rb, rw = it_w(i+1, j)
            totalb += rb
            totalw += rw
    if j + 1 <= W-1:
        if b[i][j+1] == "." and (i, j+1) not in fwset:
            rb, rw = it_w(i, j+1)
            totalb += rb
            totalw += rw
    return totalb, totalw

def it_w(i, j):
    fwset.add((i, j))
    totalb = 0
    totalw = 1
    
    if i - 1 >= 0:
        if b[i-1][j] == "
            rb, rw = it_b(i-1, j)
            totalb += rb
            totalw += rw
    if j - 1 >= 0:
        if b[i][j-1] == "
            rb, rw = it_b(i, j-1)
            totalb += rb
            totalw += rw
    if i + 1 <= H-1:
        if b[i+1][j] == "
            rb, rw = it_b(i+1, j)
            totalb += rb
            totalw += rw
    if j + 1 <= W-1:
        if b[i][j+1] == "
            rb, rw = it_b(i, j+1)
            totalb += rb
            totalw += rw
    return totalb, totalw

t = 0
while True:
    if len(bset) == 0:
        break
    x = bset.pop()
    bset.add(x)
    rb, rw = it_b(x[0], x[1])
    t += rb * rw
print(t)

Solution (Python):


import numpy as np
import sys
sys.setrecursionlimit(1000000)

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


def count_answer(x,y,num_b,num_w):
    

    if S[x][y] == "
        num_b += 1
    else:
        num_w += 1
    used[x][y] = 1
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    
    for i in range(4):
        next_x = x + dx[i]
        next_y = y + dy[i]
        
        if next_x == -1 or next_y == -1 or next_x >= H or next_y >= W:
            pass
        elif used[next_x,next_y] == 1:
            pass
        elif S[next_x][next_y] != S[x][y]:
            num_b,num_w = count_answer(next_x,next_y,num_b,num_w)
    return num_b,num_w

answer = 0
used = np.zeros((H,W))
for i in range(H):
    for j in range(W):
        if used[i][j] == 1:
            continue
        num_b = 0
        num_w = 0
        if S[i][j] == "
            num_b,num_w  = count_answer(i,j,num_b,num_w)
            answer += num_b*num_w
print(answer)

Solution (Python):
h,w=list(map(int,input().split()))
ans=0
arr=[]
for _ in range(h):
    arr+=[list(input())]
visited={}
for i in range(h):
    for j in range(w):
        visited[(i,j)]=False
for i in range(h):
    for j in range(w):
        stack=[(i,j)]
        visited[(i,j)]=True
        numblack=0
        numwhite=0
        while stack!=[]:
            current=stack.pop()
            if arr[current[0]][current[1]]=='.':
                numwhite+=1
            else:
                numblack+=1
            children=[]
            a,b=current[0],current[1]
            if a-1>=0:
                children+=[(a-1,b)]
            if a+1<h:
                children+=[(a+1,b)]
            if b-1>=0:
                children+=[(a,b-1)]
            if b+1<w:
                children+=[(a,b+1)]
            for child in children:
                if not visited[child] and (arr[child[0]][child[1]]!=arr[current[0]][current[1]]):
                    visited[child]=True
                    stack+=[child]
        ans+=numblack*numwhite
print(ans)

Solution (Python):
from collections import deque

MAX_N = 400
di = (1, 0, -1, 0)
dj = (0, 1, 0, -1)

def can_extend(i, j, d, H, W, color):
    ni = i + di[d]
    nj = j + dj[d]
    if not (0 <= ni < H and 0 <= nj < W):
        return False
    if color[i][j] == color[ni][nj]:
        return False
    return True


def solve(H, W, color):
    ans = 0
    is_used = [[False] * MAX_N for i in range(MAX_N)]
    for i in range(H):
        for j in range(W):
            if is_used[i][j]:
                continue
            black = 0
            white = 0
            que = deque()
            is_used[i][j] = True
            que.append((i, j))
            while que:
                p = que.popleft()
                ci = p[0]
                cj = p[1]
                if color[ci][cj]:
                    black += 1
                else:
                    white += 1

                for d in range(4):
                    if not can_extend(ci, cj, d, H, W, color):
                        continue
                    ni = ci + di[d]
                    nj = cj + dj[d]
                    if is_used[ni][nj]:
                        continue
                    is_used[ni][nj] = True
                    que.append((ni, nj))

            ans += black * white

    return ans


H, W = [int(v) for v in input().split()]
s = [input() for i in range(H)]
color = []
for row in s:
    color.append([v == '

print(solve(H, W, color))

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

def func(h,w): 
    move = [(0,-1), (-1,0),(0,1), (1,0)]
    w_cnt = 0
    b_cnt = 0
    que = deque()
    que.append((h,w))
    while len(que) > 0:
        xh, xw = que.popleft()
        if visited[xh][xw] == 0:
            visited[xh][xw] = 1
            if s[xh][xw] == "
                b_cnt += 1
            else:
                w_cnt += 1
        else:
            continue
        for mh, mw in move:
            if 0 <= xh + mh < H and 0 <= xw + mw <W:
                if s[xh][xw] != s[xh+mh][xw+mw] and visited[xh+mh][xw+mw] == 0:
                    que.append((xh+mh,xw+mw))
    return b_cnt, w_cnt

cnt = 0
visited = [[0 for _ in range(W)] for _ in range(H)]

for i in range(H):
    for j in range(W):
        if s[i][j] == "
            b_cnt, w_cnt = func(i,j)
            cnt += b_cnt * w_cnt

print(cnt)

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

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

used = [[0]*w for _ in range(h)]
dx=[ 0, 1, 0,-1]
dy=[ 1, 0,-1, 0]

def dfs(x, y):
    global numb, numw 
    
    used[x][y] = 1
    
    if board[x][y] == '
        numb += 1
    else:
        numw += 1
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or nx >= h or ny < 0 or ny >= w or used[nx][ny] == 1: continue 
        if board[x][y]!=board[nx][ny]: 
            dfs(nx,ny)
    return 

ans=0
for i in range(h):
    for j in range(w):
        numw = 0
        numb = 0
        if used[i][j] == 1: continue 
        dfs(i,j)
        ans += numw*numb

print(ans)

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

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

    graph = [[[]for _ in range(W)] for _ in range(H)]
    visited = [[0 for _ in range(W)] for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if S[i][j] == ".":
                continue
            if S[max(i - 1, 0)][j] == ".":
                graph[max(i - 1, 0)][j].append((i,j))
                graph[i][j].append((max(i - 1, 0),j))

            if S[min(i+1, H-1)][j] == ".":
                graph[min(i + 1, H - 1)][j].append((i,j))
                graph[i][j].append((min(i + 1, H - 1),j))

            if S[i][max(j - 1, 0)] == ".":
                graph[i][max(j - 1, 0)].append((i,j))
                graph[i][j].append((i,max(j - 1, 0)))

            if S[i][min(j+1, W-1)] == ".":
                graph[i][min(j + 1, W - 1)].append((i,j))
                graph[i][j].append((i,min(j+1, W-1)))

    bw = [0] * 2
    def dfs(g):
        for a,b in g:
            if visited[a][b] == 1:
                continue
            visited[a][b] = 1
            if S[a][b] == ".":
                bw[0] += 1
            else:
                bw[1] += 1
            dfs(graph[a][b])

    ans = 0
    for i in range(H):
        for j in range(W):
            if visited[i][j] == 1:
                continue
            bw[0], bw[1] = 0, 0
            dfs(graph[i][j])
            ans += bw[0] * bw[1]

    return ans

print(m())