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:
class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n)]
    self.size = [1]*n
    self.rank = [0]*n
    
  def find(self, x):
    if self.par[x]==x:
      return x
    else:
      self.par[x] = self.find(self.par[x])
      return self.par[x]
  def unit(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    elif self.rank[x]<self.rank[y]:
      self.par[x] = y
      self.size[y] += self.size[x]
      return
    elif self.rank[y]<self.rank[x]:
      self.par[y] = x
      self.size[x] += self.size[y]
    else:
      self.par[y] = x
      self.size[x] += self.size[y]
      self.rank[x] += 1
      
  def same(self, x, y):
    return self.find(x)==self.find(y)
  
  def count(self, x):
    return self.size[x]
H, W, *L = open('0').read().split()
H = int(H)
W = int(W)
ans = 0
u = UnionFind(H*W)
inf = [[0]*2 for i in range(W*H)]
log = [[0]*W for i in range(H)]
for i in range(H):
  for j in range(W):
    if i==H-1:
      if j==W-1:
        continue
      else:
        if L[i][j]!=L[i][j+1]:
          if log[i][j] and log[i][j+1]:
            continue
          u.unit(i*W+j,i*W+j+1)
          p = u.find(i*W+j)
          if log[i][j]==0:
            if L[i][j]=='.':
              inf[p][0] += 1
            else:
              inf[p][1] += 1
            log[i][j] = 1
          if log[i][j+1]==0:
            if L[i][j+1]=='.':
              inf[p][0] += 1
            else:
              inf[p][1] += 1
            log[i][j+1] = 1
    else:
      if j==W-1:
        if L[i][j]!=L[i+1][j]:
          if log[i][j] and log[i+1][j]:
            continue
          u.unit(i*W+j,(i+1)*W+j)
          p = u.find((i+1)*W+j)
          if log[i][j]==0:
            if L[i][j]=='.':
              inf[p][0] += 1
            else:
              inf[p][1] += 1
            log[i][j] = 1
          if log[i+1][j]==0:
            if L[i+1][j]=='.':
              inf[p][0] += 1
            else:
              inf[p][1] += 1
            log[i+1][j] = 1
      else:
        if L[i][j]!=L[i+1][j]:
          if log[i][j] and log[i+1][j]:
            continue
          u.unit(i*W+j,(i+1)*W+j)
          p = u.find((i+1)*W+j)
          if log[i][j]==0:
            if L[i][j]=='.':
              inf[p][0] += 1
            else:
              inf[p][1] += 1
            log[i][j] = 1
          if log[i+1][j]==0:
            if L[i+1][j]=='.':
              inf[p][0] += 1
            else:
              inf[p][1] += 1
            log[i+1][j] = 1
        if L[i][j]!=L[i][j+1]:
          if log[i][j] and log[i][j+1]:
            continue
          u.unit(i*W+j,i*W+j+1)
          p = u.find(i*W+j)
          if log[i][j]==0:
            if L[i][j]=='.':
              inf[p][0] += 1
            else:
              inf[p][1] += 1
            log[i][j] = 1
          if log[i][j+1]==0:
            if L[i][j+1]=='.':
              inf[p][0] += 1
            else:
              inf[p][1] += 1
            log[i][j+1] = 1
for i in range(H*W):
  a,b = inf[i]
  ans += a*b
print(ans)

Submission status: Runtime Error

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

H, W = map(int, input().split())
S = [input() for _ in range(H)]
check = [[0]*W for _ in range(H)]
di = [-1, 0, 1, 0]
dj = [ 0,-1, 0, 1]

black, white = 0, 0

def dfs(i, j):
    global check, black, white
    if check[i][j]:
        return
    else:
        check[i][j] = 1
    if S[i][j] == '#':
        black += 1
    else:
        white += 1
    for dir in range(4):
        ni = i + di[dir]
        nj = j + dj[dir]
        if ni < 0 or ni >= H or nj < 0 or nj >= W: continue
        if S[i][j] == S[ni][nj]: continue
        dfs(ni, nj)

ans = 0
for i in range(H):
    for j in range(W):
        black, white = 0, 0
        dfs(i, j)
        ans += black * white

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
H,W=map(int,input().split())
S=[input() for i in range(H)]
checked=[[0 for i in range(W)] for m in range(H)]

count=0
count2=0
visited=set()
for h1 in range(H):
    for w1 in range(W):
        if S[h1][w1]=="#" and checked[h1][w1]==0:
            checked[h1][w1]=1
            stack=deque([[h1,w1,"#"]])
            kuro=1
            siro=0
            count2+=1
            visited.add(h*400+w)
            while stack:
                h,w,iro=stack.popleft()
                for y,x in [[-1,0],[1,0],[0,1],[0,-1]]:
                    Y,X=y+h,x+w
                    visitednum=Y*400+X
                    if 0<=Y<H and 0<=X<W and not visitednum in visited:
                        if iro=="#" and S[Y][X]==".":
                            siro+=1
                            visited.add(visitednum)
                            stack.append([Y,X,"."])
                        elif iro=="." and S[Y][X]=="#" and not visitednum in visited:
                            kuro+=1
                            checked[Y][X]=1
                            visited.add(visitednum)
                            stack.append([Y,X,"#"])
            count+=kuro*siro
print(count)

Submission status: Runtime Error

Solution code:
from collections import deque
H,W=map(int,input().split())
S=[input() for i in range(H)]
checked=[[0 for i in range(W)] for m in range(H)]

count=0
count2=0
visited=set([h1*400+w1])
for h1 in range(H):
    for w1 in range(W):
        if S[h1][w1]=="#" and checked[h1][w1]==0:
            checked[h1][w1]=1
            stack=deque([[h1,w1,"#"]])
            kuro=1
            siro=0
            count2+=1

            while stack:
                h,w,iro=stack.popleft()
                for y,x in [[-1,0],[1,0],[0,1],[0,-1]]:
                    Y,X=y+h,x+w
                    visitednum=Y*400+X
                    if 0<=Y<H and 0<=X<W and not visitednum in visited:
                        if iro=="#" and S[Y][X]==".":
                            siro+=1
                            visited.add(visitednum)
                            stack.append([Y,X,"."])
                        elif iro=="." and S[Y][X]=="#" and not visitednum in visited:
                            kuro+=1
                            checked[Y][X]=1
                            visited.add(visitednum)
                            stack.append([Y,X,"#"])
            count+=kuro*siro
print(count)

Submission status: Runtime Error

Solution code:
from collections import deque
H,W=map(int,input().split())
S=[input() for i in range(H)]
checked=[[0 for i in range(W)] for m in range(H)]

count=0
count2=0
for h1 in range(H):
    for w1 in range(W):
        if S[h1][w1]=="#" and checked[h1][w1]==0:
            checked[h1][w1]=1
            stack=deque([[h1,w1,"#"]])
            kuro=1
            siro=0
            count2+=1
            visited=set([h1*400+w1])
            print(stack)
            while stack:
                h,w,iro=stack.popleft()
                for y,x in [[-1,0],[1,0],[0,1],[0,-1]]:
                    Y,X=y+h,x+w
                    visitednum=Y*400+X
                    if 0<=Y<H and 0<=X<W and not visitednum in visited:
                        if iro=="#" and S[Y][X]==".":
                            siro+=1
                            visited.add(visitednum)
                            stack.append([Y,X,"."])
                        elif iro=="." and S[Y][X]=="#" and not visitednum in visited:
                            kuro+=1
                            visited[Y][X]=1
                            checked[Y][X]=1
                            visited.add(visitednum)
                            stack.append([Y,X,"#"])
            count+=kuro*siro
print(count)
print(count2)

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

h,w = map(int,input().split())

sl = []

for _ in range(h):
    s = list(input())
    sl.append(s)

uf = UnionFind(h*w)
for i in range(h):
    for j in range(w):
        if sl[i][j] != sl[i][j + 1]:
            if j+1 < w:
                uf.union(i*w+j, i*w+j+1)
        if sl[i][j] != sl[i + 1][j]:
            if i+1 < h:
                uf.union(i * w + j, i * w + j + w)

ans = 0
for group in uf.all_group_members().values():
    a = 0
    b = 0
    for p in group:
        i = p // w
        j = p % w
        if sl[i][j] == "#":
            a += 1
        else:
            b += 1
    ans += a*b

print(ans)

Submission status: Runtime Error

Solution code:
def dfs(i, j):
    visited[i][j] = True
    res_b = 0
    res_w = 0
    if N[i][j]:
        res_b += 1
    else:
        res_w += 1
    for di, dj in d:
        if i + di < 0 or i + di >= H or j + dj < 0 or j + dj >= W:
            continue
        if N[i][j] == N[i+di][j+dj]:
            continue
        if visited[i+di][j+dj]:
            continue
        tmp_b, tmp_w = dfs(i + di, j + dj)
        res_b += tmp_b
        res_w += tmp_w
    return res_b, res_w

H, W = map(int, input().split())
N = [[False] * W for _ in range(H)]
for i in range(H):
    s = input()
    for j in range(W):
        N[i][j] = (s[j] == "#")

d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
visited = [[False] * W for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if not N[i][j]:
            continue
        if visited[i][j]:
            continue
        b, w = dfs(i, j)
        ans += (b * w)

print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**8)
h, w = [int(i) for i in sys.stdin.readline().split()]
s_ls = []
bl_ls = []
for i in range(h):
    s = [1 if i == "#" else -1 for i in sys.stdin.readline().strip()]
    for j, k in enumerate(s):
        if k == 1:
            bl_ls.append((i, j))
    s_ls.append(s)

def dfs(y, x, col):
    res = 0
    if col == -1:
        res += 1
    already.add((y, x))
    for move_y, move_x in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        next_y = y + move_y
        next_x = x + move_x
        if 0 <= next_x < w and 0 <= next_y < h and s_ls[next_y][next_x] == (-1) * col and (next_y, next_x) not in already:
            res += dfs(next_y, next_x, (-1) * col)
    return res

ans = 0
for bl in bl_ls:
    already = set()
    ans += dfs(*bl, 1)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
h, w = [int(i) for i in sys.stdin.readline().split()]
s_ls = []
bl_ls = []
for i in range(h):
    s = [1 if i == "#" else -1 for i in sys.stdin.readline().strip()]
    for j, k in enumerate(s):
        if k == 1:
            bl_ls.append((i, j))
    s_ls.append(s)

def dfs(y, x, col):
    res = 0
    if col == -1:
        res += 1
    already.add((y, x))
    for move_y, move_x in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        next_y = y + move_y
        next_x = x + move_x
        if 0 <= next_x < w and 0 <= next_y < h and s_ls[next_y][next_x] == (-1) * col and (next_y, next_x) not in already:
            res += dfs(next_y, next_x, (-1) * col)
    return res

ans = 0
for bl in bl_ls:
    already = set()
    ans += dfs(*bl, 1)
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

h, w = map(int ,input().split())
s = [list(input()) for _ in range(h)]
check = [[0] * w for _ in range(h)]
move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
ans = 0

for i in range(h):
    for j in range(w):
        if check[i][j] == 1:
            continue
        black, white = 0, 0 

        stack = [[i, j]]
        check[i][j] = 1
        if s[i][j] == '#':
            black += 1
        else:
            white += 1

        while len(stack) > 0:
            x, y = stack.pop()
            tmp = s[x][y]
            for dx, dy in move:
                nx, ny = x + dx, y + dy
                if 0 <= nx < h and 0 <= ny < w and tmp != s[nx][ny] and check[nx][ny] == 0:
                    stack.append([nx, ny])
                    check[nx][ny] = 1
                    if s[nx][ny] == '#':
                        black += 1
                    else:
                        white += 1

        ans += black * white

print(ans)

# %%

Submission status: Runtime Error

Solution code:
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.root=[-1]*(n+1)
        self.rnk=[0]*(n+1)

    def Find_Root(self,x):
        if self.root[x]<0:
            return x
        else:
            self.root[x]=self.Find_Root(self.root[x])
            return self.root[x]

    def Unite(self,x,y):
        x=self.Find_Root(x)
        y=self.Find_Root(y)
        if x==y:
            return
        elif self.rnk[x]>self.rnk[y]:
            self.root[x]+=self.root[y]
            self.root[y]=x
        else:
            self.root[y]+=self.root[x]
            self.root[x]=y
            if self.rnk[x]==self.rnk[y]:
                self.rnk[y]+=1

    def isSameGroup(self,x,y):
        return self.Find_Root(x)==self.Find_Root(y)

    def Count(self,x):
        return -self.root[self.Find_Root(x)]

h,w=map(int,input().split())
g=[list(input()) for _ in range(h)]
uf=UnionFind(h*w)
for i in range(h):
    for j in range(w-1):
        if g[i][j]!=g[i][j+1]:
            uf.Unite(i*3+j,i*3+j+1)

for j in range(w):
    for i in range(h-1):
        if g[i][j]!=g[i+1][j]:
            uf.Unite(i*3+j,(i+1)*3+j)

x=[]
for i in range(h*w):
    x.append(uf.Find_Root(i))

d=[[0,0] for _ in range(h*w)]
for i in range(h):
    for j in range(w):
        now=i*w+j
        nr=x[now]
        if g[i][j]=="#":
            d[nr][0]+=1
        else:
            d[nr][1]+=1
ans=0
for i in range(h*w):
    ans+=d[i][0]*d[i][1]
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(100000)
d=defaultdict(int)
dw=defaultdict(int)
n,m=map(int,input().split())
l=[]
for i in range(n):
  l.append(list(input()))
lb=[[0 for i in range(m)]for j in range(n)]
move=[[1,0],[-1,0],[0,1],[0,-1]]
def dfs(n1,n2,w,n3):
  if lb[n1][n2]!=0:
    return None
  else:
    lb[n1][n2]=n3
    if w==".":
      w1="#"
    else:
      w1="."
    for j in move:
      dx=j[0]
      dy=j[1]
      x=dx+n1
      y=dy+n2
      if 0>x or x>n-1 or y<0 or y>m-1:
        pass
      else:
        if w1!=l[x][y]:
          pass
        else:
          dfs(x,y,w1,n3)
    return None
dfs(0,0,l[0][0],1)
num=1
for i in range(n):
  for j in range(m):
    dfs(i,j,l[i][j],num)
    num+=1
for i in range(n):
  for j in range(m):
    d[lb[i][j]]+=1
    if l[i][j]=="#":
      dw[lb[i][j]]+=1
ans=0
for i in d:
  ans+=dw[i]*(d[i]-dw[i])
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
d=defaultdict(int)
dw=defaultdict(int)
n,m=map(int,input().split())
l=[]
for i in range(n):
  l.append(list(input()))
lb=[[0 for i in range(m)]for j in range(n)]
move=[[1,0],[-1,0],[0,1],[0,-1]]
def dfs(n1,n2,w,n3):
  if lb[n1][n2]!=0:
    return None
  else:
    lb[n1][n2]=n3
    if w==".":
      w1="#"
    else:
      w1="."
    for j in move:
      dx=j[0]
      dy=j[1]
      x=dx+n1
      y=dy+n2
      if 0>x or x>n-1 or y<0 or y>n-1:
        pass
      else:
        if w1!=l[x][y]:
          pass
        else:
          dfs(x,y,w1,n3)
    return None
dfs(0,0,l[0][0],1)
num=1
for i in range(n):
  for j in range(m):
    dfs(i,j,l[i][j],num)
    num+=1
for i in range(n):
  for j in range(m):
    d[lb[i][j]]+=1
    if l[i][j]=="#":
      dw[lb[i][j]]+=1
ans=0
for i in d:
  ans+=dw[i]*(d[i]-dw[i])
print(ans)

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
g=[list(input()) for _ in range(h)]

class UnionFind():
    def __init__(self,n):
        self.n=n
        self.root=[-1]*(n+1)
        self.rnk=[0]*(n+1)

    def Find_Root(self,x):
        if self.root[x]<0:
            return x
        else:
            self.root[x]=self.Find_Root(self.root[x])
            return self.root[x]

    def Unite(self,x,y):
        x=self.Find_Root(x)
        y=self.Find_Root(y)
        if x==y:
            return
        elif self.rnk[x]>self.rnk[y]:
            self.root[x]+=self.root[y]
            self.root[y]=x
        else:
            self.root[y]+=self.root[x]
            self.root[x]=y
            if self.rnk[x]==self.rnk[y]:
                self.rnk[y]+=1

    def isSameGroup(self,x,y):
        return self.Find_Root(x)==self.Find_Root(y)

    def Count(self,x):
        return -self.root[self.Find_Root(x)]

uf=UnionFind(h*w)

for i in range(h):
    for j in range(w):
        if j<w-1 and g[i][j]!=g[i][j+1]:
            uf.Unite(i*w+j,i*w+j+1)
        if i<h-1 and g[i][j]!=g[i+1][j]:
            uf.Unite(i*w+j,(i+1)*w+j)

kuro={}
siro={}

for i in range(h):
    for j in range(w):
        k=i*w+j
        if g[i][j]=="#":
            if uf.Find_Root(k) in kuro.keys():
                kuro[uf.Find_Root(k)]+=1
            else:
                kuro[uf.Find_Root(k)]=1
        else:
            if uf.Find_Root(k) in siro.keys():
                siro[uf.Find_Root(k)]+=1
            else:
                siro[uf.Find_Root(k)]=1

ans=0
for k in siro.keys():
    ans+=kuro[k]*siro[k]
print(ans)

Submission status: Runtime Error

Solution code:
H,W=map(int,input().split())
S=[[int(c=='#') for c in input()] for i in range(H)]
v=[[0]*W for i in range(H)]
r=0
def bfs(p,x,y,c,b):
    global r
    c^=1
    q=set()
    for h,w in p:
        v[h][w]=1
        if h>0 and not v[h-1][w] and S[h-1][w]==c:
            q.add((h-1,w))
        if w>0 and not v[h][w-1] and S[h][w-1]==c:
            q.add((h,w-1))
        if h<H-1 and not v[h+1][w] and S[h+1][w]==c:
            q.add((h+1,w))
        if w<W-1 and not v[h][w+1] and S[h][w+1]==c:
            q.add((h,w+1))
    if not q:
        r+=x*y
    else:
        if b:
            x+=len(q)
        else:
            y+=len(q)
        bfs(q,x,y,c,b^1)
for h in range(H):
    for w in range(W):
        if v[h][w]==0:
            bfs([(h,w)],1,0,S[h][w],0)
print(r)

Submission status: Runtime Error

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

seen = [[False for _ in range(W)] for _ in range(H)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
numb = 0
numw = 0

def dfs(y,x):
  global numb
  global numw
  seen[y][x] = True
  if S[y][x] == '#':
    numb += 1
  if S[y][x] == '.':
    numw += 1
  for i in range(4):
    if not(0<=y+dy[i]<H) or not(0<=x+dx[i]<W):
      continue
    if seen[y+dy[i]][x+dx[i]]:
      continue
    if S[y][x] == S[y+dy[i]][x+dx[i]]:
      continue
    dfs(y+dy[i],x+dx[i])

ans = 0
for i in range(H):
  for j in range(W):
    numb = 0
    numw = 0
    if S[i][j] == '#':
      dfs(i,j)
      ans += numb * numw
print(ans)

Submission status: Runtime Error

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

def unite(node_a, node_b):
    root_a, depth_a = node_a.root()
    root_b, depth_b = node_b.root()
    if root_a == root_b:# すでに連結成分
        return
    elif depth_a >= depth_b:# aの方が深い
        root_b.is_root = False
        root_b.parent = root_a
        root_a.white += root_b.white
        root_a.black += root_b.black
    else:# bの方が深い
        root_a.is_root = False
        root_a.parent = root_b
        root_b.white += root_a.white
        root_b.black += root_a.black

class Node:
    def __init__(self, color):# color: 0:white, 1:black
        self.parent = None
        self.is_root = True
        self.white = 1 if color == 0 else 0
        self.black = 1 if color == 1 else 0
    
    def root(self):
        node = self
        depth = 0
        while not node.is_root:
            node = node.parent
            depth += 1
        return node, depth

def main():
    H, W = map(int, input().split())
    s = [input().strip() for i in range(H)]
    
    nodes = [[Node(0 if s[j][i] == "." else 1) for i in range(W)] for j in range(H)]

    for y in range(H):
        for x in range(W):
            now = s[y][x]
            for nx, ny in [(x, y-1), (x+1, y), (x, y+1), (x-1, y)]:
                if 0 <= nx and nx < W and 0 <= ny and ny < H:
                    if s[ny][nx] != now:
                        unite(nodes[y][x], nodes[ny][nx])
    
    ans = 0
    # count_roots = 0
    for y in range(H):
        for x in range(W):
            if nodes[y][x].is_root:
                count_roots += 1
                node = nodes[y][x]
                ans += node.white * node.black
    print(ans)
    # print(count_roots)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
input = sys.stdin.readline
def main():
    h, w = map(int, input().split())
    s = [list(input()) for i in range(h)]

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

    ans = 0
    for bx, by in black:
        for wx, wy in white:

            queue = [[bx, by]]
            visited = [[False for i in range(w + 1)] for j in range(h+1)]
            while len(queue) != 0:
                p = queue.pop(0)
                visited[p[0]][p[1]] = True
                if p[0] == wx and p[1] == wy:
                    ans += 1
                    break
                for x, y in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                    nx = p[0] + x
                    ny = p[1] + y
                    if nx < 0 or ny < 0 or nx >= h or ny >= w or visited[nx][ny] == True:
                        continue
                    #print(nx, ny, s)
                    if (((nx+ny) % 2) == ((bx+by) % 2) and s[nx][ny] == ".") or (((nx+ny) % 2) != ((bx+by) % 2) and s[nx][ny] == "#"):
                        continue
                    queue.append([nx, ny])

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split());b=[[0]*(w+1)]
for i in range(h):
  b.append([0])
  for j in input():
    if j==".":b[-1].append(1)
    else:b[-1].append(2)
  b[-1].append(0)
b.append([0]*(w+1));d=[[0,1],[0,-1],[1,0],[-1,0]];a=0
def s(i,j):
  global B;B[b[i][j]-1]+=1;v=b[i][j];b[i][j]=0
  for k in d:
    if v^3!=b[i+k[0]][j+k[1]]:continue
    s(i+k[0],j+k[1])
for i in range(1,h+1):
  for j in range(1,w+1):B=[0,0];s(i,j);a+=B[0]*B[1]
print(a)

Submission status: Runtime Error

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

ans = set()


def f(i, j):
    seen[i][j] = 1
    if S[i][j] == '.':
        ans.add((s, (i, j)))
    if i != 0:
        if seen[i-1][j] == 0 and S[i-1][j] != S[i][j]:
            f(i-1, j)
    if i != H-1:
        if seen[i+1][j] == 0 and S[i+1][j] != S[i][j]:
            f(i+1, j)
    if j != 0:
        if seen[i][j-1] == 0 and S[i][j-1] != S[i][j]:
            f(i, j-1)
    if j != W-1:
        if seen[i][j+1] == 0 and S[i][j+1] != S[i][j]:
            f(i, j+1)


for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            seen = [[0] * W for i in range(H)]
            s = (i, j)
            f(i, j)

print(len(ans))

Submission status: Runtime Error

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

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

color = []
for i in range(H):
    color.append([-1] * W)

def DFS(node, c_color):
    x = node[0]
    y = node[1]
    nb = [[x, y-1], [x, y+1], [x+1, y], [x-1, y]]
    deq = deque()
    for i in range(4):
        if(nb[i][0] >= 0 and nb[i][0] < H and nb[i][1] >= 0 and nb[i][1] < W):
            if(color[nb[i][0]][nb[i][1]] == -1):
                deq.append(nb[i])

    deq_ = deque()
    while(deq):
        next_node = deq.popleft()
        if(mas[next_node[0]][next_node[1]] != mas[node[0]][node[1]]):
            color[next_node[0]][next_node[1]] = c_color
            deq_.append(next_node)
            
    while(deq_):
        next_node = deq_.popleft()
        DFS(next_node, c_color)
    return
        
current_color = 0
for i in range(H):
    for j in range(W):
        if(color[i][j] >= 0):
            continue
        else:
            color[i][j] = current_color
            DFS([i, j], current_color)
            current_color += 1

color_num = []
for i in range(current_color):
    color_num.append([0, 0])


for i in range(H):
    for j in range(W):
        if(mas[i][j] == '#'):
            color_num[color[i][j]][0] += 1
        else:
            color_num[color[i][j]][1] += 1

ans = 0
for i in range(len(color_num)):
    ans += color_num[i][0] * color_num[i][1]

print(ans)

Submission status: Runtime Error

Solution code:
from collections import *

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

color = []
for i in range(H):
    color.append([-1] * W)

def DFS(node, c_color):
    x = node[0]
    y = node[1]
    nb = [[x, y-1], [x, y+1], [x+1, y], [x-1, y]]
    deq = deque()
    for i in range(4):
        if(nb[i][0] >= 0 and nb[i][0] < H and nb[i][1] >= 0 and nb[i][1] < W):
            if(color[nb[i][0]][nb[i][1]] == -1):
                deq.append(nb[i])

    deq_ = deque()
    while(deq):
        next_node = deq.popleft()
        if(mas[next_node[0]][next_node[1]] != mas[node[0]][node[1]]):
            color[next_node[0]][next_node[1]] = c_color
            deq_.append(next_node)
            
    while(deq_):
        next_node = deq_.popleft()
        DFS(next_node, c_color)
    return
        
current_color = 0
for i in range(H):
    for j in range(W):
        if(color[i][j] >= 0):
            continue
        else:
            color[i][j] = current_color
            DFS([i, j], current_color)
            current_color += 1

color_num = []
for i in range(current_color):
    color_num.append([0, 0])


for i in range(H):
    for j in range(W):
        if(mas[i][j] == '#'):
            color_num[color[i][j]][0] += 1
        else:
            color_num[color[i][j]][1] += 1

ans = 0
for i in range(len(color_num)):
    ans += color_num[i][0] * color_num[i][1]

print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(5000)

def search_w(i, j, direct, origin_i, origin_j):
  if i<0 or j<0 or i >= row or j >= col:
    return
  if data[i][j] == ".":
    n = i*400+j
    if n in pat:
      return
    pat.append(n)
    if direct != "n":
      search_b(i - 1, j, "s", origin_i, origin_j)
    if direct != "s":
      search_b(i + 1, j, "n", origin_i, origin_j)
    if direct != "w":
      search_b(i, j - 1, "e", origin_i, origin_j)
    if direct != "e":
      search_b(i, j + 1, "w", origin_i, origin_j)


def search_b(i, j, direct, origin_i, origin_j):
  if i == origin_i and j == origin_j:
    return
  if i<0 or j<0 or i>=row or j>=col:
    return
  if data[i][j] == "#":
    if direct != "n":
      search_w(i - 1, j, "s", origin_i, origin_j)
    if direct != "s":
      search_w(i + 1, j, "n", origin_i, origin_j)
    if direct != "w":
      search_w(i, j - 1, "e", origin_i, origin_j)
    if direct != "e":
      search_w(i, j + 1, "w", origin_i, origin_j)

row, col = map(int, input().split())
data = [0]*row
for n in range(row):
  data[n] = input()

pat = []
cnt = 0
for r in range(len(data)):
  for c in range(len(data[0])):
    if data[r][c] == "#":
      search_w(r - 1, c, "s", r, c)
      search_w(r + 1, c, "n", r, c)
      search_w(r, c - 1, "e", r, c)
      search_w(r, c + 1, "w", r, c)
      cnt += len(pat)
      pat = []

print(cnt)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(3000)

def search_w(i, j, direct, origin_i, origin_j):
  if i<0 or j<0 or i >= row or j >= col:
    return
  if data[i][j] == ".":
    n = i*400+j
    if n in pat:
      return
    pat.append(n)
    if direct != "n":
      search_b(i - 1, j, "s", origin_i, origin_j)
    if direct != "s":
      search_b(i + 1, j, "n", origin_i, origin_j)
    if direct != "w":
      search_b(i, j - 1, "e", origin_i, origin_j)
    if direct != "e":
      search_b(i, j + 1, "w", origin_i, origin_j)


def search_b(i, j, direct, origin_i, origin_j):
  if i == origin_i and j == origin_j:
    return
  if i<0 or j<0 or i>=row or j>=col:
    return
  if data[i][j] == "#":
    if direct != "n":
      search_w(i - 1, j, "s", origin_i, origin_j)
    if direct != "s":
      search_w(i + 1, j, "n", origin_i, origin_j)
    if direct != "w":
      search_w(i, j - 1, "e", origin_i, origin_j)
    if direct != "e":
      search_w(i, j + 1, "w", origin_i, origin_j)

row, col = map(int, input().split())
data = [0]*row
for n in range(row):
  data[n] = input()

pat = []
cnt = 0
for r in range(len(data)):
  for c in range(len(data[0])):
    if data[r][c] == "#":
      search_w(r - 1, c, "s", r, c)
      search_w(r + 1, c, "n", r, c)
      search_w(r, c - 1, "e", r, c)
      search_w(r, c + 1, "w", r, c)
      cnt += len(pat)
      pat = []

print(cnt)