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:
def B():
    N = int(input())
    A, B = map(int, input().split())
    P = list(map(int, input().split()))
    f = []
    s = []
    t = []
    for i in P:
        if i <= A:
            f.append(i)
        elif i <= B:
            s.append(i)
        else:
            t.append(i)
    print(min(len(f), len(s), len(t)))
#B()

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:
h, w = [int(i) for i in input().split()]
s = [input() for i in range(h)]
cnt = 0
e = [[0 for i in range(w)] for j in range(h)]
def ahaha(i, j):
    global cnt
    global e
    e[i][j] = 1
    if i+1 < h and e[i+1][j] == 0:
        if s[i+1][j] != s[i][j]:
            if s[i+1][j] == ".":
                cnt += 1
            ahaha(i+1,j)
    if i-1 >= 0 and e[i-1][j] == 0:
        if s[i-1][j] != s[i][j]:
            if s[i-1][j] == ".":
                cnt += 1
            ahaha(i-1,j)
    if j+1 < w and e[i][j+1] == 0:
        if s[i][j+1] != s[i][j]:
            if s[i][j+1] == ".":
                cnt += 1
            ahaha(i,j+1)
    if j-1 >= 0 and e[i][j-1] == 0:
        if s[i][j-1] != s[i][j]:
            if s[i][j-1] == ".":
                cnt += 1
            ahaha(i,j-1)

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

Submission status: Runtime Error

Solution code:
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])

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

cnt = 0
bk = 0
wh = 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:
def getN():
    return int(input())

def getMN():
    a = input().split()
    b = [int(i) for i in a]
    return b[0],b[1]

def getlist():
    a = input().split()
    b = [int(i) for i in a]
    return b


h,w = getMN()
pos = ["."]*(w*h+1)
cur = 1

class unionfind():
    def __init__(self,n):
        self.par = [i for i in range(n+1)]
        self.rank = [0]*(n+1)
        self.childnum = [1] * (n + 1)
        self.childb = [0 if pos[i] == "." else 1 for i in range(n+1)]

    def find(self,x):
        if self.par[x] == x:
            return x
        else:
            #print(x, ":", self.par[x])
            self.par[x] = self.find(self.par[x])
            return self.find(self.par[x])

    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.childnum[y] += self.childnum[x]
            self.childb[y] += self.childb[x]

        else:
            self.par[y] = x
            self.childnum[x] += self.childnum[y]
            self.childb[x] += self.childb[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same_check(self,x,y):
        return self.find(x) == self.find(y)


for i in range(h):
    posin = input()
    for j in range(w):
        if posin[j] == "#":
            pos[j+(i)*w] = "#"

uf = unionfind(h*w+1)

unionlog = []

for i in range(h):
    for j in range(w):
        nn = j+(i)*w
        now = pos[nn]

        if j != w-1:
            nr = j + (i) * w + 1
            right = pos[nr]
            if right != now:
                if not uf.same_check(nn,nr):
                    uf.union(nn,nr)
                    unionlog.append("union:{},{}".format(nn,nr))
        if i != h-1:
            nd = j + (i + 1) * w
            down = pos[nd]
            if down != now:
                if not uf.same_check(nn,nd):
                    uf.union(nn,nd)
                    unionlog.append("union:{},{}".format(nn,nd))


a = 0
#print("\n".join(unionlog))

#print("s",uf.childnum)
#print(uf.childb)
#print([uf.find(i) for i in range(9)])
ans = 0

for parnum in list(set([uf.find(i) for i in range(h*w)])):
    #print(parnum)
    b = uf.childb[parnum]
    w = uf.childnum[parnum] - b
    #print(b,w)
    ans +=  b*w

print(ans)

Submission status: Runtime Error

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

color = [[0 for i in range(W)] for j in range(H)]
  
def path(h, w, col):
  global color
  if color[h][w] == 0:
    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=1
for i in range(H):
  for j in range(W):
    if color[i][j] == 0:
      path(i, j, col)
      col+=1


dic = {i:[0,0] for i in range(1,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(1,col):
  ans += dic[i][0] * dic[i][1]
  
print(ans)

Submission status: Runtime Error

Solution code:
def getN():
    return int(input())

def getMN():
    a = input().split()
    b = [int(i) for i in a]
    return b[0],b[1]

def getlist():
    a = input().split()
    b = [int(i) for i in a]
    return b


h,w = getMN()
pos = ["."]*(w*h+1)
posgroup = [[0]*w for i in range(h)]
already =  [[0]*w for i in range(h)]
cur = 1

class unionfind():
    def __init__(self,n):
        self.par = [i for i in range(n+1)]
        self.rank = [0]*(n+1)
        self.childnum = [1] * (n + 1)
        self.childb = [0 if pos[i] == "." else 1 for i in range(n+1)]

    def find(self,x):
        if self.par[x] == x:
            return x
        else:
            #print(x, ":", self.par[x])
            self.par[x] = self.find(self.par[x])
            return self.find(self.par[x])

    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.childnum[y] += self.childnum[x]
            self.childb[y] += self.childb[x]

        else:
            self.par[y] = x
            self.childnum[x] += self.childnum[y]
            self.childb[x] += self.childb[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same_check(self,x,y):
        return self.find(x) == self.find(y)


for i in range(h):
    posin = input()
    for j in range(w):
        if posin[j] == "#":
            pos[j+(i)*w] = "#"

uf = unionfind(h*w)

unionlog = []

for i in range(h):
    for j in range(w):
        nn = j+(i)*w
        now = pos[nn]

        if j != w-1:
            nr = j + (i) * w + 1
            right = pos[nr]
            if right != now:
                if not uf.same_check(nn,nr):
                    uf.union(nn,nr)
                    unionlog.append("union:{},{}".format(nn,nr))
        if i != h-1:
            nd = j + (i + 1) * w
            down = pos[nd]
            if down != now:
                if not uf.same_check(nn,nd):
                    uf.union(nn,nd)
                    unionlog.append("union:{},{}".format(nn,nd))


a = 0
#print("\n".join(unionlog))

#print("s",uf.childnum)
#print(uf.childb)
#print([uf.find(i) for i in range(9)])
ans = 0

for parnum in list(set([uf.find(i) for i in range(9)])):
    #print(parnum)
    b = uf.childb[parnum]
    w = uf.childnum[parnum] - b
    #print(b,w)
    ans +=  b*w

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):
	global c
	check[h][w]=1
	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)+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)]
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
			check = [[0 for w in range(W)] for h in range(H)]
print(ans)

Submission status: Runtime Error

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

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


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

foot_print=[[False for i in range(w)] for j in range(h)] #通ったらTrue(戻らないように)
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]]=True
    # 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]==False:
            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_print=[[False for i in range(w)] for j in range(h)]
        DFS(st_pos,now_pos,foot_print)

print(point[0]//2)

Submission status: Runtime Error

Solution code:
import numpy as np
H,W = list(map(int,input().split()))
Sarr = np.zeros([H,W])
for i in range(H):
    Sarr[i,:] = [1 if x=="#" else 0 for x in input()]
Marr = np.zeros([H,W])

black_l = np.zeros(H*W)
white_l = np.zeros(H*W)
new = 0
for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            Marr[i,j] = new
        elif i == 0:
            if Sarr[i,j-1] == Sarr[i,j]:
                new += 1
                Marr[i,j] = new
            else:
                Marr[i,j] = Marr[i,j-1]
        elif j==0:
            if Sarr[i-1,j] == Sarr[i,j]:
                new += 1
                Marr[i,j] = new
            else:
                Marr[i,j] = Marr[i-1,j]
        else:
            if Sarr[i-1,j] == Sarr[i,j]:
                if Sarr[i,j-1] == Sarr[i,j]:
                    new += 1
                    Marr[i,j] = new
                else:
                    Marr[i,j] = Marr[i,j-1]
            else:
                Marr[i,j] = Marr[i-1,j]
    if i > 0:
        if Sarr[i-1,0] == Sarr[i,0] and Sarr[i,0] != Sarr[i,1]:
            Marr[i,0] = Marr[i,1]
for i in range(H):
    for j in range(W):
        if Sarr[i,j] == 1:
            black_l[int(Marr[i,j])] += 1
        else:
            white_l[int(Marr[i,j])] += 1

# print(Sarr)
# print(Marr)
# print(black_l)
# print(white_l)

print(int(black_l.dot(white_l)))

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 st == '.':
        st = '#'
        s[x][y] = 1
    else:
        st = '.'
        s[x][y] = -1

    if x != 0 and S[x - 1][y] == st and s[x - 1][y] == 0:
        search(x - 1, y, st)
    if y != 0 and S[x][y - 1] == st and s[x][y - 1] == 0:
        search(x, y - 1, st)
    if x != H - 1 and S[x + 1][y] == st and s[x + 1][y] == 0:
        search(x + 1, y, st)
    if y != W - 1 and S[x][y + 1] == st and s[x][y + 1] == 0:
        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 = []
for i in range(H):
    S.append(input())

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


ans = 0
dp = [[False] * W for a in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j] == "#" and not dp[i][j]:
            black = 1
            white = 0
            dp[i][j] = True
            search(i, j, "#")
            ans += black * white

print(ans)

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, org):
  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 (org==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, org)
        else:
          cnt += findNext(i_next, j_next,  prevs + [[i, j]], prevs_all, org)
  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 (org==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, org)
        else:
          cnt += findNext(i_next, j_next,  prevs + [[i, j]], prevs_all, org)
  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 (org==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, org)
        else:
          cnt += findNext(i_next, j_next,  prevs + [[i, j]], prevs_all, org)
  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 (org==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, org)
        else:
          cnt += findNext(i_next, j_next,  prevs + [[i, j]], prevs_all, org)
  return cnt

all_cnt = 0

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

print(all_cnt)

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
visited_array = np.zeros((h,w))
visited_array[(0,0)] = 1
groups = {0:[1-current_color, current_color]} # {group_num:(white_num,black_num)}
next_visit = []
other_group = []


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

    # next_visitが空でないとき
    if len(next_visit) > 0:
        pos = next_visit.pop(0)
        current_position = pos        
        current_color = colors[current_position]
        groups[current_group][0] += 1-current_color
        groups[current_group][1] += current_color
        visited_array[current_position] = 1
        # next_visitの中から次の移動先を取り出して
        # colorをみてgroupに追加
        # current_positionとcurrent_colorを更新
    elif len(next_visit) == 0:
        # next_visitが空のとき
        row, col = np.where(visited_array==0)
        if len(row) == 0:
            break
        else:
            current_position = (row[0], col[0])
            current_color = colors[current_position]
            current_group += 1
            groups[current_group] = [1-current_color, current_color]
            visited_array[current_position] = 1
            # 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:
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
S = [list(map(lambda x: True if x == "#" else False, input())) for _ in range(H)]

move_x = (1, 0, -1, 0)
move_y = (0, 1, 0, -1)

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


def f(h, w, color, first):
    if (h < 0 or h >= H or w < 0 or w >= W):
        return
    if (grid[h][w]):
        return
    grid[h][w] = True

    if (first or (not color) == S[h][w]):
        if (not S[h][w]):
            ans_pos.append((h, w))
        for i in range(4):
            f(h + move_y[i], w + move_x[i], S[h][w], False)
    grid[h][w] = False

ans = 0
for i in range(H):
    for j in range(W):
        if (S[i][j]):
            f(i, j, True, True)
            ans += len(set(ans_pos))
            ans_pos = []
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:
            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])
        # if copy == 0:
        #     arr[x][y] = copy
        target = 1 - target
        return
    return

for each_cp in blacks:
    length = 0
    cp_arr = []
    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:
h, w = map(int, input().split())
s = [list(input()) 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

    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[x][y] = temp
    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 start in kuro:
    for goal in siro:
        if check_path(start, goal, '#'):
            ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

H,W = [int(i) for i in input().split()]
S = np.empty([H,W])
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == '#':
            S[i,j] = 0
        else:
            S[i,j] = 1

class sagasu():
    def __init__(self,H,W,S):
        self.H = H
        self.W = W
        self.S = S
        self.num = 0

    def __call__(self):
        for i in range(self.H):
            for j in range(self.W):
                self.rireki = []
                if self.S[i,j] == 0:
                    self.bunki(i,j,0)
        return(self.num)

    def bunki(self,y,x,atai):
        self.ue(y-1,x,atai)
        self.sita(y+1,x,atai)
        self.hidari(y,x-1,atai)
        self.migi(y,x+1,atai)

    def ue(self,y,x,atai):
        if y >= 0:
            if self.S[y,x] == 1 - atai:
                if '{}-{}'.format(y,x) not in self.rireki:
                    self.rireki.append('{}-{}'.format(y,x))
                    if 1 - atai == 1:
                        self.num += 1
                    self.bunki(y,x,1-atai)

    def sita(self,y,x,atai):
        if y <= self.H-1:
            if self.S[y,x] == 1 - atai:
                if '{}-{}'.format(y,x) not in self.rireki:
                    self.rireki.append('{}-{}'.format(y,x))
                    if 1 - atai == 1:
                        self.num += 1
                    self.bunki(y,x,1-atai)

    def hidari(self,y,x,atai):
        if x >= 0:
            if self.S[y,x] == 1 - atai:
                if '{}-{}'.format(y,x) not in self.rireki:
                    self.rireki.append('{}-{}'.format(y,x))
                    if 1 - atai == 1:
                        self.num += 1
                    self.bunki(y,x,1-atai)

    def migi(self,y,x,atai):
        if x <= self.W-1:
            if self.S[y,x] == 1 - atai:
                if '{}-{}'.format(y,x) not in self.rireki:
                    self.rireki.append('{}-{}'.format(y,x))
                    if 1 - atai == 1:
                        self.num += 1
                    self.bunki(y,x,1-atai)

map = sagasu(H,W,S)
num = map()

print(num)

Submission status: Runtime Error

Solution code:
def search(search_map, group, current_h, current_w, group_index, calc):
    calc[0] += 1
    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
        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, calc)
    # 下
    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, calc)
    # 左
    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, calc)
    # 右
    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, 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] = {}
    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 = {}
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(searched_map, group, i, j, group_index, calc)
                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)

'''
1 1
#
'''


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

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

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

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

Submission status: Runtime Error

Solution code:
import numpy as np

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, org):
  #print(i, j, prevs, org)
  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 (org==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, org)
        else:
          cnt += findNext(i_next, j_next,  prevs + [[i, j]], prevs_all, org)
  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 (org==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, org)
        else:
          cnt += findNext(i_next, j_next,  prevs + [[i, j]], prevs_all, org)
  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 (org==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, org)
        else:
          cnt += findNext(i_next, j_next,  prevs + [[i, j]], prevs_all, org)
  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 (org==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, org)
        else:
          cnt += findNext(i_next, j_next,  prevs + [[i, j]], prevs_all, org)
  return cnt

all_cnt = 0

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

print(all_cnt)