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: Wrong Answer

Solution code:
H, W = map(int, input().split())
S = ['' for i in range(H)]
for i in range(H):
  S[i] = input()
R = [[[i, j] for j in range(W)] for i in range(H)]
U = [[1 for j in range(W)] for i in range(H)]
def root(A):
  if R[A[0]][A[1]] == A:
    return A
  else:
    R[A[0]][A[1]] = root(R[A[0]][A[1]])
    return R[A[0]][A[1]]
def union(A, B):
  rA = root(A)
  rB = root(B)
  if rA[0] < rB[0]:
    R[rB[0]][rB[1]] = rA
    U[rA[0]][rA[1]] += U[rB[0]][rB[1]]
  elif rB[0] < rA[0]:
    R[rA[0]][rA[1]] = rB
    U[rB[0]][rB[1]] += U[rA[0]][rA[1]]
  elif rA[1] < rB[1]:
    R[rB[0]][rB[1]] = rA
    U[rA[0]][rA[1]] += U[rB[0]][rB[1]]
  elif rB[1] < rA[1]:
    R[rA[0]][rA[1]] = rB
    U[rB[0]][rB[1]] += U[rA[0]][rA[1]]
for i in range(H):
  for j in range(W):
    if S[i][j] == ".":
      if i > 0 and S[i - 1][j] == "#":
        if j > 0 and S[i - 1][j - 1] == ".":
          union([i, j], [i - 1, j - 1])
        if i > 1 and S[i - 2][j] == ".":
          union([i, j], [i - 2, j])
        if j < W - 1 and S[i - 1][j + 1] == ".":
          union([i, j], [i - 1, j + 1])
      if j > 0 and S[i][j - 1] == "#":
        if i > 0 and S[i - 1][j - 1] == ".":
          union([i, j], [i - 1, j - 1])
        if i > 1 and S[i - 2][j] == ".":
          union([i, j], [i - 2, j])
        if i < H - 1 and S[i + 1][j - 1] == ".":
          union([i, j], [i + 1, j - 1])
      if j < W - 1 and S[i][j + 1] == "#":
        if i > 0 and S[i -1][j + 1] == ".":
          union([i, j], [i - 1, j + 1])
for i in range(H):
  for j in range(W):
    root([i, j])
cnt = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == "#":
      if i > 0 and S[i - 1][j] == ".":
        r = R[i - 1][j]
        cnt += U[r[0]][r[1]]
      elif i < H - 1 and S[i + 1][j] == ".":
        r = R[i + 1][j]
        cnt += U[r[0]][r[1]]
      elif j > 0 and S[i][j - 1] == ".":
        r = R[i][j - 1]
        cnt += U[r[0]][r[1]]
      elif j < W - 1 and S[i][j + 1] == ".":
        r = R[i][j + 1]
        cnt += U[r[0]][r[1]]
print(cnt)

Submission status: Wrong Answer

Solution code:
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [ii for ii in range(n)]
        self.rank = [0 for _ in range(n)]

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

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


def to_one(first, second):
    return first * W + second


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


u = UnionFind(H*W)

for i in range(H):
    for j in range(W):
        if i != 0:
            if S[i][j] != S[i - 1][j]:
                u.union(to_one(i, j), to_one(i - 1, j))
        if i != H - 1:
            if S[i][j] != S[i + 1][j]:
                u.union(to_one(i, j), to_one(i + 1, j))
        if j != 0:
            if S[i][j] != S[i][j - 1]:
                u.union(to_one(i, j), to_one(i, j - 1))
        if j != W - 1:
            if S[i][j] != S[i][j + 1]:
                u.union(to_one(i, j), to_one(i, j + 1))


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

for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            count_bw[u.par[to_one(i,j)]][0] += 1
        else:
            count_bw[u.par[to_one(i,j)]][1] += 1

ans = 0

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

print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [ii for ii in range(n)]
        self.rank = [0 for _ in range(n)]

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

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


def to_one(first, second):
    return first * W + second


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


u = UnionFind(H*W)

for i in range(H):
    for j in range(W):
        if i != 0:
            if S[i][j] != S[i - 1][j]:
                u.union(to_one(i, j), to_one(i - 1, j))
        if i != H - 1:
            if S[i][j] != S[i + 1][j]:
                u.union(to_one(i, j), to_one(i + 1, j))
        if j != 0:
            if S[i][j] != S[i][j - 1]:
                u.union(to_one(i, j), to_one(i, j - 1))
        if j != W - 1:
            if S[i][j] != S[i][j + 1]:
                u.union(to_one(i, j), to_one(i, j + 1))


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

for i in range(H*W):
        if i % 2 == 0:
            count_bw[u.par[i]][0] += 1
        else:
            count_bw[u.par[i]][1] += 1

ans = 0

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

print(ans)

Submission status: Wrong Answer

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: Wrong Answer

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: Wrong Answer

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: Wrong Answer

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

count = 0
print(H, W)
print(MAP[0])

for row in MAP:
   for s in range(W-1):
       for f in range(s+1,W):
           extracted_row = row[s:f+1]
           for i in range(1,len(extracted_row)):
               if extracted_row[i]==extracted_row[i-1]:
                   continue
           count+=1
MAP = [[MAP[j][i] for j in range(H)] for i in range(W)]


for row in MAP:
   for s in range(W-1):
       for f in range(s+1,W):
           extracted_row = row[s:f+1]
           for i in range(1,len(extracted_row)):
               if extracted_row[i]==extracted_row[i-1]:
                   continue
           count+=1
print(count)

Submission status: Wrong Answer

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

combo = []

def search(i, j):
    lis = [[0,-1],[-1,1],[1,1],[1,-1]]
    y = []
    for k in range(4):
        y.append([])
        i += lis[k][0]
        j += lis[k][1]
        if not(i < 0 or i >= H or j < 0 or j >= W):
            y[k].append(S[i][j])
        else:
            y[k].append('_')
        y[k].append((i,j))
    return y
    

black = []
count = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            for k, c in search(i,j):
                if k == '.':
                    count += 1
                    combo.append([(i,j),c])

combo = list(map(list, set(map(tuple, combo))))

newcombo = []

for x in combo:
    for y in combo:
        if y != x:
            if x[1] == y[1]:
                for z in combo:
                    if y[0] == z[0]:
                        newcombo.append([x[0], z[1]])

for arr in newcombo:
    combo.append(arr)

combo = list(map(list, set(map(tuple, combo))))
print(len(combo))

Submission status: Wrong Answer

Solution code:
def search(search_map, group, current_h, current_w, group_index):
    s_map[current_h][current_w]
    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: Wrong Answer

Solution code:
from functools import reduce


def main():
  h, w = map(int, input().split())
  ss = []
  for _ in range(h):
    # black(#): True, white(.): False
    ss.append([cell == '#' for cell in list(input())])

  ids = [[-1 for _ in range(w)] for _ in range(h)]
  connecteds = []
  same_id = dict()
  for i in range(h):
    for j in range(w):
      id_ = ids[i][j]
      if id_ == -1:
        bw = (1, 0) if ss[i][j] else (0, 1)
        connecteds.append(bw)
        id_ = len(connecteds) - 1
      black, white = connecteds[id_]
      if i < h - 1 and ss[i][j] != ss[i+1][j]:
        if ids[i+1][j] == -1:
          ids[i+1][j] = id_
          if ss[i+1][j]:
            black += 1
          else:
            white += 1
        elif ids[i][j] != ids[i+1][j]:
          same_id[max(ids[i][j], ids[i+1][j])] = min(ids[i][j], ids[i+1][j])
      if j < w - 1 and ss[i][j] != ss[i][j+1]:
        if ids[i][j+1] == -1:
          ids[i][j+1] = id_
          if ss[i][j+1]:
            black += 1
          else:
            white += 1
        elif ids[i][j] != ids[i][j+1]:
          same_id[max(ids[i][j], ids[i][j+1])] = min(ids[i][j], ids[i][j+1])
      connecteds[id_] = (black, white)
  for k, v in same_id.items():
    while connecteds[v] is None:
      v = same_id[v]
    bk, wk = connecteds[k]
    bv, wv = connecteds[v]
    connecteds[v] = (bk+bv, wk+wv)
    connecteds[k] = None
  connecteds = list(filter(lambda x: x is not None, connecteds))
  ret = 0
  for black, white in connecteds:
    ret += black * white
  print(ret)


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
from collections import deque
answer = 0
s = []
top = 0
bottom = 0
right = 0
left = 0

def bfs(takasa, haba):
    ans = ''
    top = 0
    bottom = 0
    right = 0
    left = 0
    flag = 0
    queue = deque([[takasa, haba]])
    ans += s[takasa][haba]
    s[takasa][haba] = '_'
    while queue:
        takasa, haba = queue.popleft()
        if takasa == 0:
            top += 1
        if takasa == height-1:
            bottom += 1
        if haba == 0:
            left += 1
        if haba == wide-1:
            right += 1
        if s[takasa][haba] == '#':
            flag += 1
        if top > 0 and left > 0 and right > 0:
            j, k = 1, 0
            new_takasa, new_haba = takasa+j, haba+k
            if flag > 0 and s[new_takasa][new_haba] == '.':
                ans += '.'
                queue.append([new_takasa, new_haba])
            if flag < 0 and s[new_takasa][new_haba] == '#':
                ans += '#'
                queue.append([new_takasa, new_haba])
                s[new_takasa][new_haba] = '_'
        elif bottom > 0 and left > 0 and right > 0:
            j, k = -1, 0
            new_takasa, new_haba = takasa+j, haba+k
            if flag > 0 and s[new_takasa][new_haba] == '.':
                ans += '.'
                queue.append([new_takasa, new_haba])
            if flag < 0 and s[new_takasa][new_haba] == '#':
                ans += '#'
                queue.append([new_takasa, new_haba])
                s[new_takasa][new_haba] = '_'
        elif top > 0 and left > 0:
            for j, k in([1, 0], [0, 1]):
                new_takasa, new_haba = takasa+j, haba+k
                if flag > 0 and s[new_takasa][new_haba] == '.':
                    ans += '.'
                    queue.append([new_takasa, new_haba])
                if flag < 0 and s[new_takasa][new_haba] == '#':
                    ans += '#'
                    queue.append([new_takasa, new_haba])
                    s[new_takasa][new_haba] = '_'
        elif top > 0 and right > 0:
            for j, k in([1, 0], [0, -1]):
                new_takasa, new_haba = takasa+j, haba+k
                if flag > 0 and s[new_takasa][new_haba] == '.':
                    ans += '.'
                    queue.append([new_takasa, new_haba])
                if flag < 0 and s[new_takasa][new_haba] == '#':
                    ans += '#'
                    queue.append([new_takasa, new_haba])
                    s[new_takasa][new_haba] = '_'
        elif top > 0:
            for j, k in ([1, 0], [0, 1], [0, -1]):
                new_takasa, new_haba = takasa+j, haba+k
                if flag > 0 and s[new_takasa][new_haba] == '.':
                    ans += '.'
                    queue.append([new_takasa, new_haba])
                if flag < 0 and s[new_takasa][new_haba] == '#':
                    ans += '#'
                    queue.append([new_takasa, new_haba])
                    s[new_takasa][new_haba] = '_'
        elif bottom > 0 and left > 0:
            for j, k in([0, 1], [-1, 0]):
                new_takasa, new_haba = takasa+j, haba+k
                if flag > 0 and s[new_takasa][new_haba] == '.':
                    ans += '.'
                    queue.append([new_takasa, new_haba])
                if flag < 0 and s[new_takasa][new_haba] == '#':
                    ans += '#'
                    queue.append([new_takasa, new_haba])
                    s[new_takasa][new_haba] = '_'
        elif bottom > 0 and right > 0:
            for j, k in([0, -1], [-1, 0]):
                new_takasa, new_haba = takasa+j, haba+k
                if flag > 0 and s[new_takasa][new_haba] == '.':
                    ans += '.'
                    queue.append([new_takasa, new_haba])
                if flag < 0 and s[new_takasa][new_haba] == '#':
                    ans += '#'
                    queue.append([new_takasa, new_haba])
                    s[new_takasa][new_haba] = '_'
        elif bottom > 0:
            for j, k in ([-1, 0], [1, 0], [-1, 0]):
                new_takasa, new_haba = takasa+j, haba+k
                if flag > 0 and s[new_takasa][new_haba] == '.':
                    ans += '.'
                    queue.append([new_takasa, new_haba])
                if flag < 0 and s[new_takasa][new_haba] == '#':
                    ans += '#'
                    queue.append([new_takasa, new_haba])
                    s[new_takasa][new_haba] = '_'
        elif left > 0:
            for j, k in ([-1, 0], [1, 0], [0, 1]):
                new_takasa, new_haba = takasa+j, haba+k
                if flag > 0 and s[new_takasa][new_haba] == '.':
                    ans += '.'
                    queue.append([new_takasa, new_haba])
                if flag < 0 and s[new_takasa][new_haba] == '#':
                    ans += '#'
                    queue.append([new_takasa, new_haba])
                    s[new_takasa][new_haba] = '_'
        elif right > 0:
            for j, k in([-1, 0], [1, 0], [0, -1]):
                new_takasa, new_haba = takasa+j, haba+k
                if flag > 0 and s[new_takasa][new_haba] == '.':
                    ans += '.'
                    queue.append([new_takasa, new_haba])
                if flag < 0 and s[new_takasa][new_haba] == '#':
                    ans += '#'
                    queue.append([new_takasa, new_haba])
                    s[new_takasa][new_haba] = '_'
        else:
            for j, k in([1, 0], [0, 1], [-1, 0], [0, -1]):
                new_takasa, new_haba = takasa+j, haba+k
                if flag > 0 and s[new_takasa][new_haba] == '.':
                    ans += '.'
                    queue.append([new_takasa, new_haba])
                if flag < 0 and s[new_takasa][new_haba] == '#':
                    ans += '#'
                    queue.append([new_takasa, new_haba])
                    s[new_takasa][new_haba] = '_'
        top = 0
        bottom = 0
        right = 0
        left = 0

    return(ans.count('#')*ans.count('.'))


height, wide = map(int, input().split())

s = []
for _ in range(height):
    s.append(list(input()))
for takasa in range(height):
    for haba in range(wide):
        if s[takasa][haba] == '#':
            answer += bfs(takasa, haba)
        else:
            pass
print(answer)