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 = map(int, input().strip().split())
S = [input().strip() for _ in range(H)]
visited = [[False for _ in range(W)] for _ in range(H)]

def dfs(_i, _j, _S, _visited, _fs):
  if _i<H-1 and not _visited[_i+1][_j] and S[_i][_j]!=S[_i+1][_j]:
    if S[_i+1][_j] == '.':
      _fs.add((_i+1, _j))
    _visited[_i+1][_j] = True
    _fs |= dfs(_i+1, _j, _S, _visited, _fs)
    _visited[_i+1][_j] = False
  if _i>0 and not _visited[_i-1][_j] and S[_i][_j]!=S[_i-1][_j]:
    if S[_i-1][_j] == '.':
      _fs.add((_i-1, _j))
    _visited[_i-1][_j] = True
    _fs |= dfs(_i-1, _j, _S, _visited, _fs)
    _visited[_i-1][_j] = False
  if _j<W-1 and not _visited[_i][_j+1] and S[_i][_j]!=S[_i][_j+1]:
    if S[_i][_j+1] == '.':
      _fs.add((_i, _j+1))
    _visited[_i][_j+1] = True
    _fs |= dfs(_i, _j+1, _S, _visited, _fs)
    _visited[_i][_j+1] = False
  if _j>-0 and not _visited[_i][_j-1] and S[_i][_j]!=S[_i][_j-1]:
    if S[_i][_j-1] == '.':
      _fs.add((_i, _j-1))
    _visited[_i][_j-1] = True
    _fs |= dfs(_i, _j-1, _S, _visited, _fs)
    _visited[_i][_j-1] = False
  return _fs

ans = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == '#':
      fs = set()
      visited[i][j] = True
      fs = dfs(i, j, S, visited, fs);
      ans += len(fs)
      for k in range(H):
        for l in range(W):
          visited[k][l] = False
          
print(ans)

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
s = [input() for _ in range(h)]
box = [(1, 0), (0, 1), (-1, 0), (0, -1)]

black = []
white = []

for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            black.append((i, j))
        else:
            white.append((i, j))

def check(u, v, p):
        for x, y in box:
            if u + x < 0 or u + x >= h or v + y < 0 or v + y >= w:
                continue
            if s[u][v] == "." and s[u+x][v+y] == "#" and p[u+x][v+y] == 0:
                p[u+x][v+y] = 1
                check(u+x, v+y, p)

            elif s[u][v] == "#" and s[u+x][v+y] == "." and p[u+x][v+y] == 0:
                p[u+x][v+y] = 1
                check(u+x, v+y, p)
        return p

ans = 0
for i, j in black:
    p = [[0]*w for _ in range(h)]
    p[i][j] = 1
    for a, b in white:
        t = check(i, j, p)
        if p[a][b] == 1:
            ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
h, w = [int(i) for i in input().split()]
s = [input() for i in range(h)]
cnt = 0
e = []
def ahaha(i, j):
    global cnt
    global e
    e.append([i,j])
    if i+1 < h and [i+1,j] not in e:
        if s[i+1][j] != s[i][j]:
            if s[i+1][j] == ".":
                cnt += 1
            ahaha(i+1,j)
    if i-1 >= 0 and [i-1,j] not in e:
        if s[i-1][j] != s[i][j]:
            if s[i-1][j] == ".":
                cnt += 1
            ahaha(i-1,j)
    if j+1 < w and [i,j+1] not in e:
        if s[i][j+1] != s[i][j]:
            if s[i][j+1] == ".":
                cnt += 1
            ahaha(i,j+1)
    if j-1 >= 0 and [i,j-1] not in e:
        if s[i][j-1] != s[i][j]:
            if s[i][j-1] == ".":
                cnt += 1
            ahaha(i,j-1)

for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            ahaha(i,j)
            e = []
print(cnt)

Submission status: Runtime Error

Solution code:
# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]

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

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

t = 1


def f(h, w):
    cb = cw = 0
    dh = [1, -1, 0, 0]
    dw = [0, 0, 1, -1]

    for i in range(4):
        h2 = h + dh[i]
        w2 = w + dw[i]
        if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
            # 未調査 かつ 色違い
            if T[h2][w2] == 0:
                if S[h][w] != S[h2][w2]:
                    T[h2][w2] = 1
                    if S[h2][w2] == "#":
                        cb += 1
                    if S[h2][w2] == ".":
                        cw += 1
                    cb2, cw2 = f(h2, w2)
                    cb += cb2
                    cw += cw2
    return cb, cw


area = []
for h in range(H):
    for w in range(W):
        if S[h][w] == "#" and T[h][w] == 0:
            tmp = f(h, w)
            if tmp[0]*tmp[1] != 0:
                area.append(tmp)

ans = 0
for a in area:
    ans += a[0]*a[1]

print(ans)

Submission status: Runtime Error

Solution code:


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

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


def search(search_map, group, current_h, current_w, group_index):
    search_map[current_h][current_w] = True
    current = s_map[current_h][current_w]
    num = 0
    if (s_map[current_h][current_w] == '.'):
        num += 1
    else:
        if group[current_h][current_w] != 0:
            group[current_h][current_w] = group_index
    # 上
    if current_h != 0:
        next_h = current_h-1
        next_w = current_w
        if s_map[next_h][next_w] != current and not(search_map[next_h][next_w]):
            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
        if s_map[next_h][next_w] != current and not(search_map[next_h][next_w]):
            num += search(search_map, group, next_h, next_w, group_index)
    # 左
    if current_w != 0:
        next_h = current_h
        next_w = current_w-1
        if s_map[next_h][next_w] != current and not(search_map[next_h][next_w]):
            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
        if s_map[next_h][next_w] != current and not(search_map[next_h][next_w]):
            num += search(search_map, group, next_h, next_w, group_index)
    return num


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

ans = 0
group_index = 1
group_cnt = {}
for i in range(H):
    for j in range(W):
        if s_map[i][j] == '#':
            # TODO: 初期化(searched_map)
            if group[i][j] != 0:
                ans += group_cnt[group[i][j]]
            else:
                group_num = group_index
                cnt = search(searched_map, group, i, j, group_index)
                group_cnt[group_num] = cnt
                ans += cnt
                for h in range(H):
                    for w in range(W):
                        searched_map[h][w] = False

print(ans)

Submission status: Runtime Error

Solution code:
def make_road(i, j, b, w):
    global H, W
    #print(i, j, S[i][j])
    visited[i][j] = 1
    if S[i][j] == "#":
        b += 1
    else:
        w += 1
    if j < W - 1:
        if S[i][j + 1] != S[i][j] and visited[i][j + 1] == 0:
            b, w = make_road(i, j + 1, b, w)
    if i < H - 1:
        if S[i + 1][j] != S[i][j] and visited[i + 1][j] == 0:
            b, w = make_road(i + 1, j, b, w)
    if 0 < j:
        if S[i][j - 1] != S[i][j] and visited[i][j - 1] == 0:
            b, w = make_road(i, j - 1, b, w)
    if 0 < i:
        if S[i - 1][j] != S[i][j] and visited[i - 1][j] == 0:
            b, w = make_road(i - 1, j, b, w)
    return b, w


H, W = map(int, input().split())
S = [list(input()) for i in range(H)]
visited = [[0 for i in range(W)] for j in range(H)]
graf = [[0 for i in range(W)] for j in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if visited[i][j] == 0:
            b, w = make_road(i, j, 0, 0)
            #print(i, j, b, w)
            ans += b * w
print(ans)

Submission status: Runtime Error

Solution code:
def trace(i, j, S, col, num_color):
    next_col = 1 - col
    num_color[col] += 1
    S[i][j] = 2
    if S[i-1][j] == next_col:
        trace(i-1, j, S, next_col, num_color)
    if S[i][j-1] == next_col:
        trace(i, j-1, S, next_col, num_color)
    if S[i+1][j] == next_col:
        trace(i+1, j, S, next_col, num_color)
    if S[i][j+1] == next_col:
        trace(i, j+1, S, next_col, num_color)
    return num_color[0] * num_color[1]

def main():
    H, W = map(int, input().split())
    # 黒0，白1，padding2
    S = [[2] * (W+2)]
    for _ in range(H):
        S.append([2] + [0 if s == '#' else 1 for s in input()] + [2])
    S.append([2] * (W+2))
    num_comb = 0
    for i in range(1, H+1):
        for j in range(1, W+1):
            if S[i][j] == 0:
                num_color = [0, 0]
                num_comb += trace(i, j, S, 0, num_color)
    print(num_comb)

main()

Submission status: Runtime Error

Solution code:


def update(M, S, i, j, H, W, cluster):
    for i_n in [i - 1, i, i + 1]:
        for j_n in [j - 1, j, j + 1]:
            if i_n >= H or i_n < 0:
                continue
            if j_n >= W or j_n < 0:
                continue

            if i_n == i and j_n == j:
                continue
            if abs(i - i_n) + abs(j - j_n) == 2:
                continue

            if S[i][j] != S[i_n][j_n] and M[i_n][j_n] == 0:
                # print(M)
                M[i_n][j_n] = cluster
                update(M, S, i_n, j_n, H, W, cluster)


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

cluster = 1
counts_B = {}
counts_W = {}
M = [[0 for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        if M[i][j] == 0:
            M[i][j] = cluster
            update(M, S, i, j, H, W, cluster)
            cluster = cluster + 1
        counts_B[M[i][j]] = 0
        counts_W[M[i][j]] = 0


for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            counts_B[M[i][j]] += 1
        else:
            counts_W[M[i][j]] += 1

    #     print(M[i][j], end=" ")
    # print("")

total = 0
for k in counts_B.keys():
    if k in counts_W:
        total += counts_B[k] * counts_W[k]
    # print(counts[k])

print(total)

Submission status: Runtime Error

Solution code:
def trace(i, j, S, col, num_color):
    next_col = 1 - col
    num_color[col] += 1
    S[i][j] = 2
    if S[i-1][j] == next_col:
        trace(i-1, j, S, next_col, num_color)
    if S[i][j-1] == next_col:
        trace(i, j-1, S, next_col, num_color)
    if S[i+1][j] == next_col:
        trace(i+1, j, S, next_col, num_color)
    if S[i][j+1] == next_col:
        trace(i, j+1, S, next_col, num_color)
    return num_color[0] * num_color[1]

H, W = map(int, input().split())
# 黒0，白1，padding2
S = [[2] * (W+2)]
for _ in range(H):
    S.append([2] + [0 if s == '#' else 1 for s in input()] + [2])
S.append([2] * (W+2))
# print(S)
num_comb = 0
for i in range(1, H+1):
    for j in range(1, W+1):
        if S[i][j] == 0:
            num_color = [0, 0]
            num_comb += trace(i, j, S, 0, num_color)
print(num_comb)

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
A_list = sorted(list(map(int, input().split())))
X_list = [int(input()) for _ in range(Q)]
import numpy as np

def aoki(cards_, x):
    res = [abs(x-card) for card in cards]
    min_res = min(res)
    for idx, r in enumerate(res):
        if r == min_res:
            return cards[idx]
        
def game(cards, x):
    taka_sum = 0
    while(len(cards)>0):
        taka_card = cards.pop(np.argmax(cards))
        taka_sum += taka_card
        if len(cards) == 0:
            break
        aoki_card = aoki(cards, x)
        cards.remove(aoki_card)
    return taka_sum

import copy
for X in X_list:
    A_list_copy = copy.copy(A_list) 
    print(game(A_list_copy, X))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from itertools import product

H, W = map(int, input().split())
S = [input() for _ in range(H)]
color = [[None] * W for _ in range(H)]
memo = [[0, 0] for _ in range(H * W + 1)]
cnt = 1


def dfs(p, c):
    x, y = p
    color[x][y] = c
    memo[cnt][c] += 1
    for dx, dy in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and color[nx][ny] is None and c != (S[nx][ny] == '#'):
            dfs([nx, ny], not c)


for i, j in product(range(H), range(W)):
    if color[i][j] is None:
        dfs([i, j], S[i][j] == '#')
        cnt += 1

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

Submission status: Runtime Error

Solution code:
def trace(i, j, S, col, num_color):
    next_col = 1 - col
    num_color[col] += 1
    S[i][j] = 2
    if S[i-1][j] == next_col:
        trace(i-1, j, S, next_col, num_color)
    if S[i][j-1] == next_col:
        trace(i, j-1, S, next_col, num_color)
    if S[i+1][j] == next_col:
        trace(i+1, j, S, next_col, num_color)
    if S[i][j+1] == next_col:
        trace(i, j+1, S, next_col, num_color)
    return num_color[0] * num_color[1]

H, W = map(int, input().split())
# 黒0，白1，padding2
S = [[2] * (W+2)]
for _ in range(H):
    S.append([2] + [0 if s == '#' else 1 for s in input()] + [2])
S.append([2] * (W+2))
# print(S)
num_comb = 0
for i in range(1, H+1):
    for j in range(1, W+1):
        if S[i][j] == 0:
            num_color = [0, 0]
            num_comb += trace(i, j, S, 0, num_color)
print(num_comb)

Submission status: Runtime Error

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

def dfs(h,w,i,c):
    # グループ分け
    V[h][w] = i
    # 上
    if h>0 and V[h-1][w]==0:
        if c=="#" and S[h-1][w]==".":
            dfs(h-1,w,i,".")
        elif c=="." and S[h-1][w]=="#":
            dfs(h-1,w,i,"#")
    # 左
    if w>0 and V[h][w-1]==0:
        if c=="#" and S[h][w-1]==".":
            dfs(h,w-1,i,".")
        elif c=="." and S[h][w-1]=="#":
            dfs(h,w-1,i,"#")
    # 下
    if h<H-1 and V[h+1][w]==0:
        if c=="#" and S[h+1][w]==".":
            dfs(h+1,w,i,".")
        elif c=="." and S[h+1][w]=="#":
            dfs(h+1,w,i,"#")
    # 右
    if w<W-1 and V[h][w+1]==0:
        if c=="#" and S[h][w+1]==".":
            dfs(h,w+1,i,".")
        elif c=="." and S[h][w+1]=="#":
            dfs(h,w+1,i,"#")

V = [[0 for _ in range(W)] for _ in range(H)]
ans = 0
i = 0
for h in range(H):
    for w in range(W):
        if S[h][w]=="#" and V[h][w]==0:
            i += 1
            dfs(h,w,i,"#")

# iグループに分割完了
cnt_b = [0]*i
cnt_w = [0]*i

for h in range(H):
    for w in range(W):
        group = V[h][w]
        if group != 0:
            if S[h][w]=="#":
                cnt_b[group-1] += 1
            else:
                cnt_w[group-1] += 1

ans = 0
for i in range(len(cnt_b)):
    ans += cnt_b[i]*cnt_w[i]

print(ans)

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={}# .
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
r=0
for i in range(k):
    r += ds.get(i,0)*dd.get(i,0)
print(r)

Submission status: Runtime Error

Solution code:
import sys
fin = sys.stdin.readline
sys.setrecursionlimit(100000)
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)]
# print(S)

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)

# DFS
group = 0
for i in range(H):
    for j in range(W):
        dfs_visit(i, j, visited, group)
        # stack = [(i, j)]
        # while stack:
        #     i, j = stack.pop()
        #     if visited[i][j]:
        #         continue
        #     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:
        #             stack.append((next_i, next_j))
        group += 1
# print(visited)
# print(group_numblack)
# print(group_numwhite)

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

Submission status: Runtime Error

Solution code:
import sys
fin = sys.stdin.readline
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)]
# print(S)

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)

# DFS
group = 0
for i in range(H):
    for j in range(W):
        dfs_visit(i, j, visited, group)
        # stack = [(i, j)]
        # while stack:
        #     i, j = stack.pop()
        #     if visited[i][j]:
        #         continue
        #     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:
        #             stack.append((next_i, next_j))
        group += 1
# print(visited)
# print(group_numblack)
# print(group_numwhite)

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

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n):
        self.v = [-1 for _ in range(n)]  # 根(負): 連結頂点数 * (-1) / 子(正): 根の頂点番号(0-indexed)

    def find(self, x):  # xを含む木における根の頂点番号を返す
        if self.v[x] < 0:  # (負)は根
            return x
        else:  # 根の頂点番号
            self.v[x] = self.find(self.v[x])  # uniteでは, 旧根に属する頂点の根が旧根のままなので更新
            return self.v[x]

    def unite(self, x, y):  # 違う根に属していたらrankが低くなるように連結
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if -self.v[x] < -self.v[y]:  # size比較, 　(-1) * (連結頂点数 * (-1)), (正)同士の大小比較
            x, y = y, x  # 連結頂点数が少ない方をyにすると, findでの更新回数が減る？
        self.v[x] += self.v[y]  # 連結頂点数の和を取る, 連結頂点数 * (-1)
        self.v[y] = x  # 連結頂点数が少ないy(引数yの根の頂点番号)の根をx(引数xの根の頂点番号)にする

    def root(self, x):
        return self.v[x] < 0  # (負)は根

    def same(self, x, y):
        return self.find(x) == self.find(y)  # 同じ根に属するか

    def size(self, x):
        return -self.v[self.find(x)]  # 連結頂点数を返す


dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]

H, W = map(int, input().split())
s = [input() for _ in range(H)]
uf = UnionFind(2 * H * W)  # 全頂点 * 2
for r in range(H):
    for c in range(W):
        if s[r][c] == '#':
            for i in range(4):
                nr = r + dr[i]
                nc = c + dc[i]
                if 0 <= nr < H and 0 <= nc < W:
                    if s[nr][nc] == '.':
                        uf.unite(r * W + c, (nr * W + nc) * 2)  # #: *1, .: * 2
        else:
            for i in range(4):
                nr = r + dr[i]
                nc = c + dc[i]
                if 0 <= nr < H and 0 <= nc < W:
                    if s[nr][nc] == '#':
                        uf.unite((r * W + c) * 2, nr * W + nc)  # #: *1, .: * 2

ans = 0
for r in range(H):
    for c in range(W):
        if uf.root(r * W + c):
            sz = uf.size(r * W + c)

            wt = sz // 2
            bk = sz - wt
            ans += wt * bk

        elif uf.root((r * W + c) * 2):
            sz = uf.size((r * W + c) * 2)

            bk = sz // 2
            wt = sz - wt
            ans += wt * bk

print(ans)

Submission status: Runtime Error

Solution code:
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
    #print(a, b)
    

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

    if grid[a][b] == "#" and lastColor != -1:
        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)
        #print(x, y, blackSeen, whiteSeen)
        tot += blackSeen * whiteSeen

print(tot)

Submission status: Runtime Error

Solution code:
def dfs(x, y, c):
	d[x, y] = c
	if S[x][y] == '#':
		black[c] += 1
	else:
		white[c] += 1 
	for u, v in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
		if u < 0 or u >= H or v < 0 or v >= W:
			continue
		if d[u, v] != -1:
			continue
		if S[x][y] == '#' and S[u][v] == '.':
			dfs(u, v, c)
		if S[x][y] == '.' and S[u][v] == '#':
			dfs(u, v, c)

H, W = map(int, input().split())
S = []
for i in range(H):
	S.append(input())
d = {}
for i in range(H):
	for j in range(W):
		d[i, j] = -1
count = 0
black = {0: 0}
white = {0: 0}
for i in range(H):
	for j in range(W):
		if d[i, j] == -1:
			dfs(i, j, count)
			count += 1
			black[count] = 0
			white[count] = 0
ans = 0
for i in range(count):
	ans += black[i] * white[i]
print(ans)

Submission status: Runtime Error

Solution code:
import sys 

sys.setrecursionlimit(100000)

def dfs(row, column, black):
    global S, H, W, X, Y, visited, ans
    if black:
        for dx, dy in zip(X, Y):
            n_row = row + dx
            n_column = column + dy
            if 0 <= n_row < H and 0 <= n_column < W:
                if visited[n_row][n_column] == False and S[n_row][n_column] == '.':
                    visited[n_row][n_column] = True
                    ans += 1
                    dfs(n_row, n_column, False)
    
    else:
        for dx, dy in zip(X, Y):
            n_row = row + dx
            n_column = column + dy
            if 0 <= n_row < H and 0 <= n_column < W:
                if visited[n_row][n_column] == False and S[n_row][n_column] == '#':
                    visited[n_row][n_column] = True
                    dfs(n_row, n_column, True)






if __name__ == "__main__":
    H, W = map(int, input().split())

    S = [None] * H
    X = [0, 0, 1, -1]
    Y = [1, -1, 0, 0]
    for i in range(H):
        S[i] = list(input())
    black_row = []
    black_column = []
    for row in range(H):
        for column in range(W):
            if S[row][column] == "#":
                black_row.append(row)
                black_column.append(column)
    ans = 0
    for row, column in zip(black_row, black_column):
        visited = [[False] * W for i in range(H)]
        dfs(row, column, True)
    print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!

#n = int(input())
import sys

sys.setrecursionlimit(100000)

h,W = [int(i) for i in input().split()]
#b = [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]
#        print(nx,ny)
#        print(checked)
        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
#        print("ok")
        checked[nx][ny]=1
        if board[nx][ny] == '#':
            b+=1
        else:
            w+=1
        b1,w1 = dfs(nx, ny,0,0)
        b+=b1
        w+=w1
#    print(x,y,b,w)
    return b,w

#print(dfs(0,0,0,0))

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)
#        print(b1,w1)
        ans += b1*w1

print(ans)

Submission status: Runtime Error

Solution code:
def dfs(row, column, black):
    global S, H, W, X, Y, visited, ans
    if black:
        for dx, dy in zip(X, Y):
            n_row = row + dx
            n_column = column + dy
            if 0 <= n_row < H and 0 <= n_column < W:
                if visited[n_row][n_column] == False and S[n_row][n_column] == '.':
                    visited[n_row][n_column] = True
                    ans += 1
                    dfs(n_row, n_column, False)
    
    else:
        for dx, dy in zip(X, Y):
            n_row = row + dx
            n_column = column + dy
            if 0 <= n_row < H and 0 <= n_column < W:
                if visited[n_row][n_column] == False and S[n_row][n_column] == '#':
                    visited[n_row][n_column] = True
                    dfs(n_row, n_column, True)






if __name__ == "__main__":
    H, W = map(int, input().split())

    S = [None] * H
    X = [0, 0, 1, -1]
    Y = [1, -1, 0, 0]
    for i in range(H):
        S[i] = list(input())
    black_row = []
    black_column = []
    for row in range(H):
        for column in range(W):
            if S[row][column] == "#":
                black_row.append(row)
                black_column.append(column)
    ans = 0
    for row, column in zip(black_row, black_column):
        visited = [[False] * W for i in range(H)]
        dfs(row, column, True)
    print(ans)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(400*400)

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)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!

#n = int(input())
h,W = [int(i) for i in input().split()]
#b = [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]
#        print(nx,ny)
#        print(checked)
        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
#        print("ok")
        checked[nx][ny]=1
        if board[nx][ny] == '#':
            b+=1
        else:
            w+=1
        b1,w1 = dfs(nx, ny,0,0)
        b+=b1
        w+=w1
#    print(x,y,b,w)
    return b,w

#print(dfs(0,0,0,0))

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)
#        print(b1,w1)
        ans += b1*w1

print(ans)