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().split())
S = [input() for i in range(H)]


b_list = []
for row in S:
    tmp_raw = []
    for j, t in enumerate(row):
        if t == '#':
            tmp_raw.append(j)
    b_list.append(tmp_raw)
tmp = -1
res = {}
raw_before = []
for i, raw in enumerate(b_list):
    res[i] = {}
    for j in raw:
        res[i][j] = []
        if not((j - 1) in raw or j == 0):
            res[i][j].append((i, j-1))
        if not((j + 1) in raw or j == W -1):
            res[i][j].append((i, j+1))
        if not(i == 0 or j in raw_before):
            res[i][j].append((i-1, j))
        if not(i == H - 1):
            if not(j in b_list[i+1]):
                res[i][j].append((i+1, j))
    raw_before = raw



before = 0
for i, raw in enumerate(b_list):
    for j in raw:
         before += len(res[i][j])
while True:
    for i, raw in enumerate(b_list):
        for j in raw:
            try:
                if S[i-1][j] == '.' or S[i][j-1] == '.':
                    res[i][j] += res[i-1][j-1]
            except:
                pass
            try:
                if S[i+1][j] == '.' or S[i][j-1] == '.':
                    res[i][j] += res[i+1][j-1]
            except:
                pass
            try:
                if S[i-1][j] == '.' or S[i][j+1] == '.':
                    res[i][j] += res[i-1][j+1]
            except:
                pass
            try:
                if S[i+1][j] == '.' or S[i][j+1] == '.':
                    res[i][j] += res[i+1][j+1]
            except:
                pass
    before = result
    for i, raw in enumerate(b_list):
        for j in raw:
            res[i][j] = list(set(res[i][j]))
    result = 0
    for i, raw in enumerate(b_list):
        for j in raw:
             result += len(res[i][j])
    if before == result:
        break
print(result)

Submission status: Runtime Error

Solution code:
import itertools
import sys
sys.setrecursionlimit(2000)
h, w = map(int, input().split())
s_list = []
for i in range(h):
  s_list.append(list(input()))
res = 0
check_list = set()

def rec_create_area(point, tmp_area, current_str):
  new_point_list = []
  new_point_list.append((point[0] + 1, point[1]))
  new_point_list.append((point[0], point[1] + 1))
  new_point_list.append((point[0] - 1, point[1]))
  new_point_list.append((point[0], point[1] - 1))
  for new_point in new_point_list:
    if new_point[0] >= h or new_point[1] >= w or new_point[0] < 0 or new_point[1]  < 0:
      continue
    if new_point in check_list:
      continue
    new_str = s_list[new_point[0]][new_point[1]]
    if new_str == current_str:
      continue
    if new_str == "#":
      tmp_area[0] += 1
    else:
      tmp_area[1] += 1
    check_list.add(new_point)
    rec_create_area(new_point, tmp_area, new_str)
  
for a, b in itertools.product(range(h), range(w)):
  check_point = (a, b)
  if check_point in check_list:
    continue
  check_list.add(check_point)
  current_str = s_list[0][0]
  if current_str == "#":
    tmp_area = [1, 0]
  else:
    tmp_area = [0, 1]
  rec_create_area(check_point, tmp_area, current_str)
  res += tmp_area[0] * tmp_area[1]
  
print(res)

Submission status: Runtime Error

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

INF = int(1e12)

def dfs(h, w, p):
    b_cnt = 0
    w_cnt = 0
    if h < 0 or h >= H or w < 0 or w >= W:
        return 0, 0
    if S[h][w] == p or S[h][w] == 'x':
        return 0, 0
    if S[h][w] == '#':
        b_cnt += 1
    elif S[h][w] == '.':
        w_cnt += 1
    t = S[h][w]
    S[h][w] = 'x'

    for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
        res = dfs(h + dh, w + dw, t)
        b_cnt += res[0]
        w_cnt += res[1]

    return (b_cnt, w_cnt)

ans = 0

for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            b_cnt, w_cnt = dfs(h, w, '.')
            ans += b_cnt * w_cnt

print(ans)

Submission status: Runtime Error

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

color = [["." for i in range(W)] for j in range(H)]
  
def path(h, w, col):
  global color
  if color[h][w] == ".":
    color[h][w] = col
    if h > 0:
      if mas[h-1][w] != mas[h][w]:
        path(h-1, w, col)
    if w > 0:
      if mas[h][w-1] != mas[h][w]:
        path(h, w-1, col)
    if h < H-1:
      if mas[h+1][w] != mas[h][w]:
        path(h+1, w, col)
    if w < W-1:
      if mas[h][w+1] != mas[h][w]:
        path(h, w+1, col)
    
col=0
for i in range(H):
  for j in range(W):
    if color[i][j] == ".":
      path(i, j, col)
      col+=1

dic = {i:[0,0] for i in range(col)}
for i in range(H):
  for j in range(W):
    if mas[i][j] == "#":
      dic[color[i][j]][0] +=1
    else:
      dic[color[i][j]][1] +=1

ans=0
for i in range(col):
  ans += dic[i][0] * dic[i][1]
  
print(ans)

Submission status: Runtime Error

Solution code:
import itertools
H, W = [int(_) for _ in input().split()]
S = [input() for _ in range(H)]
A = [[0 for _ in range(W)] for _ in range(H)]
count = {}


def bfs(x, y, p, q):
    if A[x][y] == 1:
        return
    else:
        A[x][y] = 1
        count[p * H + q] = count.get(p * H + q, {})
        count[p * H + q]['#'] = count[p * H + q].get('#', 0)
        count[p * H + q]['.'] = count[p * H + q].get('.', 0)
        count[p * H + q][S[x][y]] += 1
        dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W:
                if S[x][y] != S[nx][ny] and A[nx][ny] == 0:
                    bfs(nx, ny, p, q)


for i, j in itertools.product(range(H), range(W)):
    bfs(i, j, i, j)
ans = 0
for i in count:
    ans += count[i].get('#', 0) * count[i].get('.', 0)
print(ans)

Submission status: Runtime Error

Solution code:
h, w = map(int,raw_input().split())
oarr = [[] for i in range(h)]
blacks = []
for i in range(h):
    s = raw_input()
    for j in range(w):
        if s[j] == "#":
            oarr[i].append(1)
            blacks.append([i,j])
        else:
            oarr[i].append(0)
dire = [[1,0],[-1,0],[0,1],[0,-1]]
target = 1
ans = 0


def dfs(x,y):
    global target, ans, length
    if arr[x][y] != 2 and arr[x][y] == target:
        copy = target
        if target == 0:
            if [each_cp, [x,y]] not in cp_arr:
                cp_arr.append([each_cp, [x,y]])
                ans += 1
        # print "target:", target, "x, y:", "(", x, ",", y,")", "ans:", ans
        target = 1 - target
        length += 1
        arr[x][y] = 2
        for cp in dire:
            if 0 <= x+cp[0] <= h-1 and 0 <= y+cp[1] <= w-1:
                dfs(x+cp[0],y+cp[1])
        arr[x][y] = copy
        target = 1 - target
        return
    return
cp_arr = []
for each_cp in blacks:
    length = 0
    arr = [[] for i in range(h)]
    for i in range(h):
        for j in range(w):
            arr[i].append(oarr[i][j])
    dfs(each_cp[0], each_cp[1])
    # print "--------------"
    # print arr

print ans

Submission status: Runtime Error

Solution code:
import itertools
import sys
sys.setrecursionlimit(2000)
h, w = map(int, input().split())
s_list = []
for i in range(h):
  s_list.append(list(input()))
area_list = []
check_list = set()

def rec_create_area(point, tmp_area, current_str):
  new_point_list = []
  new_point_list.append((point[0] + 1, point[1]))
  new_point_list.append((point[0], point[1] + 1))
  new_point_list.append((point[0] - 1, point[1]))
  new_point_list.append((point[0], point[1] - 1))
  for new_point in new_point_list:
    if new_point[0] >= h or new_point[1] >= w or new_point[0] < 0 or new_point[1]  < 0:
      continue
    if new_point in check_list:
      continue
    new_str = s_list[new_point[0]][new_point[1]]
    if new_str == current_str:
      continue
    if new_str == "#":
      tmp_area[0] += 1
    else:
      tmp_area[1] += 1
    check_list.add(new_point)
    rec_create_area(new_point, tmp_area, new_str)
  
for a, b in itertools.product(range(h), range(w)):
  check_point = (a, b)
  if check_point in check_list:
    continue
  check_list.add(check_point)
  current_str = s_list[0][0]
  if current_str == "#":
    tmp_area = [1, 0]
  else:
    tmp_area = [0, 1]
  rec_create_area(check_point, tmp_area, current_str)
  area_list.append(tmp_area)
  
print(sum([x[0] * x[1] for x in area_list]))

Submission status: Runtime Error

Solution code:
h, w = map(int,raw_input().split())
oarr = [[] for i in range(h)]
blacks = []
for i in range(h):
    s = raw_input()
    for j in range(w):
        if s[j] == "#":
            oarr[i].append(1)
            blacks.append([i,j])
        else:
            oarr[i].append(0)
dire = [[1,0],[-1,0],[0,1],[0,-1]]
target = 1
ans = 0


def dfs(x,y):
    global target, ans, length
    if arr[x][y] != 2 and arr[x][y] == target:
        copy = target
        if target == 0:
            if [each_cp, [x,y]] not in cp_arr:
                cp_arr.append([each_cp, [x,y]])
                ans += 1
        # print "target:", target, "x, y:", "(", x, ",", y,")", "ans:", ans
        target = 1 - target
        length += 1
        arr[x][y] = 2
        for cp in dire:
            if 0 <= x+cp[0] <= h-1 and 0 <= y+cp[1] <= w-1:
                dfs(x+cp[0],y+cp[1])
        arr[x][y] = copy
        target = 1 - target
        return
    return
cp_arr = []
for each_cp in blacks:
    length = 0

    arr = [[] for i in range(w)]
    for i in range(h):
        for j in range(w):
            arr[i].append(oarr[i][j])
    dfs(each_cp[0], each_cp[1])
    # print "--------------"
    # print arr

print ans

Submission status: Runtime Error

Solution code:
H,W=map(int,input().split())
series = [[] for h in range(H)]
for h in range(H):
	series[h] = list(input())
check = [[0 for w in range(W)] for h in range(H)]
def Go(h,w,c):
	check[h][w]=c
	count = 0
	front = ""
	tmp=0
	if series[h][w] == "#":
		front = "."
	else:
		front = "#"
	if h >= 1:
		if series[h-1][w] == front and check[h-1][w] == 0:
			if series[h-1][w] == ".":
				count += Go(h-1,w,c)+1
			else:
				count += Go(h-1,w,c)
	if h < H-1:
		if series[h+1][w] == front and check[h+1][w] == 0:
			if series[h+1][w] == ".":
				count += Go(h+1,w,c)+1
			else:
				count += Go(h+1,w,c)
	if w >= 1:
		if series[h][w-1] == front and check[h][w-1] == 0:
			if series[h][w-1] == ".":
				count += Go(h,w-1,c)+1
			else:
				count += Go(h,w-1,c)
	if w < W-1:
		if series[h][w+1] == front and check[h][w+1] == 0:
			if series[h][w+1] == ".":
				count += Go(h,w+1,c)+1
			else:
				count += Go(h,w+1,c)
	return count

ans=0
c=1
for h in range(H):
	for w in range(W):
		if series[h][w] == "#":
			ans += Go(h,w,c)
			check = [[0 for w in range(W)] for h in range(H)]
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
h, w = list(map(int, input().split()))
ss = []
for k in range(h):
    s = input()
    ss.append(s)

field = np.zeros([h, w])
for hk in range(h):
    for wk in range(w):
        field[hk,wk] = ss[hk][wk] == '.'

import numpy as np

right = np.zeros_like(field)
right[:,:-1] = field[:,:-1] - field[:,1:] != 0
left = np.zeros_like(field)
left[:,1:] = field[:,1:] - field[:,:-1] != 0
down = np.zeros_like(field)
down[:-1,:] = field[:-1,:] - field[1:,:] != 0
up = np.zeros_like(field)
up[1:,:] = field[1:,:] - field[:-1,:] != 0

ans = {}
from itertools import product
for hk1, wk1 in product(range(h), range(w)):
    ans[(hk1, wk1)] = set()

for hk1, wk1 in product(range(h), range(w)):
    if right[hk1, wk1]:
        ans[(hk1, wk1)].add((hk1, wk1 + 1))
    if left[hk1, wk1]:
        ans[(hk1, wk1)].add((hk1, wk1 - 1))
    if up[hk1, wk1]:
        ans[(hk1, wk1)].add((hk1 - 1, wk1))
    if down[hk1, wk1]:
        ans[(hk1, wk1)].add((hk1 + 1, wk1))


def check(start, kidoku, a):
    a += 1
    nex = ans[start]
    ikeru = []
    for n in nex:
        if n in kidoku:
            pass
        else:
            kidoku.append(n)
            ikeru.append(n)
            ikeru += check(n, kidoku, a)
    return ikeru

s = 0
ends = {}
for hk1, wk1 in product(range(h), range(w)):
    if field[hk1,wk1] == 0:
        if (hk1, wk1) in ends.keys():
            s_here = ends[hk1, wk1]
        else:
            s_here = 0
            lis = check((hk1,wk1), [], 0)
            for l in lis:
                if field[l[0],l[1]] == 1:
                    s_here += 1
            ends[(hk1, wk1)] = s_here
            for l in lis:
                ends[l] = s_here
#         if s_here > 0:
#             print(hk1, wk1, s_here)
        s += s_here
print(s)

Submission status: Runtime Error

Solution code:
import itertools
H, W = [int(_) for _ in input().split()]
S = [input() for _ in range(H)]
A = [[0 for _ in range(W)] for _ in range(H)]
count = {}


def bfs(x, y, p, q):
    if A[x][y] == 1:
        return
    else:
        A[x][y] = 1
        count[p * H + q] = count.get(p * H + q, {})
        count[p * H + q]['#'] = count[p * H + q].get('#', 0)
        count[p * H + q]['.'] = count[p * H + q].get('.', 0)
        count[p * H + q][S[x][y]] += 1
        dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W:
                if S[x][y] != S[nx][ny] and A[nx][ny] == 0:
                    bfs(nx, ny, p, q)


for i, j in itertools.product(range(H), range(W)):
    bfs(i, j, i, j)
ans = 0
for i in count:
    ans += count[i]['#'] * count[i]['.']
print(ans)

Submission status: Runtime Error

Solution code:
import sys


def input():
    return sys.stdin.readline()[:-1]


def ii(t: type = int):
    return t(input())


def il(t: type = int):
    return list(map(t, input().split()))


def imi(N: int, t: type = int):
    return [ii(t) for _ in range(N)]


def iml(N: int, t: type = int):
    return [il(t) for _ in range(N)]


H, W = il()
S = imi(H, str)
sharp_pos = []
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            sharp_pos.append((i, j))
c = 0
k = 0
pre_cx, pre_cy = 0, 0

board = S[:]
C = 0


def saiki(pos_list, ignore=None):
    global C
    for cx, cy in pos_list:
        p_list = []
        if ignore is None:
            ignore = []
        wanna_char = "." if board[cx][cy] == "#" else "#"
        for d in ((-1, 0), (0, -1), (1, 0), (0, 1)):
            tx = cx + d[1]
            ty = cy + d[0]
            if (
                tx >= 0
                and ty >= 0
                and tx < H
                and ty < W
                and (tx, ty) not in ignore
                and board[tx][ty] == wanna_char
            ):
                ignore.append((cx, cy))
                p_list.append((tx, ty))
                C += 1
        saiki(p_list, ignore)


saiki(sharp_pos)
print(C)

Submission status: Runtime Error

Solution code:
def dfs(x, y, c):
	d[x, y] = c
	if S[x][y] == '#':
		black[c] = black.get(c, 0) + 1
	else:
		white[c] = white.get(c, 0) + 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(100000)

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


D=[ (1,0), (-1,0), (0,1), (0,-1) ] 
V=[ [ 0 for i in range(W) ] for j in range(H) ]

ret=0
def dfs(x,y,current):
	global ret
	V[x][y]=1
	if current==".":
		ret+=1
	else:
		ret+=0

	for dx,dy in D:
		if 0<=x+dx<H and 0<=y+dy<W:
			if V[x+dx][y+dy]==0:
				if S[x+dx][y+dy] != current:
					if current==".":
						dfs(x+dx,y+dy,"#")
					else:
						dfs(x+dx,y+dy,".")
	return ret


ans=0
for x in range(H):
	for y in range(W):
		if S[x][y]=="#":
			ret=0
			V=[ [ 0 for i in range(W) ] for j in range(H) ]
			ans+=dfs(x,y, "#")

print ans

Submission status: Runtime Error

Solution code:
def dfs(x, y, c):
	d[x, y] = c
	if S[x][y] == '#':
		black[c] = black.get(c, 0) + 1
	else:
		white[c] = white.get(c, 0) + 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 = {}
white = {}
for i in range(H):
	for j in range(W):
		if d[i, j] == -1:
			dfs(i, j, count)
			count += 1
ans = 0
for i in range(count):
	ans += black[i] * white[i]
print(ans)

Submission status: Runtime Error

Solution code:
import itertools
h, w = map(int, input().split())
s_list = []
for i in range(h):
  s_list.append(list(input()))
area_list = []
check_list = set()

def rec_create_area(point, tmp_area, current_str):
  new_point_list = []
  new_point_list.append((point[0] + 1, point[1]))
  new_point_list.append((point[0], point[1] + 1))
  new_point_list.append((point[0] - 1, point[1]))
  new_point_list.append((point[0], point[1] - 1))
  for new_point in new_point_list:
    if new_point[0] >= h or new_point[1] >= w or new_point[0] < 0 or new_point[1]  < 0:
      continue
    if new_point in check_list:
      continue
    new_str = s_list[new_point[0]][new_point[1]]
    if new_str == current_str:
      continue
    if new_str == "#":
      tmp_area[0] += 1
    else:
      tmp_area[1] += 1
    check_list.add(new_point)
    rec_create_area(new_point, tmp_area, new_str)
  
for a, b in itertools.product(range(h), range(w)):
  check_point = (a, b)
  if check_point in check_list:
    continue
  check_list.add(check_point)
  current_str = s_list[0][0]
  if current_str == "#":
    tmp_area = [1, 0]
  else:
    tmp_area = [0, 1]
  rec_create_area(check_point, tmp_area, current_str)
  area_list.append(tmp_area)
  
print(sum([x[0] * x[1] for x in area_list]))

Submission status: Runtime Error

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


D=[ (1,0), (-1,0), (0,1), (0,-1) ] 
V=[ [ 0 for i in range(W) ] for j in range(H) ]

ret=0
def dfs(x,y,current):
	global ret
	V[x][y]=1
	if current==".":
		ret+=1
	else:
		ret+=0

	for dx,dy in D:
		if 0<=x+dx<H and 0<=y+dy<W:
			if V[x+dx][y+dy]==0:
				if S[x+dx][y+dy] != current:
					if current==".":
						dfs(x+dx,y+dy,"#")
					else:
						dfs(x+dx,y+dy,".")
	return ret


ans=0
for x in range(H):
	for y in range(W):
		if S[x][y]=="#":
			ret=0
			V=[ [ 0 for i in range(W) ] for j in range(H) ]
			ans+=dfs(x,y, "#")

print ans

Submission status: Runtime Error

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

class travel:
    def __init__(self, m):
        self.ma=m
        self.ans=0
        self.dp=[[False]*W for _ in range(H)]
    def go(self, x, y, m):
        dxy=[(-1,0),(1,0),(0,-1),(0,1)]
        mark=['.','#']
        for dx,dy in dxy:
            x2=x+dx
            y2=y+dy
            if 0<= x2 < H and 0<= y2 < W:
                if self.ma[x2][y2]==mark[m] and self.dp[x2][y2]==False:
                    if m: self.ans+=1
                    self.dp[x2][y2]=True
                    self.go(x2,y2,int(not m))
    def __call__(self):
        for i in range(H):
           for j in range(W):
               if m[i][j]=='.':
                   self.dp=[[False]*W for _ in range(H)]
                   self.go(i,j,1)
        return self.ans
        
print(travel(m)())

Submission status: Runtime Error

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

color = [["." for i in range(W)] for j in range(H)]
  
def path(h, w, col):
  global color
  if color[h][w] == ".":
    color[h][w] = col
    if h > 0:
      if mas[h-1][w] != mas[h][w]:
        path(h-1, w, col)
    if w > 0:
      if mas[h][w-1] != mas[h][w]:
        path(h, w-1, col)
    if h < H-1:
      if mas[h+1][w] != mas[h][w]:
        path(h+1, w, col)
    if w < W-1:
      if mas[h][w+1] != mas[h][w]:
        path(h, w+1, col)
    
col=0
for i in range(H):
  for j in range(W):
    if color[i][j] == ".":
      path(i, j, col)
      col+=1

dic = {i:[0,0] for i in range(col+1)}
for i in range(H):
  for j in range(W):
    if mas[i][j] == "#":
      dic[color[i][j]][0] +=1
    else:
      dic[color[i][j]][1] +=1

ans=0
for i in range(col+1):
  ans += dic[i][0] * dic[i][1]
  
print(ans)

Submission status: Runtime Error

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



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

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

    return 0


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

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

print(c)

Submission status: Runtime Error

Solution code:
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):
    now = 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
            now = 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
            now = check(u+x, v+y, p)
    return now

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

print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8

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

#print(S)
for idx, gyou in enumerate(S):
    for idx2, retsu in enumerate(gyou):
        if retsu == "#":
            #print(idx, idx2)
            if idx2 == 0:
                if gyou[idx2+1] == ".":
                    cnt += 1
            elif idx2 > 0 and idx2 < W-1:
                if gyou[idx2-1] == ".":
                    cnt += 1
                if gyou[idx2+1] == ".":
                    cnt += 1
            elif idx2 == W-1:
                if gyou[idx2-1] == ".":
                    cnt += 1
            if idx == 0:
                if S[idx+1][idx2] == ".":
                    cnt += 1
            elif idx > 0 and idx < H-1:
                if S[idx-1][idx2] == ".":
                    cnt += 1
                if S[idx+1][idx2] == ".":
                    cnt += 1
            elif idx == H-1:
                if S[idx-1][idx2] == ".":
                    cnt += 1
print(cnt)

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] == '#':
            if group[i][j] != 0:
                ans += group_cnt[group[i][j]]
            else:
                cnt = search(searched_map, group, i, j, group_index)
                group_cnt[group_index] = cnt
                group_index += 1
                ans += cnt
                for h in range(H):
                    for w in range(W):
                        searched_map[h][w] = False

print(ans)

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

Submission status: Runtime Error

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

#white = ".", black = "#"
def search(x, y, color):
    if color == ".":
        for m in [1, -1]:
            if 0 <= x+m <= H-1:
                if S[x+m][y] == "#" and not dp[x+m][y]:
                    dp[x+m][y] = True
                    color = "#"
                    search(x+m, y, color)
        for n in [1, -1]:
            if 0 <= y+n <= W-1:
                if S[x][y+n] == "#" and not dp[x][y+n]:
                    dp[x][y+n] = True
                    color = "#"
                    search(x, y+n, color)

    else:
        for m in [1, -1]:
            if 0 <= x+m <= H-1:
                if S[x+m][y] == "." and not dp[x+m][y]:
                    dp[x+m][y] = True
                    color = "."
                    search(x+m, y, color)

        for n in [1, -1]:
            if 0 <= y+n <= W-1:
                if S[x][y+n] == "." and not dp[x][y+n]:
                    dp[x][y+n] = True
                    color = "."
                    search(x, y+n, color)


ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            dp = [[False for a in range(W)] for b in range(H)]
            dp[i][j] = True
            search(i, j, "#")
            for k in range(H):
                for l in range(W):
                    if dp[k][l] and S[k][l] == ".":
                        ans += 1

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
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

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))
    S = np.array(S, dtype=np.int8)
    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 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:
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
    t = check(i, j, p)
    for a, b in white:
        if t[a][b] == 1:
            ans += 1

print(ans)