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

"""
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 sys
from atexit import register
from bisect import bisect_left, bisect_right







if sys.version_info[0] < 3:
    
    from io import BytesIO as stream
    
else:
    
    from io import StringIO as stream
    
    


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

Solution (Python):
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

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)
    
    bw = [0, 0]
    while len(Open)>0:
        qq = Open.popleft()
        Close.add(qq)
        y, x = qq
        
        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))

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

Solution (Python):


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 == '


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

Solution (Python):
from collections import deque

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


def count(start, S, H, W, tested):
    if tested[start[0]][start[1]]:
        return 0
    q = deque()
    q.append((start[0], start[1], "
    white = 0
    black = 0
    while(len(q)):
        i, j, color = q.popleft()
        if tested[i][j]:
            continue
        tested[i][j] = True
        if color == ".":
            white += 1
            ncolor = "
        else:  
            black += 1
            ncolor = "."
        for d in DIRECTIONS:
            ni = i + d[0]
            nj = j + d[1]
            if 0 <= ni and ni < H and 0 <= nj and nj < W and S[ni][nj] == ncolor:
                q.append((ni, nj, ncolor))
    return black * white


def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    tested = [[False] * W for _ in range(H)]
    retval = 0
    for i in range(H):
        for j in range(W):
            if(S[i][j] == "
                retval += count((i, j), S, H, W, tested)
    print(retval)


if __name__ == "__main__":
    main()

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

i = 0
color = []
edge = dd(lambda: dd(int))
for h in range(H):
  for w in range(W):
    color.append(S[h][w])
    if w != 0:
      j = i-1
      if S[h][w-1] != S[h][w]:
        edge[i][j] = 1
        edge[j][i] = 1
    if h != 0:
      j = i-W
      if S[h-1][w] != S[h][w]:
        edge[i][j] = 1
        edge[j][i] = 1
    i += 1

visited = [False] * i
ans = 0
for k in range(i):
  if not visited[k]:
    count = { '
    queue = set([k])
    while queue:
      j = queue.pop()
      count[color[j]] += 1
      visited[j] = True
      for dst in edge[j]:
        if not visited[dst]:
          queue.add(dst)
    ans += count['
print(ans)

Solution (Python):
import sys
fin = sys.stdin.readline
sys.setrecursionlimit(300000)
from collections import defaultdict


H, W = [int(elem) for elem in fin().split()]
S = [tuple(elem for elem in fin()[:-1]) for _ in range(H)]


visited = [[False] * W for _ in range(H)]
directions = ((-1, 0), (1, 0), (0, -1), (0, 1))
group_numblack = defaultdict(int)
group_numwhite = defaultdict(int)

def dfs_visit(i, j, visited, group):
    if visited[i][j]:
        return
    visited[i][j] = True
    if S[i][j] == "
        group_numblack[group] += 1
    else:
        group_numwhite[group] += 1
    for di, dj in directions:
        next_i, next_j = i + di, j + dj
        if next_i < 0 or next_i >= H or next_j < 0 or next_j >= W:
            continue
        elif visited[next_i][next_j]:
            continue
        elif S[i][j] == S[next_i][next_j]:
            continue
        else:
            dfs_visit(next_i, next_j, visited, group)


group = 0
for i in range(H):
    for j in range(W):
        dfs_visit(i, j, visited, group)
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        group += 1




num_pairs = 0
for group in group_numblack.keys():
    num_pairs += group_numblack[group] * group_numwhite[group]
print(num_pairs)

Solution (Python):
import sys
sys.setrecursionlimit(500*500)

h, w = map(int, input().split())
grid = []
seen = [[False for y in range(w)] for x in range(h)]

for x in range(h):
    grid.append(input())



blackSeen = 0
whiteSeen = 0
def countFrom(a, b, lastColor):
    global blackSeen, whiteSeen
    if not (0 <= a < h and 0 <= b < w):
        return
    if seen[a][b]:
        return
    
    

    thisColor = (1 if grid[a][b] == "." else -1)

    if grid[a][b] == "
        blackSeen += 1
    elif grid[a][b] == "." and lastColor != 1:
        whiteSeen += 1
    else:
        return
    seen[a][b] = True

    countFrom(a+1, b, thisColor)
    countFrom(a-1, b, thisColor)
    countFrom(a, b+1, thisColor)
    countFrom(a, b-1, thisColor)

tot = 0
for x in range(h):
    for y in range(w):
        blackSeen = 0
        whiteSeen = 0
        countFrom(x, y, 0)
        
        tot += blackSeen * whiteSeen

print(tot)

Solution (Python):

TTYPE = 0
X = 1
Y = 2

def main():
    buf = input()
    buflist = buf.split()
    H = int(buflist[0])
    W = int(buflist[1])
    S = []
    for i in range(H):
        buf = input()
        S.append(buf)
    searched = []
    for i in range(H):
        searched.append([])
        for j in range(W):
            searched[i].append(False)
    group_white = []
    group_black = []
    for i in range(H):
        for j in range(W):
            if searched[i][j]:
                continue
            else:
                search_stack = [[S[i][j], i, j]]
                group_white.append(0)
                group_black.append(0)
                while len(search_stack) > 0:
                    target = search_stack.pop()
                    if searched[target[X]][target[Y]]:
                        continue
                    if target[TTYPE] == '.':
                        group_white[-1] += 1
                    else:
                        group_black[-1] += 1
                    searched[target[X]][target[Y]] = True
                    if target[X] > 0:
                        if not searched[target[X]-1][target[Y]] and ((target[TTYPE] == '.' and S[target[X]-1][target[Y]] == "
                            search_stack.append([S[target[X]-1][target[Y]], target[X]-1, target[Y]])
                    if target[Y] > 0:
                        if not searched[target[X]][target[Y]-1] and ((target[TTYPE] == '.' and S[target[X]][target[Y]-1] == "
                            search_stack.append([S[target[X]][target[Y]-1], target[X], target[Y]-1])
                    if target[X] < H-1:
                        if not searched[target[X]+1][target[Y]] and ((target[TTYPE] == '.' and S[target[X]+1][target[Y]] == "
                            search_stack.append([S[target[X]+1][target[Y]], target[X]+1, target[Y]])
                    if target[Y] < W-1:
                        if not searched[target[X]][target[Y]+1] and ((target[TTYPE] == '.' and S[target[X]][target[Y]+1] == "
                            search_stack.append([S[target[X]][target[Y]+1], target[X], target[Y]+1])
    total = 0
    for i in range(len(group_black)):
        total += group_black[i] * group_white[i]
    print(total)

if __name__ == '__main__':
    main()

Solution (Python):
H, W = map(int, input().split())
T = [[] for i in range(H)]
for i in range(H):
    a = list(input())
    T[i] = a

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

rec = 0
ans = [[0] * (H * W + 5) for i in range(2)]
for i in range(H):
    for j in range(W):
        if T[i][j] == "
            rec += 1
            S[i][j] = rec
            ans[1][rec] += 1
            pre = "
            que = [(i, j, pre)]
            while que:
                x, y, pre = que.pop()
                for dx, dy in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
                    nx, ny = x + dx, y + dy
                    if pre == "
                        if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == -1 and T[nx][ny] == ".":
                            S[nx][ny] = rec
                            ans[0][rec] += 1
                            que.append((nx, ny, "."))
                    else:
                        if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == -1 and T[nx][ny] == "
                            S[nx][ny] = rec
                            ans[1][rec] += 1
                            que.append((nx, ny, "


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

print(num1)

Solution (Python):
h,w = map(int,input().split())
s = []
point = [[0 for j in range(0,w+2)] for i in range(0,h+2)]
ans = []
for _ in range(h):
    S = input()
    s.append(S)
for i in range(0,h+2):
    point[i][0] = 1
    point[i][w+1] = 1
for i in range(0,w+2):
    point[0][i] = 1
    point[h+1][i] = 1

def haba(y,x):
    point[y][x] = 1
    q = []
    q.append((y,x,s[y-1][x-1]))
    while len(q) > 0:
        (y,x,ss) = q.pop(0)
        nextPoint = [[y+1,x],[y,x+1],[y-1,x],[y,x-1]]
        for ny,nx in nextPoint:
            if point[ny][nx] != 0:
                continue
            if ss == "
                ans[-1][0] += 1
                point[ny][nx] = 1
                q.append((ny,nx,s[ny-1][nx-1]))
            if ss == "." and s[ny-1][nx-1] == "
                ans[-1][1] += 1
                point[ny][nx] = 1
                q.append((ny,nx,s[ny-1][nx-1]))
for i in range(1,h+1):
    for j in range(1,w+1):
        if point[i][j] == 1:
            continue
        if s[i-1][j-1] == ".":
            ans.append([1,0])
        else:
            ans.append([0,1])
        haba(i,j)
sum = 0
for i,j in ans:
    sum += i*j
print(sum)

Solution (Python):
dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
H,W = map(int,input().split())
s = []
for i in range(H):
    s.append(input())

goto = [[False]*W for _ in range(H)]
count = 0
for h in range(H):
    for w in range(W):
        black = 0
        white = 0
        if s[h][w] == '
            black = 1
            goto[h][w] = True
            stack = [[h,w,'
            while(stack!=[]):
                tarr = stack.pop()
                for dx,dy in dxdy:
                    if tarr[0]+dx >= 0 and tarr[0]+dx < H and tarr[1]+dy >= 0 and tarr[1]+dy < W:
                        if s[tarr[0]+dx][tarr[1]+dy] != tarr[2] and goto[tarr[0]+dx][tarr[1]+dy] == False:
                            stack.append([tarr[0]+dx,tarr[1]+dy,s[tarr[0]+dx][tarr[1]+dy]])
                            goto[tarr[0]+dx][tarr[1]+dy] = True
                            if s[tarr[0]+dx][tarr[1]+dy] == '
                                black += 1
                            else:
                                white += 1
        count += black*white
print(count)

Solution (Python):




import sys

sys.setrecursionlimit(1000000)

h,W = [int(i) for i in input().split()]

board = []
for _ in range(h):
    board.append(input())

checked = [[0]*W for i in range(h)]

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

ans = 0

def dfs(x,y,b,w):
    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 checked[nx][ny]==1:
            continue
        if board[x][y] == board[nx][ny]:
            continue

        checked[nx][ny]=1
        if board[nx][ny] == '
            b+=1
        else:
            w+=1
        b1,w1 = dfs(nx, ny,0,0)
        b+=b1
        w+=w1

    return b,w



for i in range(h):
    for j in range(W):
        if checked[i][j] == 1:
            continue
        checked[i][j] = 1
        if board[i][j] == '
            b2 = 1; w2=0
        else:
            b2 = 0; w2=1
        b1,w1 = dfs(i,j,b2,w2)

        ans += b1*w1

print(ans)

Solution (Python):


II = lambda: int(input())
MI = lambda: map(int, input().split())


def make_cells(h, w):
    cells = set()
    for i in range(h):
        for j in range(w):
            cells.add((i, j))
    return cells

def make_bcells(h, w, m):
    cells = set()
    for i in range(h):
        for j in range(w):
            if m[i][j]:
                cells.add((i, j))
    return cells


def search(sc, bcells_yet, m, H, W):
    valid = lambda cell: cell[0] >= 0 and cell[0] < H and cell[1] >= 0 and cell[1] < W
    color = lambda cell: m[cell[0]][cell[1]]

    ccnt = {0:0, 1:1}
    wcells_searched = set()

    q = set()
    q.add(sc)
    while len(q) > 0:
        c = q.pop()
        dirs = filter(valid, [(c[0] + 1, c[1]), (c[0] - 1, c[1]), (c[0], c[1] + 1), (c[0], c[1] - 1)])
        for nc in dirs:
            if color(nc) != color(c):
                if color(nc) and nc in bcells_yet:
                    bcells_yet.remove(nc)
                    ccnt[1] += 1
                    q.add(nc)
                elif not color(nc) and nc not in wcells_searched:
                    wcells_searched.add(nc)
                    ccnt[0] += 1
                    q.add(nc)
    return ccnt[0] * ccnt[1]


def main():
    H, W = MI()

    m = []
    for h in range(H):
        m.append(tuple(map(lambda c:c == "

    bcells = make_bcells(H, W, m)

    ans = 0
    while len(bcells) > 0:
        ans += search(bcells.pop(), bcells, m, H, W)
    return ans


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

Solution (Python):
def main():
    from collections import defaultdict
    import sys
    sys.setrecursionlimit(10 ** 9)
    
    H, W = list(map(int, raw_input().split()))
    G = [list(raw_input()) for i in range(H)]
    
    Visited = [[0] * W for i in range(H)]
    direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    
    
    def dfs(ny, nx, color):
        for dy, dx in direction:
            if not ((0 <= ny + dy < H) and (0 <= nx + dx < W)):
                continue
    
            if G[ny + dy][nx + dx] == G[ny][nx]:
                continue
    
            if Visited[ny + dy][nx + dx] != 0:
                continue
    
            if G[ny + dy][nx + dx] == '
                Visited[ny + dy][nx + dx] = color
            else:
                Visited[ny + dy][nx + dx] = -color
    
            dfs(ny + dy, nx + dx, color)
    
    
    Color = 1
    for y in range(H):
        for x in range(W):
            if Visited[y][x] == 0:
                if G[y][x] == '
                    Visited[y][x] = Color
                else:
                    Visited[y][x] = -Color
                dfs(y, x, Color)
                Color += 1
    
    D = defaultdict(int)
    for i in range(1, Color + 1):
        D[i] = 0
        D[-i] = 0
    
    for row in Visited:
        for data in row:
            D[data] += 1
    
    ans = 0
    for key in D.keys():
        ans += D[key] * D[-key]
    
    print(ans // 2)
    
main()

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

def main():
    h, w = map(int, input().split())
    mp = ["X" * (w + 2)] + ["X" + input() + "X" for _ in range(h)] + ["X" * (w + 2)]
    checked = [[False] * (w + 2) for _ in range(h + 2)]
    vec = ((1, 0), (0, -1), (-1, 0), (0, 1))


    def search(stack):
        x, y = stack.pop()
        if mp[y][x] == "
            b_cnt = 1
            w_cnt = 0
            another = "."
        else:
            b_cnt = 0
            w_cnt = 1
            another = "
        for dx, dy in vec:
            nx, ny = x + dx, y + dy
            if not checked[ny][nx] and mp[ny][nx] == another:
                checked[ny][nx] = True
                stack.append((nx, ny))
        return w_cnt, b_cnt

    ans = 0
    for y in range(1, h + 1):
        for x in range(1, w + 1):
            if not checked[y][x]:
                checked[y][x] = True
                stack = []
                stack.append((x, y))
                w_cnt = b_cnt = 0
                while stack:
                    w_add, b_add = search(stack)
                    w_cnt += w_add
                    b_cnt += b_add
                ans += w_cnt * b_cnt

    print(ans)

main()

Solution (Python):
import sys

sys.setrecursionlimit(1000*1000)

H, W = map(int, input().split(" "))
map_info = [input() for i in range(H)]

visit = [[False for j in range(W)] for i in range(H)]
ans = 0


def search(i, j, want_color):
    if i < 0 or i >= H:
        return
    if j < 0 or j >= W:
        return
    if visit[i][j]:
        return
    this_color = map_info[i][j]
    if want_color != this_color:
        return

    global white
    global black

    visit[i][j] = True
    if this_color == '.':
        white += 1
        next_color = '
    else:
        black += 1
        next_color = '.'
    search(i, j+1, next_color)
    search(i, j-1, next_color)
    search(i+1, j, next_color)
    search(i-1, j, next_color)


for i in range(H):
    for j in range(W):
        white = 0
        black = 0
        search(i, j, map_info[i][j])
        ans += black * white
print(ans)

Solution (Python):
def root(x):
    if parent[x] == x:
        return(x)
    else:
        parent[x] = root(parent[x])
        return(parent[x])


def same(x, y):
    return(root(x) == root(y))


def union(x, y):
    x = root(x)
    y = root(y)
    if(x == y):
        return False

    parent[x] = min(x, y)
    parent[y] = min(x, y)
    return True





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

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

neighbor = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for h in range(H):
    for w in range(W):
        for px, py in neighbor:
            tx = w + px
            ty = h + py
            
            if tx < 0 or tx >= W or ty < 0 or ty >= H:
                continue
            
            
            if {S[h][w], S[ty][tx]} == {"
                union(h*W+w,ty*W+tx)

ans = {root(r):{"
for i in range(H*W):
    ans[root(i)][S[i//W][i%W]] += 1



print(sum(v["

Solution (Python):
from collections import deque

H, W = map(int, input().split())
s = ["X" * (W+2)] + ["X" + input() + "X" for _ in range(H)] + ["X" * (W+2)]
visited = [[-1 for _ in range(W+2)] for _ in range(H+2)]

DH = [1, 0, -1, 0]
DW = [0, 1, 0, -1]

ans = 0
def bfs(start, num):
	global ans
	dot, sharp = 0, 0
	que = deque([start])
	
	visited[start[0]][start[1]] = num
	
	while que:
		label = que.pop()
		h, w = label[0], label[1]
		if s[h][w] == ".":
			dot += 1
		elif s[h][w] == "
			sharp += 1
		
			
		for dh, dw in zip(DH, DW):
			if s[h][w] == ".":
				if s[h+dh][w+dw] == "
					que.appendleft([h+dh, w+dw])
					visited[h+dh][w+dw] = num
			elif s[h][w] == "
				if s[h+dh][w+dw] == "." and visited[h+dh][w+dw] == -1:
					que.appendleft([h+dh, w+dw])
					visited[h+dh][w+dw] = num
	
	return dot*sharp

k = 0
for i in range(1, H+1):
	for j in range(1, W+1):
		if visited[i][j] == -1:
			ans += bfs([i, j], k)

print(ans)

Solution (Python):

import collections, atexit, math, sys, bisect 

sys.setrecursionlimit(1000000)
def getIntList():
    return list(map(int, input().split()))    

try :
    
    import numpy
    def dprint(*args, **kwargs):
        
        
        print(*args,  file=sys.stderr)
    dprint('debug mode')
except Exception:
    def dprint(*args, **kwargs):
        pass



inId = 0
outId = 0
if inId>0:
    dprint('use input', inId)
    sys.stdin = open('input'+ str(inId) + '.txt', 'r') 
if outId>0:
    dprint('use output', outId)
    sys.stdout = open('stdout'+ str(outId) + '.txt', 'w') 
    atexit.register(lambda :sys.stdout.close())     
    
H, W = getIntList()

zs = []
dprint(H,W)
for i in range(H):
    s = input()
    zs.append(s)
    dprint(s)
zu = [  [(i,j) for j in range(W) ]  for i in range(H) ]
dprint(11111)
def getr(p):
    
    if p == zu[ p[0] ] [p[1] ]:
        return p
    np = getr(zu[ p[0] ] [p[1] ])
    zu[ p[0] ] [ p[1] ] = np
    return np
dprint(11111)
def uuu( p0, p1) :
    p0 = getr(p0)
    p1 = getr(p1)
    
    zu[ p0[0] ] [p0[1] ] =  p1
dprint(zu)
dprint(zs)
for i in range(H):
    for j in range(W): 
        if i>0:
            if zs[i-1][j] != zs[i][j]:
                uuu( (i-1,j), (i,j) )
        if j>0:
            if zs[i][j-1] != zs[i][j]:
                uuu( (i,j-1), (i,j) )
         
dprint(11111) 
zr = dict()
dprint(11111)
for i in range(H):
    for j in range(W):
        p = (i,j)
        p = getr(p)
        if p not in zr:
            zr[p] = [0,0]
        if zs[i][j] == '.':
            zr[p][0] +=1
        else:
            zr[p][1] +=1
dprint(zr)            
r = 0
for x in zr:
    r += zr[x][0] * zr[x][1]
    
print(r)

Solution (Python):
from collections import defaultdict
def find(A,x):
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a
 
def union(A, x, y):

    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    A[y] = bx
    A[by] = bx

H, W = map( int, input().split())
S = [ input() for _ in range(H)]
A = [ i for i in range(H*W)]
D = defaultdict( lambda: (0,0))
for i in range(H):
    for j in range(W):
        if i > 0 and H != 1:
            if S[i][j] != S[i-1][j]:
                union(A, i*W+j, (i-1)*W + j)
        if i < H-1 and H != 1:
            if S[i][j] != S[i+1][j]:
                union(A, i*W+j, (i+1)*W + j)
        if j > 0 and W != 1:
            if S[i][j] != S[i][j-1]:
                union( A, i*W+j, i*W + j-1)
        if j < W-1 and W != 1:
            if S[i][j] != S[i][j+1]:
                union( A, i*W+j, i*W+j+1)
for i in range(H):
    for j in range(W):
        a, b = D[ find(A,i*W+j)]
        if S[i][j] == "
            D[ find(A,i*W+j)] = (a+1,b)
        else:
            D[ find(A,i*W+j)] = (a,b+1)
ans = 0
for d in D:
    a, b = D[d]
    ans += a*b
print(ans)

Solution (Python):
from collections import deque

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

CHECK=[[0]*W for i in range(H)]
ANSLIST=[]

for i in range(H):
    for j in range(W):
        if CHECK[i][j]==1:
            continue
        QUE = deque()
        QUE.append((i,j))
        BC=0
        WC=0

        while QUE:
            x,y=QUE.pop()
            if CHECK[x][y]==1:
                continue

            
            CHECK[x][y]=1
            

            if S[x][y]=="
                BC+=1
            else:
                WC+=1


            for k,l in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
                
                if k<0 or l<0 or k>=H or l>=W:
                    
                    continue
                if CHECK[k][l]==1:
                    continue

                if S[k][l]!=S[x][y]:
                    QUE.appendleft((k,l))
                    

        ANSLIST.append((BC,WC))
        

ANS=0
for a,b in ANSLIST:
    ANS+=a*b

print(ANS)

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

move=((1,0),(0,1),(-1,0),(0,-1))


def dfs(used,mat,node,nums):
    y,x=node
    color=mat[y][x]
    if used[y][x]==1 or color=='!':
        return
    
    used[y][x]=1
    nums[color]+=1
    for i,j in move:
        if mat[y+i][x+j]!=color and mat[y+i][x+j] != '!':
            dfs(used,mat,(y+i,x+j),nums)


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

grid=['!'*(W+2)]
used=[[0 for _ in range(W+2)] for _ in range(H+2)]

for i in range(H):
    grid.append('!'+input()+'!')
grid.append('!'*(W+2))

ans=0
for i in range(H+2):
    for j in range(W+2):
        nums={'
        dfs(used,grid,(i,j),nums)
        ans+=nums['
print(ans)

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

H, W = map(int, input().split())
S = [input() for y in range(H)]
visited = [[False] * W for y in range(H)]

def color(y, x):
    if y < 0 or H <= y or x < 0 or W <= x or visited[y][x]:
        return "@"
    else:
        return S[y][x]


def dfs(y, x):
    b = 0
    w = 0
    nxt = "n"
    if color(y, x) == ".":
        w = 1
        nxt = "
    elif color(y, x) == "
        b = 1
        nxt = "."
    
    visited[y][x] = True
    if color(y - 1, x) == nxt:
        _b, _w = dfs(y - 1, x)
        b += _b
        w += _w
    if color(y + 1, x) == nxt:
        _b, _w = dfs(y + 1, x)
        b += _b
        w += _w
    if color(y, x - 1) == nxt:
        _b, _w = dfs(y, x - 1)
        b += _b
        w += _w
    if color(y, x + 1) == nxt:
        _b, _w = dfs(y, x + 1)
        b += _b
        w += _w

    return (b, w)

    
ans = 0
for y in range(H):
    for x in range(W):
        b, w = dfs(y, x)
        ans += b * w

print(ans)