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:
h,w = [int(x) for x in input().split(" ")]

s = []
for i in range(h):
  s.append(input())


used = np.zeros((h,w))
wh = 0; bl=0

def findNext(i, j):
  global wh
  global bl
  global used
  
  used[i,j] = 1
  i_next = i - 1; j_next = j
  if (i_next >= 0) and (i_next < h) and (j_next >= 0) and (j_next < w):
    if (s[i][j] != s[i_next][j_next]):
      if used[i_next, j_next]==0:
        if s[i][j] == "#":
          wh += 1 
        else:
          bl += 1
        findNext(i_next, j_next)
  i_next = i; j_next = j+1
  if (i_next >= 0) and (i_next < h) and (j_next >= 0) and (j_next < w):
    if (s[i][j] != s[i_next][j_next]):
      if used[i_next, j_next]==0:
        if s[i][j] == "#":
          wh += 1 
        else:
          bl += 1
        findNext(i_next, j_next)
  i_next = i; j_next = j-1
  if (i_next >= 0) and (i_next < h) and (j_next >= 0) and (j_next < w):
    if (s[i][j] != s[i_next][j_next]):
      if used[i_next, j_next]==0:
        if s[i][j] == "#":
          wh += 1 
        else:
          bl += 1
        findNext(i_next, j_next)
  i_next = i + 1; j_next = j
  if (i_next >= 0) and (i_next < h) and (j_next >= 0) and (j_next < w):
    if (s[i][j] != s[i_next][j_next]):
      if used[i_next, j_next]==0:
        if s[i][j] == "#":
          wh += 1 
        else:
          bl += 1
        findNext(i_next, j_next)

all_cnt = 0
for i in range(h):
  for j in range(w):
    if used[i, j] == 0:
      wh = 0; bl = 0
      if s[i][j]=="#":
        bl = 1
      else:
        wh = 1
      findNext(i, j)
      all_cnt += wh * bl

print(all_cnt)

Submission status: Runtime Error

Solution code:
h,w = [int(x) for x in input().split(" ")]

s = []
for i in range(h):
  s.append(input())


used = np.zeros((h,w))
wh = 0; bl=0

def findNext(i, j):
  global wh
  global bl
  used[i,j] = 1
  i_next = i - 1; j_next = j
  if (i_next >= 0) and (i_next < h) and (j_next >= 0) and (j_next < w):
    if (s[i][j] != s[i_next][j_next]):
      if used[i_next, j_next]==0:
        if s[i][j] == "#":
          wh += 1 
        else:
          bl += 1
        findNext(i_next, j_next)
  i_next = i; j_next = j+1
  if (i_next >= 0) and (i_next < h) and (j_next >= 0) and (j_next < w):
    if (s[i][j] != s[i_next][j_next]):
      if used[i_next, j_next]==0:
        if s[i][j] == "#":
          wh += 1 
        else:
          bl += 1
        findNext(i_next, j_next)
  i_next = i; j_next = j-1
  if (i_next >= 0) and (i_next < h) and (j_next >= 0) and (j_next < w):
    if (s[i][j] != s[i_next][j_next]):
      if used[i_next, j_next]==0:
        if s[i][j] == "#":
          wh += 1 
        else:
          bl += 1
        findNext(i_next, j_next)
  i_next = i + 1; j_next = j
  if (i_next >= 0) and (i_next < h) and (j_next >= 0) and (j_next < w):
    if (s[i][j] != s[i_next][j_next]):
      if used[i_next, j_next]==0:
        if s[i][j] == "#":
          wh += 1 
        else:
          bl += 1
        findNext(i_next, j_next)

all_cnt = 0
for i in range(h):
  for j in range(w):
    if used[i, j] == 0:
      wh = 0; bl = 0
      if s[i][j]=="#":
        bl = 1
      else:
        wh = 1
      findNext(i, j)
      all_cnt += wh * bl

print(all_cnt)

Submission status: Runtime Error

Solution code:
def search(search_map, group, current_h, current_w, group_index):
    if not(current_h > -1 and current_w > -1 and current_h < H and current_w < W):
        return 0
    num = 0
    if current_h not in search_map:
        search_map[current_h] = {}
    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)

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

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

Submission status: Runtime Error

Solution code:
if False:
    H, W = map(int, input().split())

    X = [[0] * W for i in range(H)]
    G = [[0,0] for i in range(W*H)] 
    L = [[-1] * W for i in range(H)] # Group ID

    for i in range(H):
        s = input()
        for j in range(W):
            if (i+j) % 2 == 0:
                if s[j] == "#":
                    X[i][j] = 1
            else:
                if s[j] != "#":
                    X[i][j] = 1
else:
    H, W = 400, 400

    X = [[0] * W for i in range(H)]
    G = [[0,0] for i in range(W*H)] 
    L = [[-1] * W for i in range(H)] # Group ID

    for i in range(H):
        if i%2 == 0:
            s = ("#.#." * W)[:W]
        else:
            s = (".#.#" * W)[:W]
        for j in range(W):
            if (i+j) % 2 == 0:
                if s[j] == "#":
                    X[i][j] = 1
            else:
                if s[j] != "#":
                    X[i][j] = 1


g = -1
for i in range(H):
    for j in range(W):
        if L[i][j] < 0:
            g += 1
            L[i][j] = g
            # GGG = [[i,j]]
            nd = Node(i*400+j,1)
            post = [[i,j]]
            G[g][(i+j)%2] += 1
            while post:
                pre = post
                post = []
                for ggg in pre:
                    i0, j0 = ggg
                    if i0>0 and L[i0-1][j0] < 0 and X[i0][j0] == X[i0-1][j0]:
                        post.append([i0-1,j0])
                        L[i0-1][j0] = g
                        G[g][(i0+j0+1)%2] += 1
                    if i0<H-1 and L[i0+1][j0] < 0 and X[i0][j0] == X[i0+1][j0]:
                        post.append([i0+1,j0])
                        L[i0+1][j0] = g
                        G[g][(i0+j0+1)%2] += 1
                    if j0>0 and L[i0][j0-1] < 0 and X[i0][j0] == X[i0][j0-1]:
                        post.append([i0,j0-1])
                        L[i0][j0-1] = g
                        G[g][(i0+j0+1)%2] += 1
                    if j0<W-1 and L[i0][j0+1] < 0 and X[i0][j0] == X[i0][j0+1]:
                        post.append([i0,j0+1])
                        L[i0][j0+1] = g
                        G[g][(i0+j0+1)%2] += 1
                        
            # print(GGG)
# print(G)
ans = 0
for t in G:
    aa, bb = t
    ans += aa * bb
    
print(ans)

Submission status: Runtime Error

Solution code:
def search(search_map, group, current_h, current_w, group_index):
    num = 0
    if current_h not in search_map:
        search_map[current_h] = {}
    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
        if next_h > -1 and next_w > -1 and next_h < H and next_w < 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)

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

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

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

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:
h,w = [int(x) for x in input().split(" ")]

s = []
for i in range(h):
  s.append(input())


used = []
wh = 0; bl=0

def findNext(i, j):
  global wh
  global bl
  used.append([i, j])
  i_next = i - 1; j_next = j
  if (i_next >= 0) and (i_next < h) and (j_next >= 0) and (j_next < w):
    if (s[i][j] != s[i_next][j_next]):
      if ([i_next, j_next] not in used):
        if s[i][j] == "#":
          wh += 1 
        else:
          bl += 1
        findNext(i_next, j_next)
  i_next = i; j_next = j+1
  if (i_next >= 0) and (i_next < h) and (j_next >= 0) and (j_next < w):
    if (s[i][j] != s[i_next][j_next]):
      if ([i_next, j_next] not in used):
        if s[i][j] == "#":
          wh += 1 
        else:
          bl += 1
        findNext(i_next, j_next)
  i_next = i; j_next = j-1
  if (i_next >= 0) and (i_next < h) and (j_next >= 0) and (j_next < w):
    if (s[i][j] != s[i_next][j_next]):
      if ([i_next, j_next] not in used):
        if s[i][j] == "#":
          wh += 1 
        else:
          bl += 1
        findNext(i_next, j_next)
  i_next = i + 1; j_next = j
  if (i_next >= 0) and (i_next < h) and (j_next >= 0) and (j_next < w):
    if (s[i][j] != s[i_next][j_next]):
      if ([i_next, j_next] not in used):
        if s[i][j] == "#":
          wh += 1 
        else:
          bl += 1
        findNext(i_next, j_next)

all_cnt = 0
for i in range(h):
  for j in range(w):
    if [i, j] not in used:
      wh = 0; bl = 0
      if s[i][j]=="#":
        bl = 1
      else:
        wh = 1
      findNext(i, j)
      all_cnt += wh * bl

print(all_cnt)

Submission status: Runtime Error

Solution code:
def search(search_map, group, current_h, current_w, group_index):
    num = 0
    if current_h not in search_map:
        search_map[current_h] = {}
    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
        if next_h > 0 and next_w > 0 and next_h < H and next_w < 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)

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

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

Submission status: Runtime Error

Solution code:
def search(search_map, group, current_h, current_w, group_index):
    num = 0
    if current_h not in search_map:
        search_map[current_h] = {}
    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
        if next_h > 0:
            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)

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

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

Submission status: Runtime Error

Solution code:
def search(search_map, group, current_h, current_w, group_index):
    num = 0
    if current_h not in search_map:
        search_map[current_h] = {}
    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
        if next_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)

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

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

Submission status: Runtime Error

Solution code:
h,w = [int(x) for x in input().split(" ")]

s = []
for i in range(h):
  s.append(input())


used = []

def findNext(i, j):
  used.append([i, j])
  i_next = i - 1; j_next = j
  if (i_next >= 0) and (i_next < h) and (j_next >= 0) and (j_next < w):
    if (s[i][j] != s[i_next][j_next]):
      if ([i_next, j_next] not in used):
        if s[i][j] == "#":
          wh += 1 
        else:
          bl += 1
        findNext(i_next, j_next)
  i_next = i; j_next = j+1
  if (i_next >= 0) and (i_next < h) and (j_next >= 0) and (j_next < w):
    if (s[i][j] != s[i_next][j_next]):
      if ([i_next, j_next] not in used):
        if s[i][j] == "#":
          wh += 1 
        else:
          bl += 1
        findNext(i_next, j_next)
  i_next = i; j_next = j-1
  if (i_next >= 0) and (i_next < h) and (j_next >= 0) and (j_next < w):
    if (s[i][j] != s[i_next][j_next]):
      if ([i_next, j_next] not in used):
        if s[i][j] == "#":
          wh += 1 
        else:
          bl += 1
        findNext(i_next, j_next)
  i_next = i + 1; j_next = j
  if (i_next >= 0) and (i_next < h) and (j_next >= 0) and (j_next < w):
    if (s[i][j] != s[i_next][j_next]):
      if ([i_next, j_next] not in used):
        if s[i][j] == "#":
          wh += 1 
        else:
          bl += 1
        findNext(i_next, j_next)

all_cnt = 0
for i in range(h):
  for j in range(w):
    if [i, j] not in used:
      wh = 0; bl = 0
      findNext(i, j)
      all_cnt += wh * bl

print(all_cnt)

Submission status: Runtime Error

Solution code:
h,w = [int(x) for x in input().split(" ")]

s = []
for i in range(h):
  s.append(input())


used = []

def findNext(i, j):
  used.append([i, j])
  i_next = i - 1; j_next = j
  if (i_next >= 0) and (i_next < h) and (j_next >= 0) and (j_next < w):
    if (s[i][j] != s[i_next][j_next]):
      if ([i_next, j_next] not in used):
        used.append([i_next, j_next])
        if s[i][j] == "#":
          wh += 1 
        else:
          bl += 1
        findNext(i_next, j_next)
  i_next = i; j_next = j+1
  if (i_next >= 0) and (i_next < h) and (j_next >= 0) and (j_next < w):
    if (s[i][j] != s[i_next][j_next]):
      if ([i_next, j_next] not in used):
        used.append([i_next, j_next])
        if s[i][j] == "#":
          wh += 1 
        else:
          bl += 1
        findNext(i_next, j_next)
  i_next = i; j_next = j-1
  if (i_next >= 0) and (i_next < h) and (j_next >= 0) and (j_next < w):
    if (s[i][j] != s[i_next][j_next]):
      if ([i_next, j_next] not in used):
        used.append([i_next, j_next])
        if s[i][j] == "#":
          wh += 1 
        else:
          bl += 1
        findNext(i_next, j_next)
  i_next = i + 1; j_next = j
  if (i_next >= 0) and (i_next < h) and (j_next >= 0) and (j_next < w):
    if (s[i][j] != s[i_next][j_next]):
      if ([i_next, j_next] not in used):
        used.append([i_next, j_next])
        if s[i][j] == "#":
          wh += 1 
        else:
          bl += 1
        findNext(i_next, j_next)

all_cnt = 0
for i in range(h):
  for j in range(w):
    if [i, j] not in used:
      wh = 0; bl = 0
      findNext(i, j)
      all_cnt += wh * bl

print(all_cnt)

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/aising2019/submissions/3986315
# 解説のように 連結成分を求めてから、bfsする

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

ans = 0

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

un_reached = [[True for i in range(W)] for j in range(H)]


def isIn(x, y):
    return 0 <= x < H and 0 <= y < W


def dfs(x, y):
    un_reached[x][y] = False
    if s[x][y] == '#':
        cc[1] += 1
    else:
        cc[0] += 1

    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if isIn(nx, ny) and s[nx][ny] != s[x][y] and un_reached[nx][ny]:
            dfs(nx, ny)


for i in range(H):
    for j in range(W):
        if un_reached[i][j]:
            cc = [0 for _ in range(2)]
            dfs(i, j)
            ans += cc[1]*cc[0]
print(ans)

Submission status: Runtime Error

Solution code:
def search(search_map, group, current_h, current_w, group_index):
    num = 0
    if current_h not in search_map:
        search_map[current_h] = {}
    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
print(s_map)

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 = [int(x) for x in input().split(" ")]

s = []
for i in range(h):
  s.append(input())


used = []

def findNext(i, j):
  i_next = i - 1; j_next = j
  if (i_next >= 0) and (i_next < h) and (j_next >= 0) and (j_next < w):
    if (s[i][j] != s[i_next][j_next]):
      if ([i_next, j_next] not in used):
        used.append([i_next, j_next])
        if s[i][j] == "#":
          wh += 1 
        else:
          bl += 1
        findNext(i_next, j_next)
  i_next = i; j_next = j+1
  if (i_next >= 0) and (i_next < h) and (j_next >= 0) and (j_next < w):
    if (s[i][j] != s[i_next][j_next]):
      if ([i_next, j_next] not in used):
        used.append([i_next, j_next])
        if s[i][j] == "#":
          wh += 1 
        else:
          bl += 1
        findNext(i_next, j_next)
  i_next = i; j_next = j-1
  if (i_next >= 0) and (i_next < h) and (j_next >= 0) and (j_next < w):
    if (s[i][j] != s[i_next][j_next]):
      if ([i_next, j_next] not in used):
        used.append([i_next, j_next])
        if s[i][j] == "#":
          wh += 1 
        else:
          bl += 1
        findNext(i_next, j_next)
  i_next = i + 1; j_next = j
  if (i_next >= 0) and (i_next < h) and (j_next >= 0) and (j_next < w):
    if (s[i][j] != s[i_next][j_next]):
      if ([i_next, j_next] not in used):
        used.append([i_next, j_next])
        if s[i][j] == "#":
          wh += 1 
        else:
          bl += 1
        findNext(i_next, j_next)

all_cnt = 0
for i in range(h):
  for j in range(w):
    if [i, j] not in used:
      wh = 0; bl = 0
      findNext(i, j)
      all_cnt += wh * bl

print(all_cnt)