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: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)


class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n + 1)]
        self.rank = [0 for _ in range(n + 1)]
        self.size = [1] * (n + 1)

    def find(self, x):
        # If x is root
        if self.parent[x] == x:
            return x
        # If x is not root, search again by using x's parent
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        # Make an edge from the root of lower tree to the root of higher tree
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.size[y] += self.size[x]
        else:
            self.parent[y] = x
            self.size[x] += self.size[y]
            # If the height of tree the tree is the same, increase one of the heights by 1
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

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


H, W = map(int, input().split())
s_list = []
for i in range(H):
    s_list.append(input())
check = [[0 for _ in range(W)] for _ in range(H)]

brack_list = []
union_find = UnionFind(H * W)
for i in range(H):
    for j in range(W):
        if s_list[i][j] == "#":
            brack_list.append(i * W + j)
            if i - 1 >= 0 and s_list[i - 1][j] == ".":
                union_find.union(i * W + j, (i - 1) * W + j)
            if i + 1 < H and s_list[i + 1][j] == ".":
                union_find.union(i * W + j, (i + 1) * W + j)
            if j - 1 >= 0 and s_list[i][j - 1] == ".":
                union_find.union(i * W + j, i * W + j - 1)
            if j + 1 < W and s_list[i][j + 1] == ".":
                union_find.union(i * W + j, i * W + j + 1)


black = {}
white = {}
for i in range(H):
    for j in range(W):
        p = union_find.find(i * W + j)
        if s_list[i][j] == "#":
            if p in black:
                black[p] += 1
            else:
                black[p] = 1
        else:
            if p in white:
                white[p] += 1
            else:
                white[p] = 1

p = set(union_find.parent[:-1])
count = 0
for i in p:
    count += white[i] * black[i]
print(count)

Submission status: Runtime Error

Solution code:
def search(search_map, group, current_h, current_w, group_index):
    num = 0
    if current_h in search_map:
        search_map[current_h][current_w] = True
    else:
        search_map[current_h] = {}
        search_map[current_h][current_w] = True
    search_map[current_h][current_w] = True
    current = s_map[current_h][current_w]
    if (current == '.'):
        num += 1
    else:
        group[current_h][current_w] = group_index
    # 上
    if current_h > 0:
        next_h = current_h-1
        next_w = current_w
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    # 下
    if current_h < H-1:
        next_h = current_h+1
        next_w = current_w
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    # 左
    if current_w > 0:
        next_h = current_h
        next_w = current_w-1
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    # 右
    if current_w < W-1:
        next_h = current_h
        next_w = current_w+1
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    return num


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

s_map = {}
group = {}
searched_map = {}


for i in range(H):
    s_map[i] = {}
    group[i] = {}
    w = list(A[i])
    for j in range(W):
        s_map[i][j] = w[j]
        group[i][j] = 0

ans = 0
group_index = 1
group_cnt = {}
group_cnt[0] = 0
for i in range(H):
    for j in range(W):
        if s_map[i][j] == '#':
            if group[i][j] != 0:
                ans += group_cnt[group[i][j]]
            else:
                cnt = search({}, group, i, j, group_index)
                group_cnt[group_index] = cnt
                group_index += 1
                ans += cnt
print(ans)

'''
1 1
#
'''

'''
1 1
.
'''

'''
4 5
#####
#...#
#...#
#####
'''

'''
5 5
.....
.....
.###.
.###.
.....
'''


'''
3 1
#
.
#
'''


'''
3 3
###
#.#
###
'''

'''
5 5
##.##
#.###
####.
##.#.
####.
'''

'''
5 4
#.#.
####
####
#.##
##.#
'''

'''
5 4
#.#.
####
#.#.
####
####
'''

'''
5 4
....
.#..
..#.
...#
#.#.
'''

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(20000)
#input = sys.stdin.readline
h,w = map(int,input().split())
a = [[j for j in input()] for i in range(h)]
used = [[0]*w for i in range(h)]
def dfs(x,y):
    if used[x][y]:
        return 0
    global go
    used[x][y] = 1
    if x-1 >=0 and a[x-1][y] != a[x][y]:
            go.add((x-1,y))
            dfs(x-1,y)
    if y-1 >=0 and a[x][y-1] != a[x][y]:
            go.add((x,y-1))
            dfs(x,y-1)
    if x+1 <h and a[x+1][y] != a[x][y]:
            go.add((x+1,y))      
            dfs(x+1,y)
    if y+1 <w and a[x][y+1] != a[x][y]:
            go.add((x,y+1))
            dfs(x,y+1)
ans = 0
for i in range(h):
    for j in range(w):
        go = set()
        if used[i][j]:
            continue
        dfs(i,j)
        kuro = 0
        siro = 0
        for k,l in go:
            if a[k][l] == "#":
                kuro += 1
            else:
                siro += 1
        ans += kuro*siro

print(ans)

Submission status: Runtime Error

Solution code:
c=0
x=[-1,0,1,0]
y=[0,-1,0,1]
buf=[]
p=0
def count(h,w,S,table,H,W):
    global buf,x,y,p
    if buf or p==0:
        for i in range(4):
            if h+y[i]>=0 and h+y[i]<H and w+x[i]>=0 and w+x[i]<W:
                if table[h+y[i]][w+x[i]]==-1:
                    if S[h][w]=='.' and S[h+y[i]][w+x[i]]=='#':
                        table[h+y[i]][w+x[i]]=table[h][w]+1
                        buf.append([h+y[i],w+x[i]])
                    elif S[h][w]=='#' and S[h+y[i]][w+x[i]]=='.':
                        table[h+y[i]][w+x[i]]=table[h][w]+1
                        buf.append([h+y[i],w+x[i]])
        if buf:
            a=buf.pop(0)
            count(a[0],a[1],S,table,H,W)
    elif not(buf) and p==0:
        p+=1
        count(h,w,S,table,H,W)

H,W=map(int,input().split())
S=[]
for i in range(H):
    S.append(input())
for h in range(H):
    for w in range(W):
        if S[h][w]=='#':
            table=[[-1 for j in range(W)] for i in range(H)]
            table[h][w]=0
            p=0
            count(h,w,S,table,H,W)
            for k in range(H):
                for l in range(W):
                    if table[k][l]%2==1 and table[k][l]!=-1:
                        c+=1
print(c)

Submission status: Runtime Error

Solution code:
def search(search_map, group, current_h, current_w, group_index):
    num = 0
    if current_h in search_map:
        search_map[current_h]
    else:
        search_map[current_h] = {}
        search_map[current_h][current_w] = True
    search_map[current_h][current_w] = True
    current = s_map[current_h][current_w]
    if (current == '.'):
        num += 1
    else:
        group[current_h][current_w] = group_index
    # 上
    if current_h > 0:
        next_h = current_h-1
        next_w = current_w
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        try:
            if s_map[next_h][next_w] != current and not(isExist):
                num += search(search_map, group, next_h, next_w, group_index)
        except:
            num+1
    # 下
    if current_h < H-1:
        next_h = current_h+1
        next_w = current_w
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        try:
            if s_map[next_h][next_w] != current and not(isExist):
                num += search(search_map, group, next_h, next_w, group_index)
        except:
            num+1
    # 左
    if current_w > 0:
        next_h = current_h
        next_w = current_w-1
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        try:
            if s_map[next_h][next_w] != current and not(isExist):
                num += search(search_map, group, next_h, next_w, group_index)
        except:
            num+1
    # 右
    if current_w < W-1:
        next_h = current_h
        next_w = current_w+1
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        try:
            if s_map[next_h][next_w] != current and not(isExist):
                num += search(search_map, group, next_h, next_w, group_index)
        except:
            num+1
    return num


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

s_map = {}
group = {}
searched_map = {}


for i in range(H):
    s_map[i] = {}
    group[i] = {}
    w = list(A[i])
    for j in range(W):
        s_map[i][j] = w[j]
        group[i][j] = 0

ans = 0
group_index = 1
group_cnt = {}
group_cnt[0] = 0
for i in range(H):
    for j in range(W):
        if s_map[i][j] == '#':
            if group[i][j] != 0:
                ans += group_cnt[group[i][j]]
            else:
                cnt = search({}, group, i, j, group_index)
                group_cnt[group_index] = cnt
                group_index += 1
                ans += cnt
print(ans)

'''
1 1
#
'''

'''
1 1
.
'''

'''
4 5
#####
#...#
#...#
#####
'''

'''
5 5
.....
.....
.###.
.###.
.....
'''


'''
3 1
#
.
#
'''


'''
3 3
###
#.#
###
'''

'''
5 5
##.##
#.###
####.
##.#.
####.
'''

'''
5 4
#.#.
####
####
#.##
##.#
'''

'''
5 4
#.#.
####
#.#.
####
####
'''

'''
5 4
....
.#..
..#.
...#
#.#.
'''

Submission status: Runtime Error

Solution code:
def search(search_map, group, current_h, current_w, group_index):
    num = 0
    if current_h in search_map:
        search_map[current_h]
    else:
        search_map[current_h] = {}
        search_map[current_h][current_w] = True
    search_map[current_h][current_w] = True
    current = s_map[current_h][current_w]
    if (current == '.'):
        num += 1
    else:
        group[current_h][current_w] = group_index
    # 上
    if current_h > 0:
        next_h = current_h-1
        next_w = current_w
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    # 下
    if current_h < H-1:
        next_h = current_h+1
        next_w = current_w
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    # 左
    if current_w > 0:
        next_h = current_h
        next_w = current_w-1
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    # 右
    if current_w < W-1:
        next_h = current_h
        next_w = current_w+1
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    return num


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

s_map = {}
group = {}
searched_map = {}


for i in range(H):
    s_map[i] = {}
    group[i] = {}
    w = list(A[i])
    for j in range(W):
        s_map[i][j] = w[j]
        group[i][j] = 0

ans = 0
group_index = 1
group_cnt = {}
group_cnt[0] = 0
for i in range(H):
    for j in range(W):
        if s_map[i][j] == '#':
            if group[i][j] != 0:
                ans += group_cnt[group[i][j]]
            else:
                cnt = search({}, group, i, j, group_index)
                group_cnt[group_index] = cnt
                group_index += 1
                ans += cnt
print(ans)

'''
1 1
#
'''

'''
1 1
.
'''

'''
4 5
#####
#...#
#...#
#####
'''

'''
5 5
.....
.....
.###.
.###.
.....
'''


'''
3 1
#
.
#
'''


'''
3 3
###
#.#
###
'''

'''
5 5
##.##
#.###
####.
##.#.
####.
'''

'''
5 4
#.#.
####
####
#.##
##.#
'''

'''
5 4
#.#.
####
#.#.
####
####
'''

'''
5 4
....
.#..
..#.
...#
#.#.
'''

Submission status: Runtime Error

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

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


def search(x, y, st):
    global c_1, c_2
    if st == '.':
        st = '#'
        s[x][y] = 1
        c_1 += 1
    else:
        st = '.'
        s[x][y] = -1
        his[x][y] = 1
        c_2 += 1

    if x != 0 and S[x - 1][y] == st and s[x - 1][y] == 0:
        search(x - 1, y, st)
    if y != 0 and S[x][y - 1] == st and s[x][y - 1] == 0:
        search(x, y - 1, st)
    if x != H - 1 and S[x + 1][y] == st and s[x + 1][y] == 0:
        search(x + 1, y, st)
    if y != W - 1 and S[x][y + 1] == st and s[x][y + 1] == 0:
        search(x, y + 1, st)



ans = 0
for i in range(H):
    for j in range(W):
        s = [[0] * W for _ in range(H)]

        if S[i][j] == '#' and his[i][j] == 0:
            c_1, c_2 = 0, 0
            search(i, j, '#')
            ans += c_1 * c_2

print(ans)

Submission status: Runtime Error

Solution code:
def search(search_map, group, current_h, current_w, group_index):
    num = 0
    if current_h in search_map:
        search_map[current_h]
    else:
        search_map[current_h] = {}
        search_map[current_h][current_w] = True
    search_map[current_h][current_w] = True
    current = s_map[current_h][current_w]
    if (current == '.'):
        num += 1
    else:
        group[current_h][current_w] = group_index
    # 上
    if current_h != 0:
        next_h = current_h-1
        next_w = current_w
        isExist = False
        '''
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        '''
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    # 下
    if current_h < H-1:
        next_h = current_h+1
        next_w = current_w
        isExist = False
        '''
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        '''
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    # 左
    if current_w != 0:
        next_h = current_h
        next_w = current_w-1
        isExist = False
        '''
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        '''
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    # 右
    if current_w < W-1:
        next_h = current_h
        next_w = current_w+1
        isExist = False
        '''
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        '''
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    return num


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

s_map = {}
group = {}
searched_map = {}


for i in range(H):
    s_map[i] = {}
    group[i] = {}
    w = list(A[i])
    for j in range(W):
        s_map[i][j] = w[j]
        group[i][j] = 0

ans = 0
group_index = 1
group_cnt = {}
group_cnt[0] = 0
for i in range(H):
    for j in range(W):
        if s_map[i][j] == '#':
            if group[i][j] != 0:
                ans += group_cnt[group[i][j]]
            else:
                cnt = search({}, group, i, j, group_index)
                group_cnt[group_index] = cnt
                group_index += 1
                ans += cnt
print(ans)

'''
1 1
#
'''

'''
1 1
.
'''

'''
4 5
#####
#...#
#...#
#####
'''

'''
5 5
.....
.....
.###.
.###.
.....
'''


'''
3 1
#
.
#
'''


'''
3 3
###
#.#
###
'''

'''
5 5
##.##
#.###
####.
##.#.
####.
'''

'''
5 4
#.#.
####
####
#.##
##.#
'''

'''
5 4
#.#.
####
#.#.
####
####
'''

'''
5 4
....
.#..
..#.
...#
#.#.
'''

Submission status: Runtime Error

Solution code:
def search(search_map, group, current_h, current_w, group_index):
    num = 0
    if current_h in search_map:
        search_map[current_h]
    else:
        search_map[current_h] = {}
        search_map[current_h][current_w] = True
    search_map[current_h][current_w] = True
    current = s_map[current_h][current_w]
    if (current == '.'):
        num += 1
    else:
        group[current_h][current_w] = group_index
    # 上
    if current_h != 0:
        next_h = current_h-1
        next_w = current_w
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    # 下
    if current_h < H-1:
        next_h = current_h+1
        next_w = current_w
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    # 左
    if current_w != 0:
        next_h = current_h
        next_w = current_w-1
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    # 右
    if current_w < W-1:
        next_h = current_h
        next_w = current_w+1
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    return num


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

s_map = {}
group = {}
searched_map = {}


for i in range(H):
    s_map[i] = {}
    group[i] = {}
    w = list(A[i])
    for j in range(W):
        s_map[i][j] = w[j]
        group[i][j] = 0

ans = 0
group_index = 1
group_cnt = {}
group_cnt[0] = 0
for i in range(H):
    for j in range(W):
        if s_map[i][j] == '#':
            if group[i][j] != 0:
                ans += group_cnt[group[i][j]]
            else:
                cnt = search({}, group, i, j, group_index)
                group_cnt[group_index] = cnt
                group_index += 1
                ans += cnt
print(ans)

'''
1 1
#
'''

'''
1 1
.
'''

'''
4 5
#####
#...#
#...#
#####
'''

'''
5 5
.....
.....
.###.
.###.
.....
'''


'''
3 1
#
.
#
'''


'''
3 3
###
#.#
###
'''

'''
5 5
##.##
#.###
####.
##.#.
####.
'''

'''
5 4
#.#.
####
####
#.##
##.#
'''

'''
5 4
#.#.
####
#.#.
####
####
'''

'''
5 4
....
.#..
..#.
...#
#.#.
'''

Submission status: Runtime Error

Solution code:
H,W=map(int,input().split())
S=[input() for i in [0]*H]
M=[[-1]*W for _ in [0]*H]
def dfs(i,j,k):
    M[i][j]=k
    s=S[i][j]
    if i+1<H and M[i+1][j]==-1 and s!=S[i+1][j]:
        dfs(i+1,j,k)
    if i-1>=0 and M[i-1][j]==-1 and s!=S[i-1][j]:
        dfs(i-1,j,k)
    if j+1<W and M[i][j+1]==-1 and s!=S[i][j+1]:
        dfs(i,j+1,k)
    if j-1>=0 and M[i][j-1]==-1 and s!=S[i][j-1]:
        dfs(i,j-1,k)
k=0
for i in range(H):
    for j in range(W):
        if M[i][j]==-1:dfs(i,j,k);k+=1
ds={}# #
dd={}# .
#di=set()
for i in range(H):
    for j in range(W):
        m=M[i][j]
        if S[i][j]=='#':ds[m]=ds.get(m,0)+1
        else:dd[m]=dd.get(m,0)+1
        #di|={m}
r=0
for i in range(k):
    r += ds.get(i,0)*dd.get(i,0)
print(r)

Submission status: Runtime Error

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


def search(x, y, st):
    if st == '.':
        st = '#'
        s[x][y] = 1
    else:
        st = '.'
        s[x][y] = -1

    if x != 0 and S[x - 1][y] == st and s[x - 1][y] == 0:
        search(x - 1, y, st)
    if y != 0 and S[x][y - 1] == st and s[x][y - 1] == 0:
        search(x, y - 1, st)
    if x != H - 1 and S[x + 1][y] == st and s[x + 1][y] == 0:
        search(x + 1, y, st)
    if y != W - 1 and S[x][y + 1] == st and s[x][y + 1] == 0:
        search(x, y + 1, st)


c = 0
for i in range(H):
    for j in range(W):
        s = [[0] * W for _ in range(H)]

        if S[i][j] == '#':
            search(i, j, '#')
            for a in s:
                c += a.count(1)

print(c)

Submission status: Runtime Error

Solution code:
def search(search_map, group, current_h, current_w, group_index):
    '''
    num = 0
    if current_h in search_map:
        search_map[current_h]
    else:
        search_map[current_h] = {}
        search_map[current_h][current_w] = True
    search_map[current_h][current_w] = True
    current = s_map[current_h][current_w]
    if (current == '.'):
        num += 1
    else:
        group[current_h][current_w] = group_index
    # 上
    if current_h != 0:
        next_h = current_h-1
        next_w = current_w
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    # 下
    if current_h < H-1:
        next_h = current_h+1
        next_w = current_w
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    # 左
    if current_w != 0:
        next_h = current_h
        next_w = current_w-1
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    # 右
    if current_w < W-1:
        next_h = current_h
        next_w = current_w+1
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    '''
    return num


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

s_map = {}
group = {}
searched_map = {}


for i in range(H):
    s_map[i] = {}
    group[i] = {}
    w = list(A[i])
    for j in range(W):
        s_map[i][j] = w[j]
        group[i][j] = 0

ans = 0
group_index = 1
group_cnt = {}
group_cnt[0] = 0
for i in range(H):
    for j in range(W):
        if s_map[i][j] == '#':
            if group[i][j] != 0:
                ans += group_cnt[group[i][j]]
            else:
                cnt = search({}, group, i, j, group_index)
                group_cnt[group_index] = cnt
                group_index += 1
                ans += cnt
print(ans)

'''
1 1
#
'''

'''
1 1
.
'''

'''
4 5
#####
#...#
#...#
#####
'''

'''
5 5
.....
.....
.###.
.###.
.....
'''


'''
3 1
#
.
#
'''


'''
3 3
###
#.#
###
'''

'''
5 5
##.##
#.###
####.
##.#.
####.
'''

'''
5 4
#.#.
####
####
#.##
##.#
'''

'''
5 4
#.#.
####
#.#.
####
####
'''

'''
5 4
....
.#..
..#.
...#
#.#.
'''

Submission status: Runtime Error

Solution code:
def search(search_map, group, current_h, current_w, group_index):
    if current_h in search_map:
        search_map[current_h]
    else:
        search_map[current_h] = {}
        search_map[current_h][current_w] = True
    search_map[current_h][current_w] = True
    current = s_map[current_h][current_w]
    num = 0
    if (current == '.'):
        num += 1
    else:
        group[current_h][current_w] = group_index
    # 上
    if current_h != 0:
        next_h = current_h-1
        next_w = current_w
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    # 下
    if current_h < H-1:
        next_h = current_h+1
        next_w = current_w
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    # 左
    if current_w != 0:
        next_h = current_h
        next_w = current_w-1
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    # 右
    if current_w < W-1:
        next_h = current_h
        next_w = current_w+1
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    return num


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

s_map = {}
group = {}
searched_map = {}


for i in range(H):
    s_map[i] = {}
    group[i] = {}
    w = list(A[i])
    for j in range(W):
        s_map[i][j] = w[j]
        group[i][j] = 0

ans = 0
group_index = 1
group_cnt = {}
group_cnt[0] = 0
for i in range(H):
    for j in range(W):
        if s_map[i][j] == '#':
            if group[i][j] != 0:
                ans += group_cnt[group[i][j]]
            else:
                cnt = search({}, group, i, j, group_index)
                group_cnt[group_index] = cnt
                group_index += 1
                ans += cnt
print(ans)

'''
1 1
#
'''

'''
1 1
.
'''

'''
4 5
#####
#...#
#...#
#####
'''

'''
5 5
.....
.....
.###.
.###.
.....
'''


'''
3 1
#
.
#
'''


'''
3 3
###
#.#
###
'''

'''
5 5
##.##
#.###
####.
##.#.
####.
'''

'''
5 4
#.#.
####
####
#.##
##.#
'''

'''
5 4
#.#.
####
#.#.
####
####
'''

'''
5 4
....
.#..
..#.
...#
#.#.
'''