Problem:


Score : 300 points

Problem Statement

There is a grid with H rows and W columns, where each square is painted black or white.

You are given H strings S_1, S_2, ..., S_H, each of length W.
If the square at the i-th row from the top and the j-th column from the left is painted black, the j-th character in the string S_i is #; if that square is painted white, the j-th character in the string S_i is ..

Find the number of pairs of a black square c_1 and a white square c_2 that satisfy the following condition:

There is a path from the square c_1 to the square c_2 where we repeatedly move to a vertically or horizontally adjacent square through an alternating sequence of black and white squares: black, white, black, white...

Constraints

1 \leq H, W \leq 400

|S_i| = W (1 \leq i \leq H)

For each i (1 \leq i \leq H), the string S_i consists of characters # and ..

Input

Input is given from Standard Input in the following format:

H W
S_1
S_2
:
S_H

Output

Print the answer.

Sample Input 1

3 3
.#.
..#
#..

Sample Output 1

10

Some of the pairs satisfying the condition are ((1, 2), (3, 3)) and ((3, 1), (3, 2)), where (i, j) denotes the square at the i-th row from the top and the j-th column from the left.

Sample Input 2

2 4
....
....

Sample Output 2

0

Sample Input 3

4 3
###
###
...
###

Sample Output 3

6



Sample input:
3 3
.#.
..#
#..


Sample output:
10

Submission status: Runtime Error

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

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


prevs_all = []
def findNext(i, j, prevs):
  cnt = 0
  i_next = i - 1; j_next = j
  if ([i_next, j_next] not in prevs):
    if (i_next >= 0) and (i_next < h) and (j_next >= 0) and (j_next < w):
      if (s[i][j] != s[i_next][j_next]):
        if (s[i][j]=='#') and ([i_next, j_next] not in prevs_all):
          prevs_all.append([i_next, j_next])
          cnt += 1 + findNext(i_next, j_next,  prevs + [[i, j]])
        else:
          cnt += findNext(i_next, j_next,  prevs + [[i, j]])
  i_next = i; j_next = j+1
  if ([i_next, j_next] not in prevs):
    if (i_next >= 0) and (i_next < h) and (j_next >= 0) and (j_next < w):
      if (s[i][j] != s[i_next][j_next]):
        if (s[i][j]=='#') and ([i_next, j_next] not in prevs_all):
          prevs_all.append([i_next, j_next])
          cnt += 1 + findNext(i_next, j_next,  prevs + [[i, j]])
        else:
          cnt += findNext(i_next, j_next,  prevs + [[i, j]])
  i_next = i; j_next = j-1
  if ([i_next, j_next] not in prevs):
    if (i_next >= 0) and (i_next < h) and (j_next >= 0) and (j_next < w):
      if (s[i][j] != s[i_next][j_next]):
        if (s[i][j]=='#') and ([i_next, j_next] not in prevs_all):
          prevs_all.append([i_next, j_next])
          cnt += 1 + findNext(i_next, j_next,  prevs + [[i, j]])
        else:
          cnt += findNext(i_next, j_next,  prevs + [[i, j]])
  i_next = i + 1; j_next = j
  if ([i_next, j_next] not in prevs):
    if (i_next >= 0) and (i_next < h) and (j_next >= 0) and (j_next < w):
      if (s[i][j] != s[i_next][j_next]):
        if (s[i][j]=='#') and ([i_next, j_next] not in prevs_all):
          prevs_all.append([i_next, j_next])
          cnt += 1 + findNext(i_next, j_next,  prevs + [[i, j]])
        else:
          cnt += findNext(i_next, j_next,  prevs + [[i, j]])
  return cnt

all_cnt = 0

for i in range(h):
  for j in range(w):
    if s[i][j]=="#":
      prevs_all = []
      all_cnt += findNext(i, j, [])

print(all_cnt)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)
H,W=map(int,input().split())
series = [[] for h in range(H)]
for h in range(H):
	series[h] = list(input())

def Go(h,w):
	#print(h,w)
	global c
	check[h][w]=1
	count = 0
	front = ""
	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)+1
			else:
				count += Go(h-1,w)
				c += 1
				used[h-1][w] = 1
	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)+1
			else:
				count += Go(h+1,w)
				c += 1
				used[h+1][w] = 1
	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)+1
			else:
				count += Go(h,w-1)
				c += 1
				used[h][w-1] = 1
	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)+1
			else:
				count += Go(h,w+1)
				c += 1
				used[h][w+1] = 1
	return count

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(5000)
H,W=map(int,input().split())
series = [[] for h in range(H)]
for h in range(H):
	series[h] = list(input())

def Go(h,w):
	#print(h,w)
	global c
	check[h][w]=1
	count = 0
	front = ""
	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)+1
			else:
				count += Go(h-1,w)
				c += 1
				used[h-1][w] = 1
	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)+1
			else:
				count += Go(h+1,w)
				c += 1
				used[h+1][w] = 1
	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)+1
			else:
				count += Go(h,w-1)
				c += 1
				used[h][w-1] = 1
	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)+1
			else:
				count += Go(h,w+1)
				c += 1
				used[h][w+1] = 1
	return count

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

Submission status: Runtime Error

Solution code:
def search(search_map, group, current_h, current_w, group_index, calc):
    calc[0] += 1
    if current_h in search_map:
        search_map[current_h]
    else:
        search_map[current_h] = {}
        search_map[current_h][current_w] = True
    search_map[current_h][current_w] = True
    current = s_map[current_h][current_w]
    num = 0
    if (current == '.'):
        num += 1
    else:
        group[current_h][current_w] = group_index
    # 上
    if current_h != 0:
        next_h = current_h-1
        next_w = current_w
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index, calc)
    # 下
    if current_h < H-1:
        next_h = current_h+1
        next_w = current_w
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index, calc)
    # 左
    if current_w != 0:
        next_h = current_h
        next_w = current_w-1
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index, calc)
    # 右
    if current_w < W-1:
        next_h = current_h
        next_w = current_w+1
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index, calc)
    return num


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

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


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

ans = 0
group_index = 1
group_cnt = {}
calc = [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, calc)
                #group_cnt[group_index] = cnt
                group_index += 1
                ans += cnt
print(ans)

'''
1 1
#
'''

'''
1 1
.
'''

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

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


'''
3 1
#
.
#
'''


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

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

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

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

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

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
MAP = ["_" * (w + 1)] + ['_' + input() + '_' for _ in range(h)] + ["_" * (w + 1)]
ans = set()
m = {0:'#', 1:'.'}
def f(y, x, u, z, fi):
    for ny, nx in ((y - 1, x), (y, x - 1), (y, x + 1), (y + 1, x)):
        if MAP[ny][nx] == m[u] and (ny, nx) not in z:
            if u == 1:
                global ans
                ans.add(fi * 1000 + ny * 1000 + nx)
            f(ny, nx, 1 - u, z | {(ny, nx)}, fi)
for i in range(1, h + 1):
    for j in range(1, w + 1):
        if MAP[i][j] == '#':
            f(i, j, 1, set(), i * 1000 + j)
print(len(ans))

Submission status: Runtime Error

Solution code:
H,W = list(map(int,input().split()))
data = [list(input()) for l in range(H)]
visit = [[0 for i in range(W)] for j in range(H)]
sum = 0
def search(i,j,col):
    global H,W,data,visit,sum
    if (i < 0)or(i >= H)or(j < 0)or(j >= W):
        return
    if (i >= 0)and(i <= H-1)and(j >= 0)and(j <= W-1):
        if (visit[i][j]):return
        if (col == '#') and (data[i][j] == '.'):
            sum += 1
            visit[i][j] = 1
        elif (col == '.') and (data[i][j] == '#'):
            visit[i][j] = 1
        elif (col == ''):
            visit[i][j] = 1
        else:return
    
            
    if data[i][j] == '#':
        search(i-1,j,'#')
        search(i,j-1,'#')
        search(i,j+1,'#')
        search(i+1,j,'#')
    if data[i][j] == '.':
        search(i-1,j,'.')
        search(i,j-1,'.')
        search(i,j+1,'.')
        search(i+1,j,'.')
    

for i in range(H):
    for j in range(W):
        if data[i][j] == '#':
            visit = [[0 for i in range(W)] for j in range(H)]
            search(i,j,'')

print(sum)

Submission status: Runtime Error

Solution code:
h, w = list(map(int, input().split()))
field = []
for i in range(h):
    si = input()
    field.append( [c for c in si] )

def visalizer():
    global field
    print("=========================")
    for i in range(h):
        for j in range(w):
            print(field[i][j], end=' ')
        print('\n')
    print("=========================")

def maeke_last(c):
    if c == "#":
        return "."
    else:
        return "#"

pair_list = []
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
def dfs( last, s_row=0, s_colmun=0, row=0, column=0,):
    global field
    global dict
    if not((0 <= row and row <=h-1) and (0 <=column and column <= w-1)):
        return
    if field[row][column] == '@':
        return

    here = field[row][column]

    if here == last:
        return
    else:
        if not ((s_row, s_colmun) ,(row, column)) in pair_list:
            if here == '.':
                pair_list.append(((s_row, s_colmun) ,(row, column)))


    here_was = field[row][column]
    field[row][column] = '@'
    # visalizer()
    for i in range(len(dx)):
        n_row = row + dx[i]
        n_column = column + dy[i]
        dfs(last = here, s_row = s_row, s_colmun=s_colmun, row=n_row, column=n_column)
    field[row][column] = here_was

# for s_row in range(h):
#     for s_column in range(w):
#         dfs(last = field[s_row][s_column],  s_row=s_row, s_colmun=s_column, row=s_row, column=s_column)

for s_row in range(h):
    for s_column in range(w):
        if field[s_row][s_column] == "#":
            dfs(last = maeke_last(field[s_row][s_column]),  s_row=s_row, s_colmun=s_column, row=s_row, column=s_column)

for ele in pair_list:
    if ele[0]==ele[1] :
        pair_list.remove(ele)
    # pair_list.remove((ele[1], ele[0]))

pair_list2 = []
for ele in pair_list:
    if (not (ele[1], ele[0]) in pair_list2) :
        pair_list2.append(ele)

# for ele in pair_list2:
#     print(ele)
print(len(pair_list2))


# visalizer()

Submission status: Runtime Error

Solution code:
h,w= map(int,input().split())

arr = [input() for i in range(h)]

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

foot_print1=[[0 for i in range(w)] for j in range(h)] #通ったらTrue(戻らないように)
foot_print2=[[0 for i in range(w)] for j in range(h)]
point=[0]
def DFS(st_color,now_pos,foot_print):
    now_color = arr[now_pos[0]][now_pos[1]]
    foot_print[now_pos[0]][now_pos[1]]=1
    # print(now_pos)
    # print(foot_print)

    for i in range(0,4):
        # print(i)
        nextx=now_pos[0]+dx[i]
        nexty=now_pos[1]+dy[i]
        if nextx<0 or nextx>=h or nexty<0 or nexty>=w: continue
        next_color = arr[nextx][nexty]
        # print(next_color)
        if next_color!=now_color and foot_print[nextx][nexty]==0:
            if st_color!=next_color:
                point[0]+=1
                # print(st_color,nextx,nexty,st_color,)

            
            next_pos=[nextx,nexty]
            DFS(st_color,next_pos,foot_print)
    return
##最後1/2


for i in range(0,h):
    for j in range(0,w):
        st_pos=arr[i][j]
        now_pos=[i,j]
        foot_print1=copy.deepcopy(foot_print2)
        DFS(st_pos,now_pos,foot_print1)
        foot_print2[i][j]=1

print(point[0])

Submission status: Runtime Error

Solution code:
def search(search_map, group, current_h, current_w, group_index, calc):
    calc[0] += 1
    if current_h in search_map:
        search_map[current_h]
    else:
        search_map[current_h] = {}
        search_map[current_h][current_w] = True
    search_map[current_h][current_w] = True
    current = s_map[current_h][current_w]
    num = 0
    if (current == '.'):
        num += 1
    else:
        group[current_h][current_w] = group_index
    # 上
    if current_h != 0:
        next_h = current_h-1
        next_w = current_w
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index, calc)
    # 下
    if current_h < H-1:
        next_h = current_h+1
        next_w = current_w
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index, calc)
    # 左
    if current_w != 0:
        next_h = current_h
        next_w = current_w-1
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index, calc)
    # 右
    if current_w < W-1:
        next_h = current_h
        next_w = current_w+1
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index, calc)
    return num


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

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


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

ans = 0
group_index = 1
group_cnt = {}
calc = [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]]
                calc[0] += 1
            else:
                #cnt = search({}, group, i, j, group_index, calc)
                group_cnt[group_index] = cnt
                group_index += 1
                ans += cnt
print(ans)

'''
1 1
#
'''

'''
1 1
.
'''

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

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


'''
3 1
#
.
#
'''


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

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

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

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

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

Submission status: Runtime Error

Solution code:
import numpy as np
h, w = map(int, input().split())
colors = np.zeros((h,w))
for i in range(h):
    s = input()
    for j,c in enumerate(s):
        if c=='#':
            colors[i,j] = 1

def tonari(pos):
    i,j = pos
    ans = []
    if i==0:
        ans.append((i+1,j))
    elif i==h-1:
        ans.append((i-1,j))
    else:
        ans.append((i-1,j))
        ans.append((i+1,j))
    if j==0:
        ans.append((i,j+1))
    elif j==w-1:
        ans.append((i,j-1))
    else:
        ans.append((i,j-1))
        ans.append((i,j+1))
    
    return ans

# 深さ優先探索をする
# マス(0,0)からスタート
# 次の仕切り直しで使うスタート位置のリストnext_start
# すでに訪ねたかどうかを表すh*wの表 visited=1 
# current_positionの前後左右を見てもしcurrent_colorと異なればそっちに動く

current_position = (0,0)
current_color = colors[current_position]
current_group = 0
groups = {0:[1-current_color, current_color]} # {group_num:(white_num,black_num)}
next_visit = []
other_group = []

unvisited = [(i,j) for i in range(h) for j in range(w)]
unvisited.remove((0,0))

while True:
    # current_positionの前後左右を見る
    # print(current_position)
    neighbors = tonari(current_position)
    for ngb in neighbors:
        if colors[ngb] != current_color and ngb in unvisited and ngb not in next_visit:
            next_visit.append(ngb)
        # もしnon_visitedかつcurrent_colorと異なればnext_visitに追加
        # それ以外は何もしない

    # next_visitが空でないとき
    if len(next_visit) > 0:
        current_position = next_visit.pop(0)
        current_color = colors[current_position]
        groups[current_group][0] += 1-current_color
        groups[current_group][1] += current_color
        unvisited.remove(current_position)
        # next_visitの中から次の移動先を取り出して
        # colorをみてgroupに追加
        # current_positionとcurrent_colorを更新

    elif len(next_visit) == 0:
        # next_visitが空のとき
        if len(unvisited) == 0:
            break
        else:
            current_position = unvisited.pop(0)
            current_color = colors[current_position]
            current_group += 1
            groups[current_group] = [1-current_color, current_color]
            # unvisitedの中から一つ選んで
            # current_position, color更新
            # current_group更新

# print(groups)
ans = 0
for g in groups:
    black, white = groups[g]
    ans += black*white
print(int(ans))

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
MAP = ["_" * (w + 1)] + ['_' + input() + '_' for _ in range(h)] + ["_" * (w + 1)]
ans = set()
m = {0:'#', 1:'.'}
def f(y, x, u, z, fi):
    for ny, nx in ((y - 1, x), (y, x - 1), (y, x + 1), (y + 1, x)):
        if MAP[ny][nx] == m[u] and (ny, nx) not in z:
            if u == 1:
                global ans
                ans.add((fi, ny, nx))
            f(ny, nx, 1 - u, z | {(ny, nx)}, fi)
for i in range(1, h + 1):
    for j in range(1, w + 1):
        if MAP[i][j] == '#':
            f(i, j, 1, set(), (i, j))
print(len(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)]
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:
import sys
sys.setrecursionlimit(100000)

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:
def count(i,j):
    global h,w,s1,s2,ans,i1,j1
    a=s1[i][j]
    s1[i][j]=0
    if i-1>=0:
        if s1[i-1][j]!=0 and s1[i-1][j]!=a:
            if s1[i-1][j]=='.':
                ans+=1
                s2[i1][j1]+=1
            else:
                s2[i-1][j]==[i1,j1]
            count(i-1,j)
    if i+1<h:
        if s1[i+1][j]!=0 and s1[i+1][j]!=a:
            if s1[i+1][j]=='.':
                ans+=1
                s2[i1][j1]+=1
            else:
                s2[i+1][j]==[i1,j1]
            count(i+1,j)
    if j-1>=0:
        if s1[i][j-1]!=0 and s1[i][j-1]!=a:
            if s1[i][j-1]=='.':
                ans+=1
                s2[i1][j1]+=1
            else:
                s2[i][j-1]==[i1,j1]
            count(i,j-1)
    if j+1<w:
        if s1[i][j+1]!=0 and s1[i][j+1]!=a:
            if s1[i][j+1]=='.':
                ans+=1
                s2[i1][j1]+=1
            else:
                s2[i][j+1]==[i1,j1]
            count(i,j+1)

import copy
h,w=map(int,input().split())
s=[]
for i in range(h):
    s.append(list(input()))
ans=0
s2=copy.deepcopy(s)
for i in range(h):
    for j in range(w):
        if s[i][j]=='#':
            if s2[i][j]=='#':
                s2[i][j]=0
                s1=copy.deepcopy(s)
                i1=i
                j1=j
                count(i,j)
            else:
                ans+=s2[s2[i][j][0]][s2[i][j][1]]
print(int(ans))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

# -*- coding: utf-8 -*-

h, w = map(int, input().split())
s = [list(input()) for i in range(h)]

dp = [[True] * w for i in range(h)]

def check_path(st, go, c):
    check = False
    if s[st[0]][st[1]]!=c:
        return False

    if st==go:
        return True

    if not dp[st[0]][st[1]]:
        return False

    d=''
    if c=='.':
        d='#'
    elif c=='#':
        d='.'

    if st[0]>0:
        s[st[0]][st[1]] = '?'
        check = check | check_path((st[0]-1, st[1]), (go[0], go[1]), d)
        s[st[0]][st[1]] = c
    if st[1]>0:
        s[st[0]][st[1]] = '?'
        check = check | check_path((st[0], st[1]-1), (go[0], go[1]), d)
        s[st[0]][st[1]] = c        
    if st[0]<h-1:
        s[st[0]][st[1]] = '?'
        check = check | check_path((st[0]+1, st[1]), (go[0], go[1]), d)
        s[st[0]][st[1]] = c
    if st[1]<w-1:
        s[st[0]][st[1]] = '?'
        check = check | check_path((st[0], st[1]+1), (go[0], go[1]), d)
        s[st[0]][st[1]] = c
    
    dp[st[0]][st[1]] = check
    
    return check

kuro = []
siro = []

for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            kuro += [(i, j)]
        else:
            siro += [(i, j)]

ans=0

for goal in siro:
    dp = [[True] * w for i in range(h)]
    for start in kuro:
        if check_path(start, goal, '#'):
            ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
def search(search_map, group, current_h, current_w, group_index, calc):
    calc[0] += 1
    if current_h in search_map:
        search_map[current_h]
    else:
        search_map[current_h] = {}
        search_map[current_h][current_w] = True
    search_map[current_h][current_w] = True
    current = s_map[current_h][current_w]
    num = 0
    if (current == '.'):
        num += 1
    else:
        group[current_h][current_w] = group_index
    # 上
    if current_h != 0:
        next_h = current_h-1
        next_w = current_w
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index, calc)
    # 下
    if current_h < H-1:
        next_h = current_h+1
        next_w = current_w
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index, calc)
    # 左
    if current_w != 0:
        next_h = current_h
        next_w = current_w-1
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index, calc)
    # 右
    if current_w < W-1:
        next_h = current_h
        next_w = current_w+1
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index, calc)
    return num


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

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


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

ans = 0
group_index = 1
group_cnt = {}
calc = [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]]
                calc[0] += 1
            else:
                cnt = search({}, group, i, j, group_index, calc)
                group_cnt[group_index] = cnt
                group_index += 1
                ans += cnt
print(ans)

'''
1 1
#
'''


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

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

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

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

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

Submission status: Runtime Error

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

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


def findNext(i, j, prevs, prevs_all):
  cnt = 0
  i_next = i - 1; j_next = j
  if ([i_next, j_next] not in prevs):
    if (i_next >= 0) and (i_next < h) and (j_next >= 0) and (j_next < w):
      if (s[i][j] != s[i_next][j_next]):
        if (s[i][j]=='#') and ([i_next, j_next] not in prevs_all):
          prevs_all.append([i_next, j_next])
          cnt += 1 + findNext(i_next, j_next,  prevs + [[i, j]], prevs_all)
        else:
          cnt += findNext(i_next, j_next,  prevs + [[i, j]], prevs_all)
  i_next = i; j_next = j+1
  if ([i_next, j_next] not in prevs):
    if (i_next >= 0) and (i_next < h) and (j_next >= 0) and (j_next < w):
      if (s[i][j] != s[i_next][j_next]):
        if (s[i][j]=='#') and ([i_next, j_next] not in prevs_all):
          prevs_all.append([i_next, j_next])
          cnt += 1 + findNext(i_next, j_next,  prevs + [[i, j]], prevs_all)
        else:
          cnt += findNext(i_next, j_next,  prevs + [[i, j]], prevs_all)
  i_next = i; j_next = j-1
  if ([i_next, j_next] not in prevs):
    if (i_next >= 0) and (i_next < h) and (j_next >= 0) and (j_next < w):
      if (s[i][j] != s[i_next][j_next]):
        if (s[i][j]=='#') and ([i_next, j_next] not in prevs_all):
          prevs_all.append([i_next, j_next])
          cnt += 1 + findNext(i_next, j_next,  prevs + [[i, j]], prevs_all)
        else:
          cnt += findNext(i_next, j_next,  prevs + [[i, j]], prevs_all)
  i_next = i + 1; j_next = j
  if ([i_next, j_next] not in prevs):
    if (i_next >= 0) and (i_next < h) and (j_next >= 0) and (j_next < w):
      if (s[i][j] != s[i_next][j_next]):
        if (s[i][j]=='#') and ([i_next, j_next] not in prevs_all):
          prevs_all.append([i_next, j_next])
          cnt += 1 + findNext(i_next, j_next,  prevs + [[i, j]], prevs_all)
        else:
          cnt += findNext(i_next, j_next,  prevs + [[i, j]], prevs_all)
  return cnt

all_cnt = 0

for i in range(h):
  for j in range(w):
    if s[i][j]=="#":
      all_cnt += findNext(i, j, [], [])

print(all_cnt)

Submission status: Runtime Error

Solution code:
program main
  character(400) :: Sc
  integer,allocatable,dimension(:, :) :: S, C, D
  integer(16) :: H, W, i, j, su1, su0, n
  read*, H, W
  allocate(S(W, H), C(W, H), D(W, H))
  do i = 1, H
    read*, Sc
    do j = 1, W
      if (Sc(j:j) == "#") then
        S(j, i) = 1
      else
        S(j, i) = 0
      endif
    enddo
  enddo

  i = 1
  j = 1
  D = 0
  n = 0
  do while(.true.)
    C = 0
    call search_zero(D, i, j)
    call search(S, i, j, C)
    su1 = sum(C * S)
    su0 = sum(C) - su1



    n = n + su1 * su0
    


    D = D + C
    if (minval(D) > 0) then
      print*, n
      return
    endif
  end do


contains

  subroutine search_zero(S, i, j)
    integer,dimension(:, :),intent(inout) :: S
    integer :: i, j
    integer :: a, b
    do a = 1, size(S, 1)
      do b = 1, size(S, 2)
        if (S(a, b) == 0) then
          i = a
          j = b
          return
        endif
      enddo
    enddo
  end subroutine

  recursive subroutine search(S, i, j, C)
    integer,dimension(:, :),intent(inout) :: S, C
    integer,intent(in) :: i, j
    integer :: di, dj
    C(i, j) = 1
    do di = -1, 1, 2
      if (i + di >= 1 .and. i + di <= W) then
        if(C(i + di, j) == 0) then
          if (S(i + di, j) /= S(i, j)) then
            call search(S, i + di, j, C)
          endif
        endif
      endif
    enddo
    do dj = -1, 1, 2
      if (j + dj >= 1 .and. j + dj <= H) then
        if(C(i, j + dj) == 0) then
          if (S(i, j + dj) /= S(i, j)) then
            call search(S, i, j + dj, C)
          endif
        endif
      endif
    enddo
  end subroutine

  subroutine print_matrix(A)
    integer,intent(in) :: A(:,:)
    integer :: s(2), i
    s = shape(A)
    do i = 1, s(1)
      print *, A(i, :)
    enddo
  end subroutine

end program