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:
#encoding:utf-8

import numpy as np
import sys
sys.setrecursionlimit(1000000)

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

S_ = np.array(S)

def count_answer(x,y,num_b,num_w):
    # print(used)
    # global num_b,num_w
    count = 0
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    # print("x,y:",x,y)
    for i in range(4):
        next_x = x + dx[i]
        next_y = y + dy[i]
        # print(next_x,next_y)
        used[next_x][next_y] = 1
        if next_x == -1 or next_y == -1:
            pass
        elif next_x >= H or next_y >= W:
            pass
        elif used[next_x][next_y] == 1:
            pass
        elif S_[next_x][next_y] != S_[x][y]:
            if S_[next_x][next_y] == "#":
                num_b += 1
            else:
                num_w += 1
            num_b,num_w = count_answer(next_x,next_y,num_b,num_w)
    return num_b,num_w

answer = 0
used = np.zeros((H,W))
for i in range(H):
    for j in range(W):
        if used[i][j] == 1:
            pass
        elif S_[i,j] == "#":
            num_b = 0
            num_w = 0
            num_b,num_w  = count_answer(i,j,num_b,num_w)
            answer += num_b*num_w
print(answer)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin

s_in = lambda: stdin.readline()[:-1]  # s = s_in()
d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


H, W = ds_in()
s_list = []
for _ in range(H):
    s_list.append(s_in())
parents = [[-1] * W for _ in range(H)]

group = {}
for i in range(H):
    for j in range(W):
        idx = i * W + j
        parents[i][j] = idx
        group[idx] = [0, 0]  # [black, white]
        if s_list[i][j] == '#':
            group[idx][0] = 1
        else:
            group[idx][1] = 1

        if i > 0:
            if s_list[i][j] != s_list[i-1][j]:
                parents[i][j] = parents[i-1][j]
                group[parents[i][j]][0] += group[idx][0]
                group[parents[i][j]][1] += group[idx][1]
                del group[idx]
        if j > 0:
            if s_list[i][j] != s_list[i][j-1]:
                if parents[i][j] == idx:
                    # [i][j]未更新
                    parents[i][j] = parents[i][j-1]
                    group[parents[i][j]][0] += group[idx][0]
                    group[parents[i][j]][1] += group[idx][1]
                    del group[idx]
                elif parents[i][j] != parents[i][j-1]:
                    # [i][j]更新済み
                    group[parents[i][j]][0] += group[parents[i][j-1]][0]
                    group[parents[i][j]][1] += group[parents[i][j-1]][1]
                    del group[parents[i][j-1]]

ans = 0
for _, g in group.items():
    ans += g[0] * g[1]
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)

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

    graph = [[[]for _ in range(W)] for _ in range(H)]
    visited = [[0 for _ in range(W)] for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if S[i][j] == ".":
                continue
            if S[max(i - 1, 0)][j] == ".":
                graph[max(i - 1, 0)][j].append((i,j))
                graph[i][j].append((max(i - 1, 0),j))

            if S[min(i+1, H-1)][j] == ".":
                graph[min(i + 1, H - 1)][j].append((i,j))
                graph[i][j].append((min(i + 1, H - 1),j))

            if S[i][max(j - 1, 0)] == ".":
                graph[i][max(j - 1, 0)].append((i,j))
                graph[i][j].append((i,max(j - 1, 0)))

            if S[i][min(j+1, W-1)] == ".":
                graph[i][min(j + 1, W - 1)].append((i,j))
                graph[i][j].append((i,min(j+1, W-1)))

    bw = [0] * 2
    def dfs(g):
        for a,b in g:
            if visited[a][b] == 1:
                continue
            visited[a][b] = 1
            if S[a][b] == ".":
                bw[0] += 1
            else:
                bw[1] += 1
            dfs(graph[a][b])

    ans = 0
    for i in range(H):
        for j in range(W):
            if visited[a][b] == 1:
                continue
            bw[0], bw[1] = 0, 0
            dfs(graph[i][j])
            ans += bw[0] * bw[1]

    return ans

print(m())

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

# AISing Programming Contest 2019：C - Alternating Path


H, W = [int(i) for i in raw_input().strip().split(' ')]
S = []
for _ in range(H):
    S.append(raw_input().strip())
C = '#.'
CR = {'#':0, '.':1}


def find(h, w, sumi):
    while True:
        if sumi[h][w] == False:
            return (h, w)
        w += 1
        if w >= W:
            w = 0
            h += 1
            if h >= H:
                return None
    return None


def chain((h, w), t, c, sumi):
    if 0 <= h < H and 0 <= w < W:
        pass
    else:
        return c
    if sumi[h][w]:
        return c
    if S[h][w] == C[t]:
        sumi[h][w] = True
        c[t] += 1
        for ptr in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
            c = chain((h+ptr[0], w+ptr[1]), 1-t, c, sumi)
        return c
    return c


def main():
    sumi = [[False for _ in range(W)] for _ in range(H)]
    h, w = 0, 0
    n = 0
    while True:
        c = [0, 0]
        # print 'sumi:', sumi
        result = find(h, w, sumi)
        if not result:
            break
        h, w = result[0], result[1]
        # print 'found:', h, w
        c = chain((h, w), CR[S[h][w]], c, sumi)
        # print c
        n += c[0] * c[1]
    print n


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
h,w = [int(i) for i in input().split()]
board = [input() for _ in range(h)]

used = [[0]*w for _ in range(h)]
dx=[ 0, 1, 0,-1]
dy=[ 1, 0,-1, 0]

def dfs(x, y):
    global numb, numw #numbたちがグローバル変数だと教えてあげる
    #(x,y)地点を訪問済みにする
    used[x][y] = 1
    #(x,y)地点での処理を行う（マスの色をカウントするなど）
    if board[x][y] == '#':
        numb += 1
    else:
        numw += 1
    #foreach((nx,ny) \in (x,y)のお隣さん){(nx,ny)に訪問していないとき、dfs(nx,ny)} 
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or nx >= h or ny < 0 or ny >= w or used[nx][ny] == 1: continue #範囲外参照 or (nx,ny)は確認済み スキップ
        if board[x][y]!=board[nx][ny]: #さらに(nx,ny)と(x,y)がつながっている場合(nx,ny)を訪問
            dfs(nx,ny)
    return #情報をもらうとき：返り値、各地点の情報のみで更新：グローバル変数、情報を送るとき：引数

ans=0
for i in range(h):
    for j in range(w):
        numw = 0
        numb = 0
        if used[i][j] == 1: continue #すでに確認した地点は見ない
        dfs(i,j)
        ans += numw*numb

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import deque

@np.vectorize
def trans(s):
    return 1 if s == "#" else 0

def parse(inp):
    H, W = map(int, next(inp).split())
    return np.array([trans([w for w in next(inp).strip()]) for _ in range(H)])

def search(S, start, C):
    Q = deque([start])
    H, W = S.shape
    n0 = 0
    n1 = 0
    while Q:
        i, j = Q.popleft()
        if C[i, j] != 0:
            continue
        else:
            C[i, j] = 1
            if S[i, j] == 0:
                n0 += 1
            else:
                n1 += 1
        if i + 1 < H and C[i+1, j] == 0 and S[i, j] != S[i+1, j]:
            Q.append((i + 1, j))
        if i > 0 and C[i-1, j] == 0 and S[i, j] != S[i-1, j]:
            Q.append((i - 1, j))
        if j + 1 < W and C[i, j+1] == 0 and S[i, j] != S[i, j+1]:
            Q.append((i, j + 1))
        if j > 0 and C[i, j-1] == 0 and S[i, j] != S[i, j-1]:
            Q.append((i, j - 1))
    return n0, n1


def search_all(S):
    C = np.full_like(S, 0)
    D = np.full_like(S, 0)
    ret = 0
    for i in range(S.shape[0]):
        for j in range(S.shape[1]):
            if D[i, j] == 0:
                n0, n1 = search(S, (i, j), C)
                D += C
                ret += n1 * n0
                if np.all(D):
                    return ret
                else:
                    C[:, :] = 0

    
print(search_all(parse(sys.stdin)))

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra

@np.vectorize
def trans(s):
    return 1 if s == "#" else 0

H, W = map(int, input().split())
S = np.array([trans([w for w in input()]) for _ in range(H)]).flatten()

def adjacency_matrix(H, W):
    t1 = [1 if i % W != W - 1 else 0 for i in range(H * W - 1)]
    t2 = [1 for _ in range(H * W - W)]
    return np.diag(t1, k=1) + np.diag(t1, k=-1) + np.diag(t2, k=W) + np.diag(t2, k=-W)
    
def different_colors(colors):
    return np.array([np.abs(colors - c) for c in colors])


ad = adjacency_matrix(H, W)
df = different_colors(S)

di = dijkstra(ad * df)
co = np.logical_and(di > 0, di < np.inf)

print(int(np.sum(co * df) / 2))

Submission status: Runtime Error

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

    graph = [[[]for _ in range(W)] for _ in range(H)]
    visited = []
    for i in range(H):
        for j in range(W):
            if S[i][j] == ".":
                continue
            if S[max(i - 1, 0)][j] == ".":
                graph[max(i - 1, 0)][j].append((i,j))
                graph[i][j].append((max(i - 1, 0),j))

            if S[min(i+1, H-1)][j] == ".":
                graph[min(i + 1, H - 1)][j].append((i,j))
                graph[i][j].append((min(i + 1, H - 1),j))

            if S[i][max(j - 1, 0)] == ".":
                graph[i][max(j - 1, 0)].append((i,j))
                graph[i][j].append((i,max(j - 1, 0)))

            if S[i][min(j+1, W-1)] == ".":
                graph[i][min(j + 1, W - 1)].append((i,j))
                graph[i][j].append((i,min(j+1, W-1)))

    bw = [0] * 2
    def dfs(g):
        for a,b in g:
            if (a,b) in visited:
                continue
            visited.append((a,b))
            if S[a][b] == ".":
                bw[0] += 1
            else:
                bw[1] += 1
            dfs(graph[a][b])

    ans = 0
    for i in range(H):
        for j in range(W):
            bw[0], bw[1] = 0, 0
            dfs(graph[i][j])
            ans += bw[0] * bw[1]

    return ans

print(m())

Submission status: Runtime Error

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

board=[]
check=[[None]*W for i in range(H)]
answer=0

for i in range(H):
  S=list(input())
  board.append(S)
  
def dfs(i,j,color):
  if not (0<=i<H and 0<=j<W):
    return 0,0
  if board[i][j]==color:
    return 0,0
  if check[i][j]:
    return 0,0
  
  check[i][j]=True
  black,white=0,0
  
  if board[i][j]=='#':
  	black+=1
  else:
    white+=1
 
  tempblack,tempwhite=dfs(i+1,j,board[i][j])
  black+=tempblack
  white+=tempwhite
  
  tempblack,tempwhite=dfs(i-1,j,board[i][j])
  black+=tempblack
  white+=tempwhite
  
  tempblack,tempwhite=dfs(i,j+1,board[i][j])
  black+=tempblack
  white+=tempwhite

  tempblack,tempwhite=dfs(i,j-1,board[i][j])
  black+=tempblack
  white+=tempwhite
  return black,white

for i in range(H):
  for j in range(W):
    black,white=dfs(i,j,"!")
    answer+=black*white
print(answer)

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
s_array = ["+" * (w + 2)]
for i in range(h):
    s_array.append("+" + input() + "+")
else:
    s_array.append("+" * (w + 2))
moving = [[0, 1], [0, -1], [1, 0], [-1, 0]]
visit = [[False for x in range(w+2)] for x in range(h+2)]


def recursive(mark, mark_point, mark_sharp, row, point):
    # 訪問済みならreturn
    if visit[row][point]:
        return mark_point, mark_sharp
    else:
        visit[row][point] = True

    for x, y in moving:
        # 範囲外かどうかと連結かどうか
        if s_array[row + x][point + y] != "+" and s_array[row + x][point + y] != s_array[row][point]:
            if visit[row+x][point+y]:
                continue
            # 移動先のマークの確認
            if s_array[row + x][point + y] == "#":
                mark_sharp += 1
            else:
                mark_point += 1
            mark_point, mark_sharp = recursive(mark, mark_point, mark_sharp, row + x, point + y)
    else:
        return mark_point, mark_sharp


res = 0
for row in range(1, h + 1):
    for point in range(1, w + 1):
        m, n = recursive(s_array[1][1], s_array[1][1].count("."), s_array[1][1].count("#"), row, point)
        res += m*n
print(res)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
S = []
for i in [0]*H:
    l = input()
    S.append([1 if x == "#" else -1 for x in l])

bk = 0
wh = 0
def check(S, x, y):
    global bk, wh
    n = S[y][x]
    if n == 0:
        return 
    elif n == 1:
        bk += 1
    elif n == -1:
        wh += 1
    S[y][x] = 0
    if 0 < y and S[y-1][x] == -n:
        check(S, x, y-1)
    if 0 < x and S[y][x-1] == -n:
        check(S, x-1, y)
    if y < H-1 and S[y+1][x] == -n:
        check(S, x, y+1)
    if x < W-1 and S[y][x+1] == -n:
        check(S, x+1, y)
    return 

cnt = 0
for y in range(H):
    for x in range(W):
        if S[y][x] == 1:
            check(S, x, y)
            cnt += wh*bk
            wh = 0
            bk = 0
            
print(cnt)

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
s_list = []
for i in range(H):
    s_list.append(input())
check = [[False for _ in range(W)] for _ in range(H)]
move_x = [1, 0, -1, 0]
move_y = [0, 1, 0, -1]


def dfs(i, j):
    check[i][j] = True

    if s_list[i][j] == "#":
        cnt[0] += 1
    else:
        cnt[1] += 1

    for m in range(4):
        next_i = i + move_y[m]
        next_j = j + move_x[m]
        if 0 <= next_i < H and 0 <= next_j < W  and s_list[i][j] != s_list[next_i][next_j] \
                and not check[next_i][next_j]:
            dfs(next_i, next_j)


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

Submission status: Runtime Error

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


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

used = [[False for _ in range(W)] for _ in range(H)]


def dfs(x, y):
    global nb, nw
    if S[y][x] == '#':
        nb += 1
    if S[y][x] == '.':
        nw += 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or nx >= W or ny < 0 or ny >= H:
            continue
        if used[ny][nx]:
            continue
        if S[y][x] == '#' and S[ny][nx] == '#':
            continue
        if S[y][x] == '.' and S[ny][nx] == '.':
            continue
        used[ny][nx] = True
        dfs(nx, ny)

ans = 0
for i in range(H):
    for j in range(W):
        if not used[i][j]:
            used[i][j] = True
            nb = 0
            nw = 0
            dfs(j, i)
            ans += nb*nw
print(ans)

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] !=  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(200000)

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

move = ((1, 0), (-1, 0), (0, 1), (0, -1))
visited = [[False] * W for _ in range(H)]
b, w = 0, 0

def dfs(i, j):
    global b, w

    visited[i][j] = True

    if S[i][j] == '#':
        b += 1
    else:
        w += 1

    for di, dj in move:
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W:
            if S[i][j] != S[ni][nj] and not visited[ni][nj]:
                dfs(ni, nj)


result = 0
for i in range(H):
    for j in range(W):
        if visited[i][j]:
            continue
        b, w = 0, 0
        dfs(i, j)
        result += b * w
print(result)

Submission status: Runtime Error

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

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

visited = [[False] * W for _ in range(H)]

b, w = 0, 0

def dfs(i, j):
    global b, w, visited

    if visited[i][j]:
        return
    visited[i][j] = True

    if S[i][j] == '#':
        b += 1
    else:
        w += 1

    for di, dj in move:
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W and S[i][j] != S[ni][nj]:
            dfs(ni, nj)


result = 0
for i in range(H):
    for j in range(W):
        b, w = 0, 0
        dfs(i, j)
        result += b * w
print(result)

Submission status: Runtime Error

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

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

visited = [[False] * W for _ in range(H)]

b, w = 0, 0

def dfs(i, j):
    global b, w

    if visited[i][j]:
        return
    visited[i][j] = True

    if S[i][j] == '#':
        b += 1
    else:
        w += 1

    for di, dj in move:
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W and S[i][j] != S[ni][nj]:
            dfs(ni, nj)


result = 0
for i in range(H):
    for j in range(W):
        b, w = 0, 0
        dfs(i, j)
        result += b * w
print(result)

Submission status: Runtime Error

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

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

visited = [[False] * W for _ in range(H)]

b, w = 0, 0

def dfs(i, j):
    global b, w

    if visited[i][j]:
        return
    visited[i][j] = True

    if S[i][j] == '#':
        b += 1
    else:
        w += 1

    for di, dj in move:
        ni, nj = i + di, j + dj
        if ni < 0 or H <= ni or nj < 0 or W <= nj:
            continue
        if S[i][j] == S[ni][nj]:
            continue
        dfs(ni, nj)


result = 0
for i in range(H):
    for j in range(W):
        b, w = 0, 0
        dfs(i, j)
        result += b * w
print(result)

Submission status: Runtime Error

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

di = (1, 0, -1, 0)
dj = (0, 1, 0, -1)
visited = [[False] * W for _ in range(H)]

b, w = 0, 0

def dfs(i, j):
    global b, w

    if visited[i][j]:
        return 0, 0
    visited[i][j] = True

    if S[i][j] == '#':
        b += 1
    else:
        w += 1

    for d in range(4):
        ni, nj = i + di[d], j + dj[d]
        if ni < 0 or H <= ni or nj < 0 or W <= nj:
            continue
        if S[i][j] == S[ni][nj]:
            continue
        dfs(ni, nj)


result = 0
for i in range(H):
    for j in range(W):
        b, w = 0, 0
        dfs(i, j)
        result += b * w
print(result)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2000)

def dfs(i,j):
    for m in move:
        ni = i + m[0]
        nj = j + m[1]
        if ni < 0 or ni >= H or nj < 0 or nj >= W:
            continue
        if ch[ni][nj]:
            continue
        if X[i][j] == X[ni][nj]:
            continue
            
        ch[ni][nj] = 1
        K[(ni+nj)%2] += 1
        dfs(ni, nj)
        
H, W = map(int, input().split())
X = [[[0, 1][a=="#"] for a in input()] for i in range(H)]
ch = [[0] * W for _ in range(H)]
    
move = [[0,1], [0,-1], [1,0], [-1,0]]

K = [0, 0]
ans = 0
for i in range(H):
    for j in range(W):
        if ch[i][j] > 0:
            continue
        ch[i][j] = 1
        K = [0, 0]
        K[(i+j)%2] = 1
        dfs(i, j)
        ans += K[0] * K[1]
        
print(ans)

Submission status: Runtime Error

Solution code:
import random

def search(group, current_h, current_w, group_index, prev):
    num = 0
    if not(current_h > -1 and current_w > -1 and current_h < H and current_w < W):
        return num
    if searched_map[current_h][current_w]:
        return num
    current = s_map[current_h][current_w]
    if current == prev:
        return num
    searched_map[current_h][current_w] = True

    if (current == '.'):
        num += 1
    else:
        group[current_h][current_w] = group_index
    num += search(group, current_h+1, current_w, group_index, s_map[current_h][current_w])
    num += search(group, current_h-1, current_w, group_index, s_map[current_h][current_w])
    num += search(group, current_h, current_w+1, group_index, s_map[current_h][current_w])
    num += search(group, current_h, current_w-1, group_index, s_map[current_h][current_w])
    return num

'''
def nsin(X, n):
    if(int(X/n)):
        return nsin(int(X/n), n)+str(X % n)
    return str(X % n)
'''


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


'''
n = 2**(W*H)
for try_num in range(n):
    b = list(nsin(try_num, 2))
    A = []
    cnt = 0
    for j in range(H):
        s = ''
        for i in range(W):
            c = '.'
            if len(b) > cnt:
                if b[cnt] == '1':
                    c = '#'
            s += c
            cnt += 1
        A.append(s)
'''

'''
W = 400
H = 400

A = []
for j in range(H):
    s = ''
    for i in range(W):
        v = random.random()
        c = '.'
        if v < 0.5:
            c = '#'
        s += c
    A.append(s)
print(A)
'''


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


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 = {}
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
.....
.....
.###.
.###.
.....
'''

'''
2 1
#
.
'''

Submission status: Runtime Error

Solution code:
H,W = map(int,input().split())
grid = [["&"] * (W+2) for i in range(H+2)]
visited = [[False] * (W+2) for i in range(H+2)]
# debug: visited_count = [[0] * (W+2) for i in range(H+2)]
start = []
for i in range(H):
    s = input()
    for j in range(W):
        grid[i+1][j+1] = s[j]
        if s[j] == ".":
            start.append([i+1,j+1])

ans = 0
b = 0
w = 0
def dfs(p_i,p_j):
    if visited[p_i][p_j] is True:
        global ans
        return
    visited[p_i][p_j] = True
    if grid[p_i][p_j] == "#":
        # debug: visited_count[p_i][p_j] += 1
        global b
        b += 1
    elif grid[p_i][p_j] == ".":
        start.remove([p_i,p_j])
        # debug: visited_count[p_i][p_j] += 1
        global w
        w += 1
    around = [[p_i,p_j+1],[p_i+1,p_j],[p_i,p_j-1],[p_i-1,p_j]]
    for i,j in around:
        if grid[p_i][p_j] == "#" and grid[i][j] == ".":
            dfs(i,j)
        elif grid[p_i][p_j] == "." and grid[i][j] == "#":
            dfs(i,j)

while True:
    if start == []:
        break
    dfs(start[0][0],start[0][1])
    ans += b * w
    b = 0
    w = 0

print(ans)

""" debug
print(start)
for line in visited_count:
    print(line)
print("b = {}".format(b))
print("w = {}".format(w)) """

Submission status: Runtime Error

Solution code:
def dfs(i,j):
    # print("dfs", i, j)
    for m in move:
        ni = i + m[0]
        nj = j + m[1]
        if ni < 0 or ni >= H or nj < 0 or nj >= W:
            continue
        if ch[ni][nj]:
            continue
        if X[i][j] == X[ni][nj]:
            continue
            
        ch[ni][nj] = 1
        K[(ni+nj)%2] += 1
        dfs(ni, nj)
        
H, W = map(int, input().split())
X = [[[0, 1][a=="#"] for a in input()] for i in range(H)]
ch = [[0] * W for _ in range(H)]
    
move = [[0,1], [0,-1], [1,0], [-1,0]]

K = [0, 0]
ans = 0
for i in range(H):
    for j in range(W):
        if ch[i][j] > 0:
            continue
        ch[i][j] = 1
        K = [0, 0]
        K[(i+j)%2] = 1
        dfs(i, j)
        ans += K[0] * K[1]
        # print(K)
print(ans)

Submission status: Runtime Error

Solution code:
def check(i, j):
  T = []
  if i >= 1:
    if M[i-1][j] == 0:
      if D[i][j] != D[i-1][j]:
        T.append((i-1, j))
        M[i-1][j] = 1
        T.extend(check(i-1, j))
  if i < H - 1:
    if M[i+1][j] == 0:
      if D[i][j] != D[i+1][j]:
        T.append((i+1, j))
        M[i+1][j] = 1
        T.extend(check(i+1,j))
  if j >= 1:
    if M[i][j-1] == 0:
      if D[i][j] != D[i][j-1]:
        T.append((i, j-1))
        M[i][j-1] = 1
        T.extend(check(i, j-1))
  if j < W - 1:
    if M[i][j+1] == 0:
      if D[i][j] != D[i][j+1]:
        T.append((i, j+1))
        M[i][j+1] = 1
        T.extend(check(i, j+1))
  return T

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

D = []
for i in range(H):
  D.append(input())

M = [[0] * W for i in range(H)]
L = []
for i in range(H):
  for j in range(W):
    if M[i][j] == 0:
      L.append(check(i, j))

cnt = 0
for i in L:
  E = 0
  A = 0
  for j in i:
    if (j[0] + j[1]) % 2 == 0:
      E += 1
    else:
      A += 1
  cnt += E * A
print(cnt)

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
X = [[0] * W for _ in range(H)]
ch = [[0] * W for _ in range(H)]
for i in range(H):
    s = input()
    for j in range(W):
        if ((i + j)%2 == 0) ^ (s[j] == "#"):
            X[i][j] = 1
    
move = [[0,1], [0,-1], [1,0], [-1,0]]

def dfs(i,j):
    for m in move:
        ni = i+ m[0]
        nj = j + m[1]
        if ni < 0 or ni >= H or nj < 0 or nj >= W:
            continue
        if ch[ni][nj]:
            continue
        if X[i][j] != X[ni][nj]:
            continue
            
        ch[ni][nj] = 1
        K[(ni+nj)%2] += 1
        dfs(ni, nj)

K = [0, 0]
k = -1
ans = 0
for i in range(H):
    for j in range(W):
        if ch[i][j] > 0:
            continue
        ch[i][j] = 1
        K = [0, 0]
        K[(i+j)%2] = 1
        dfs(i, j)
        ans += K[0] * K[1]
print(ans)

Submission status: Runtime Error

Solution code:
import random

def search(search_map, group, current_h, current_w, group_index, prev):
    num = 0
    # if not(current_h > -1 and current_w > -1 and current_h < H and current_w < W):
    if not(current_h > 0 and current_w > 0 and current_h < H-1 and current_w < W-1):
        return num
    if current_h in search_map:
        if current_w in search_map[current_h]:
            return num
    current = s_map[current_h][current_w]
    if current == prev:
        return num
    if current_h not in search_map:
        search_map[current_h] = {}
    search_map[current_h][current_w] = True

    if (current == '.'):
        num += 1
    else:
        group[current_h][current_w] = group_index
    num += search(search_map, group, current_h+1, current_w, group_index, s_map[current_h][current_w])
    num += search(search_map, group, current_h-1, current_w, group_index, s_map[current_h][current_w])
    num += search(search_map, group, current_h, current_w+1, group_index, s_map[current_h][current_w])
    num += search(search_map, group, current_h, current_w-1, group_index, s_map[current_h][current_w])
    return num

'''
def nsin(X, n):
    if(int(X/n)):
        return nsin(int(X/n), n)+str(X % n)
    return str(X % n)


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


'''
n = 2**(W*H)
for try_num in range(n):
    b = list(nsin(try_num, 2))
    A = []
    cnt = 0
    for j in range(H):
        s = ''
        for i in range(W):
            c = '.'
            if len(b) > cnt:
                if b[cnt] == '1':
                    c = '#'
            s += c
            cnt += 1
        A.append(s)
'''


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
.....
.....
.###.
.###.
.....
'''