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:
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()
    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:


def search_w(i, j, direct, origin_i, origin_j):
  if i<0 or j<0 or i>=len(data) or j>=len(data[0]):
    return
  if data[i][j] == ".":
    if (i,j,origin_i,origin_j) in pat:
      return
    pat.append((i, j, origin_i, origin_j))
    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>=len(data) or j>=len(data[0]):
    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 = []
for n in range(row):
  data.append(input())

pat = []
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)

print(len(set(pat)))

Submission status: Runtime Error

Solution code:


def search_w(i, j, direct, origin_i, origin_j):
  if i<0 or j<0 or i>=len(data) or j>=len(data[0]):
    return
  global pat
  if data[i][j] == ".":
    pat.append((i, j, origin_i, origin_j))
    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>=len(data) or j>=len(data[0]):
    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 = []
for n in range(row):
  data.append(input())

pat = []
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)

print(len(set(pat)))

Submission status: Runtime Error

Solution code:
from sys import stdin
dx = (1, 0, -1, 0)
dy = (0, 1, 0, -1)
H, W = [int(_) for _ in stdin.readline().rstrip().split()]
field = [list(stdin.readline().rstrip()) for _ in range(H)]
seen = [[False for i in range(400)] for j in range(400)]
num_b, num_w = 0, 0
ans = 0

def dfs(h, w):
    seen[h][w] = True
    if field[h][w] == '#':
        global num_b
        num_b += 1
    else:
        global num_w
        num_w += 1

    for direction in range(4):
        nh = h + dx[direction]
        nw = w + dy[direction]

        if nh < 0 or nh >= H or nw < 0 or nw >= W:
            continue
        if field[nh][nw] == field[h][w]:
            continue
        if seen[nh][nw]:
            continue

        dfs(nh, nw)

for i in range(H):
    for j in range(W):
        if field[i][j] == '.':
            continue
        if seen[i][j]:
            continue
        num_b, num_w = 0, 0
        dfs(i, j)
        ans += num_b * num_w 

print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin
dx = (1, 0, -1, 0)
dy = (0, 1, 0, -1)
H, W = [int(_) for _ in stdin.readline().rstrip().split()]
field = [list(stdin.readline().rstrip()) for _ in range(H)]
seen = [[False for i in range(400)] for j in range(400)]
num_b, num_w = 0, 0
ans = 0

def dfs(h, w):
    print('h: %d, w: %d' % (h, w))
    seen[h][w] = True
    if field[h][w] == '#':
        global num_b
        num_b += 1
    else:
        global num_w
        num_w += 1
    print('b: %d, w: %d' % (num_b, num_w))

    for direction in range(4):
        nh = h + dx[direction]
        nw = w + dy[direction]

        if nh < 0 or nh >= H or nw < 0 or nw >= W:
            continue
        if field[nh][nw] == field[h][w]:
            continue
        if seen[nh][nw]:
            continue

        dfs(nh, nw)

for i in range(H):
    for j in range(W):
        print('i: %d, j: %d' % (i, j))
        if field[i][j] == '.':
            continue
        if seen[i][j]:
            continue
        num_b, num_w = 0, 0
        dfs(i, j)
        ans += num_b * num_w 

print(ans)

Submission status: Runtime Error

Solution code:
h, w = [int(item) for item in input().split()]
field = []
for i in range(h):
    field.append(input().rstrip())

black = 0; white = 0
visited = [[0] * w for _ in range(h)]

def dfs(is_black, i, j):
    global black
    global white
    visited[i][j] = 1
    for x, y in [[1,0], [0,1], [0,-1], [-1,0]]:
        if i+x < 0 or i+x >= h or j+y < 0 or j+y >= w:
            continue
        if visited[i + x][j + y] != 0:
            continue
        if is_black:
            if field[i+x][j+y] == ".":
                white += 1
                dfs(False, i+x, j+y)
        if not is_black:
            if field[i+x][j+y] == "#":
                black += 1
                dfs(True, i+x, j+y)

ans = 0
for i in range(h):
    for j in range(w):
        if visited[i][j] != 0:
            continue
        if field[i][j] == "#":
            white = 0; black = 1
            dfs(True, i, j)
        else:
            white = 1; black = 0
            dfs(False, i, j)
        ans += white * black

print(ans)

Submission status: Runtime Error

Solution code:
class UF():
  def __init__(self, N):
    self._parent=[n for n in range(0, N)]
    self._size=[1] * N

  def find_root(self, x):
    if self._parent[x]==x:return x
    self._parent[x]=self.find_root(self._parent[x])
    return self._parent[x]

  def unite(self, x, y):
    gx=self.find_root(x)
    gy=self.find_root(y)
    if gx==gy:return

    if self._size[gx]<self._size[gy]:
      self._parent[gx]=gy
      self._size[gy]+=self._size[gx]
    else:
      self._parent[gy]=gx
      self._size[gx]+=self._size[gy]

  def size(self, x):
    return self._size[self.find_root(x)]

  def samegroup(self, x, y):
    return self.find_root(x)==self.find_root(y)

  def groupnum(self):
    N=len(self._parent)
    ans=0
    for i in range(N):
      if self.find_root(i)==i:
        ans+=1
    return ans

from collections import defaultdict
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
UF=UF(h*w)
for i in range(h):
  for j in range(w):
    if i!=0:
      if s[i][j]!=s[i-1][j]:UF.unite(i*h+j,(i-1)*h+j)
    if i!=h-1:
      if s[i][j]!=s[i+1][j]:UF.unite(i*h+j,(i+1)*h+j)
    if j!=0:
      if s[i][j]!=s[i][j-1]:UF.unite(i*h+j,i*h+(j-1))
    if j!=w-1:
      if s[i][j]!=s[i][j+1]:UF.unite(i*h+j,i*h+(j+1))
listB=[0 for i in range(h*w)]
listW=[0 for i in range(h*w)]
for i in range(h):
  for j in range(w):
    if s[i][j]=='#':
      listB[UF.find_root(i*h+j)]+=1
    else:
      listW[UF.find_root(i*h+j)]+=1
ct=0
for i in range(h*w):
  ct+=listB[i]*listW[i]
print(ct)

Submission status: Runtime Error

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


isVisited = [ [False]*W for _ in range(H) ]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
# (i, j) から行けるペアの数
def dfs( x, y ):
    isVisited[x][y] = True
    numBlack, numWhite = 0, 0
    if S[x][y] == '#': numBlack = 1
    else:              numWhite = 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx and nx < H and 0 <= ny and ny < W and not isVisited[nx][ny]:
            if S[x][y] != S[nx][ny]:
                tmpB, tmpW = dfs( nx, ny )
                numBlack += tmpB
                numWhite += tmpW
    return numBlack, numWhite

ans = 0
for i in range(H):
    for j in range(W):
        if not isVisited[i][j]: 
            numBlack, numWhite = dfs( i, j )
            ans += numBlack * numWhite

print( ans )

Submission status: Runtime Error

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

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
# (i, j) から行けるペアの数
def dfs( x, y, isVisited ):
    ans = 0
    isVisited[x][y] = True
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if S[x][y] == '#':
            if 0 <= nx and nx < H and 0 <= ny and ny < W and not isVisited[nx][ny]:
                if S[nx][ny] == '.': ans += dfs( nx, ny, isVisited )+1
        else:
            if 0 <= nx and nx < H and 0 <= ny and ny < W and not isVisited[nx][ny]:
                if S[nx][ny] == '#': ans += dfs( nx, ny, isVisited )
    return ans


ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
          isVisited = [ [False]*W for _ in range(H) ]
          ans += dfs( i, j, isVisited )

print( ans )

Submission status: Runtime Error

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

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
# (i, j) から行けるペアの数
def dfs( x, y, isVisited ):
    ans = 0
    isVisited[x][y] = True
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if S[x][y] == '#':
            if 0 <= nx and nx < H and 0 <= ny and ny < W and not isVisited[nx][ny]:
                if S[nx][ny] == '.': ans += dfs( nx, ny, isVisited )+1
        else:
            if 0 <= nx and nx < H and 0 <= ny and ny < W and not isVisited[nx][ny]:
                if S[nx][ny] == '#': ans += dfs( nx, ny, isVisited )
    return ans


ans = 0
for i in range(H):
    for j in range(W):
        isVisited = [ [False]*W for _ in range(H) ]
        if S[i][j] == '#': ans += dfs( i, j, isVisited )

print( ans )

Submission status: Runtime Error

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


# (i, j) から行けるペアの数
def dfs( i, j, isVisited ):
    ans = 0
    isVisited[i][j] = True
    if S[i][j] == '#':
        if i+1 < H and isVisited[i+1][j] == False:
            if S[i+1][j] == '.': ans += dfs( i+1, j, isVisited )+1
        if j+1 < W and isVisited[i][j+1] == False:
            if S[i][j+1] == '.': ans += dfs( i, j+1, isVisited )+1
        if i-1 >= 0 and isVisited[i-1][j] == False:
            if S[i-1][j] == '.': ans += dfs( i-1, j, isVisited )+1 
        if j-1 >= 0 and isVisited[i][j-1] == False:
            if S[i][j-1] == '.': ans += dfs( i, j-1, isVisited )+1
    else:
        if i+1 < H and isVisited[i+1][j] == False:
            if S[i+1][j] == '#': ans += dfs( i+1, j, isVisited )
        if j+1 < W and isVisited[i][j+1] == False:
            if S[i][j+1] == '#': ans += dfs( i, j+1, isVisited )
        if i-1 >= 0 and isVisited[i-1][j] == False:
            if S[i-1][j] == '#': ans += dfs( i-1, j, isVisited ) 
        if j-1 >= 0 and isVisited[i][j-1] == False:
            if S[i][j-1] == '#': ans += dfs( i, j-1, isVisited )
    return ans


ans = 0
for i in range(H):
    for j in range(W):
        isVisited = [ [False]*W for _ in range(H) ]
        if S[i][j] == '#': ans += dfs( i, j, isVisited )

print( ans )

Submission status: Runtime Error

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

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

class UnionFind():
    def __init__(self, N):
        self.par = [i for i in range(N)]
        self.size = [1] * N
        self.N = N

    # xのrootを返す
    def root(self, x):
        if self.par[x] == x:
            return x
        else: 
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    # x, yが同じrootの場合true
    def same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry

    # x,yのrootが違った場合、併合
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if self.size[rx] < self.size[ry]:
            self.par[rx] = ry
            self.size[ry] += self.size[rx]
        else:
            self.par[ry] = rx
            self.size[rx] += self.size[ry]
            
uf = UnionFind(h*w)

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

for v in range(h*w):
    uf.root(v)

wc = [0]*(h*w)
bc = [0]*(h*w)
for j in range(h):
    for i in range(w):
        idx = w*j+i
        if a[j][i] == ".":
            wc[idx] += 1
        else:
            bc[idx] += 1

res = 0
for i in range(len(l_idx)):
    res += wc[i] * bc[i]
print(res)

Submission status: Runtime Error

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

arr = [[-1 for i in range(w)] for j in range(h)]
cnt = 0

def draw(j, i, cnt):
    arr[j][i] = cnt
    if i != w-1 and arr[j][i+1]==-1 and a[j][i+1] != a[j][i]:
        draw(j,i+1,cnt)
    if j != h-1 and arr[j+1][i]==-1 and a[j+1][i] != a[j][i]:
        draw(j+1,i,cnt)
    if i != 0 and arr[j][i-1]==-1 and a[j][i-1] != a[j][i]:
        draw(j,i-1,cnt)
    if j != 0 and arr[j-1][i]==-1 and a[j-1][i] != a[j][i]:
        draw(j-1,i,cnt)

for j in range(h):
    for i in range(w):
        if arr[j][i] == -1:
            draw(j,i,cnt)
            cnt += 1
wc = [0]*(cnt)
bc = [0]*(cnt)

for j in range(h):
    for i in range(w):
        if a[j][i] == ".":
            wc[arr[j][i]] += 1
        else:
            bc[arr[j][i]] += 1

res = 0
for i in range(cnt):
    res += wc[i] * bc[i]
print(res)

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n = II()
    h = II()
    w = II()
    print((n-h+1)*(n-w+1))
    return

#B
def B():
    n = II()
    a, b = LI()
    p = LI()
    p.sort()
    ans = [0 for i in range(3)]
    for p_ in p:
        if p_ <= a:
            ans[0] += 1
        elif a < p_ <= b:
            ans[1] += 1
        else:
            ans[2] += 1
    print(min(ans))
    return

#C
def C():
    h, w = LI()
    s = SR(h)
    def bfs(x, y):
        xy_ = [(0, -1), (1, 0), (0, 1), (-1, 0)]
        count1 = 1
        count2 = 0
        q = deque([])
        q.append((x,y))
        while q:
            x,y = q.popleft()
            for xy in xy_:
                x_, y_ = x + xy[0], y + xy[1]
                if 0 <= x_ < w and 0 <= y_ < h:
                    if s[y_][x_] != s[y][x] and field[y_][x_]:
                        field[y_][x_] = False
                        if s[y_][x_] == "#":
                            count1 += 1
                        else:
                            count2 += 1
                        q.append((y_, x_))
        return count1*count2
                        
    field = [[True for i in range(w)] for k in range(h)]
    ans = 0
    for y in range(h):
        for x in range(w):
            if s[y][x] == "#" and field[y][x]:
                field[y][x] = False
                ans += bfs(x, y)
    
    print(ans)
    
        
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    C()

Submission status: Runtime Error

Solution code:
from collections import deque
around = [(0,1),(1,0),(0,-1),(-1,0)]

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

checked = [[0]*W for i in range(H)]

def dfs(si,sj):
    if grid[si][sj] == ".":
        b = 0; w = 1
    if grid[si][sj] == "#":
        b = 1; w = 0
    dq = deque()
    dq.append((si,sj))
    checked[si][sj] = 1
    while dq:
        i,j = dq.pop()
        for di,dj in around:
            ni = i + di; nj = j + dj
            if not(0 <= ni <= H-1 and 0 <= nj <= W-1):
                continue
            if checked[ni][nj]:
                continue
            p = grid[i][j]
            np = grid[ni][nj]
            if (p,np) == (".","#"):
                b += 1
                dq.append((ni,nj))
                checked[ni][nj] = 1
            if (p,np) == ("#","."):
                w += 1
                dq.append((ni,nj))
                checked[ni][nj] = 1
    return b*w

ans = 0
for i in range(H):
    for j in range(W):
        if not checked[i][j] and grid[i][j] == ".":
            ans += bfs(i,j)
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Mar  6 16:29:39 2019

@author: Yamazaki Kenichi
"""

H,W = map(int,input().split())
A = [input() for i in range(H)]
T = [[-1,0,0] for j in range(H*W)] 

def g(x,i,j):
    if x == '.':
        return 1 if (i+j)%2 == 0 else 2
    else:
        return 4 if (i+j)%2 == 0 else 3
def p(u):
    return T[u][0]
def findset(u):
    if p(u) == -1:
        return u
    else:
        T[u][0] = findset(p(u))
        return T[u][0]

def unite(u,v):
    if findset(u) == findset(v):
        return
#    if T[findset(u)[0]][findset(u)[1]][1]+T[findset(u)[0]][findset(u)[1]][0
#         ] >= T[findset(v)[0]][findset(v)[1]][0]+T[findset(v)[0]][findset(v)[1]][1]:
    T[findset(u)][1] += T[findset(v)][1]
    T[findset(u)][2] += T[findset(v)][2]
    T[findset(v)][0] = findset(u)
def unite_check(i1,j1,i2,j2):
    if g(A[i1][j1],i1,j1)%2 == 0 and g(A[i2][j2],i2,j2)%2 == 0:
        unite(i1 * H + j1, i2 * H + j2)
    elif g(A[i1][j1],i1,j1)%2 == 1 and g(A[i2][j2],i2,j2)%2 == 1:
        unite(i1 * H + j1, i2 * H + j2)

for i in range(H):
    for j in range(W):
        if g(A[i][j],i,j) <= 2:
            T[i * H + j][1] += 1
        else:
            T[i * H + j][2] += 1
        if i !=0:
            unite_check(i,j,i-1,j)
        if j !=0:
            unite_check(i,j,i,j-1)
ans = 0
for i in range(H):
    for j in range(W):
        if T[i * H + j][0] == -1:
            ans += T[i * H + j][1] * T[i * H + j][2]
print(ans)

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
s=[input() for _ in range(h)]
dy=[0,0,1,-1]
dx=[1,-1,0,0]
import sys
sys.setrecursionlimit(10000)
def dfs(y,x):
    global check
    global was
    was[y][x]=1
    if s[y][x]=="#":
        check[0]+=1
    else:
        check[1]+=1
    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if nx >= 0 and ny >= 0 and nx < w and ny < h and s[ny][nx] != s[y][x] and not was[ny][nx]:
            dfs(ny,nx) 
ans=0
was=[[0 for _ in range(w)] for _ in range(h)]
for i in range(w):
    for j in range(h):
        if not was[j][i]:
            check=[0,0]
            dfs(j,i)
            ans+=check[0]*check[1]
print(ans)

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
s=[input() for _ in range(h)]
dy=[0,0,1,-1]
dx=[1,-1,0,0]
def dfs(y,x):
    global check
    global was
    was[y][x]=1
    if s[y][x]=="#":
        check[0]+=1
    else:
        check[1]+=1
    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if nx >= 0 and ny >= 0 and nx < w and ny < h and s[ny][nx] != s[y][x] and not was[ny][nx]:
            dfs(ny,nx) 
ans=0
was=[[0 for _ in range(w)] for _ in range(h)]
for i in range(w):
    for j in range(h):
        if not was[j][i]:
            check=[0,0]
            dfs(j,i)
            ans+=check[0]*check[1]
print(ans)

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
s=[input() for _ in range(n)]
dy=[0,0,1,-1]
dx=[1,-1,0,0]
def dfs(y,x):
    global check
    global was
    was[y][x]=1
    if s[y][x]=="#":
        check[0]+=1
    else:
        check[1]+=1
    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if nx >= 0 and ny >= 0 and nx < w and ny < h and s[ny][nx] != s[y][x] and not was[ny][nx]:
            dfs(ny,nx) 
ans=0
was=[[0 for _ in range(w)] for _ in range(h)]
for i in range(w):
    for j in range(h):
        if not was[j][i]:
            check=[0,0]
            dfs(j,i)
            ans+=check[0]*check[1]
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
global h, w
h, w = map(int, input().split())
s = [list(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]
black_count = 0
white_count = 0


def dfs(x: int, y: int):
    global black_count, white_count

    if s[x][y] == '#':
        black_count += 1
    else:
        white_count += 1

    seen[x][y] = True

    for k in range(4):
        next_x = x + dx[k]
        next_y = y + dy[k]

        if 0 <= next_x < h and 0 <= next_y < w:
            if s[x][y] != s[next_x][next_y] and not seen[next_x][next_y]:
                dfs(next_x, next_y)


def main():
    global black_count, white_count
    ans = 0

    # See:
    # http://drken1215.hatenablog.com/entry/2019/01/13/035500
    for i in range(h):
        for j in range(w):
            if s[i][j] == '#' and not seen[i][j]:
                black_count = 0
                white_count = 0
                dfs(i, j)
                ans += black_count * white_count

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
h, w = map(int, input().split())
s = [list(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]
black_count = 0
white_count = 0


def dfs(x: int, y: int):
    global black_count, white_count

    if s[x][y] == '#':
        black_count += 1
    else:
        white_count += 1

    seen[x][y] = True

    for k in range(4):
        next_x = x + dx[k]
        next_y = y + dy[k]

        if 0 <= next_x < h and 0 <= next_y < w:
            if s[x][y] != s[next_x][next_y] and not seen[next_x][next_y]:
                dfs(next_x, next_y)


def main():
    global black_count, white_count
    ans = 0

    # See:
    # http://drken1215.hatenablog.com/entry/2019/01/13/035500
    for i in range(h):
        for j in range(w):
            if s[i][j] == '#' and not seen[i][j]:
                black_count = 0
                white_count = 0
                dfs(i, j)
                ans += black_count * white_count

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def search_obj(x,y,grids):
    ans = [0,0]
    curr_state = grids[y][x]
    grids[y][x] = '0'    
    obj_state = '.'
    if(curr_state == '.'):
        ans[0] += 1
        obj_state = '#'
    elif(curr_state == '#'):
        ans[1] += 1
    
    if(grids[y-1][x] == obj_state):
        a,b = search_obj(x,y-1,grids)
        ans[0] += a
        ans[1] += b

    if(grids[y][x-1] == obj_state):
        a,b = search_obj(x-1,y,grids)
        ans[0] += a
        ans[1] += b

    if(grids[y+1][x] == obj_state):
        a,b = search_obj(x,y+1,grids)
        ans[0] += a
        ans[1] += b

    if(grids[y][x+1] == obj_state):
        a,b = search_obj(x+1,y,grids)
        ans[0] += a
        ans[1] += b

    return ans
    

H,W = (int(x) for x in input().split())
s = ""
ans = 0
for _ in range(W+2):
    s+="0"
s = list(s)
grids = [s]

for _ in range(H):
    si = input()
    si = "0"+si+"0"
    grids.append(list(si))
    
grids.append(s)

for i in range(W):
    for j in range(H):
        a,b = search_obj(i+1,j+1,grids)
        ans += a*b

print(ans)

Submission status: Runtime Error

Solution code:
import collections
import numpy as np
import sys


def search(i, j, S, Q):
    nxt = collections.deque([[i, j]])
    black = 0
    white = 0
    if (S[i][j] == "#"): black += 1
    if (S[i][j] == "."): white += 1

    while nxt:
        i, j = nxt.popleft()
        Q[i][j] = True

        if (j + 1 < S.shape[1]):
            if (S[i][j] != S[i][j + 1] and Q[i][j + 1] == False):
                Q[i][j + 1] = True
                nxt.append([i, j + 1])
                if (S[i][j + 1] == "#"):
                    black += 1
                else:
                    white += 1
        if (i + 1 < S.shape[0]):
            if (S[i][j] != S[i + 1][j] and Q[i + 1][j] == False):
                Q[i + 1][j] = True
                nxt.append([i + 1, j])
                if (S[i + 1][j] == "#"):
                    black += 1
                else:
                    white += 1
        if (j - 1 >= 0 and S[i][j] != S[i][j - 1] and Q[i][j - 1] == False):
            Q[i][j - 1] = True
            nxt.append([i, j - 1])
            if (S[i][j + 1] == "#"):
                black += 1
            else:
                white += 1
        if (i - 1 >= 0 and S[i][j] != S[i - 1][j] and Q[i - 1][j] == False):
            Q[i - 1][j] = True
            nxt.append([i - 1, j])
            if (S[i][j + 1] == "#"):
                black += 1
            else:
                white += 1

    #    print(S)
    #    print(Q)
    return black * white

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


def main(inp):
    S = parse(inp)
    H, W = S.shape
    # print(S)
    Q = np.full([H, W], False)
    #     print(Q)

    answer = 0
    for i in range(H):
        for j in range(W):
            if (Q[i][j] == False):
                answer += search(i, j, S, Q)
    return answer

print(main(sys.stdin))

Submission status: Runtime Error

Solution code:
(h, w)=list(map(int, input().split()))
ms=[]
for y in range(0, h):
    for c in input():
        if c == '#':
            ms.append(True)
        else:
            ms.append(False)

edge=[]
for i in range(0, h * w):
    edge.append([])

for y in range(0, h):
    for x in range(0, w):
        if ms[w * y + x]:
            if x != 0:
                if not ms[w * y + x - 1]:
                    edge[w * y + x].append(w * y + x - 1)
            if x != w - 1:
                if not ms[w * y + x + 1]:
                    edge[w * y + x].append(w * y + x + 1)
            if y != 0:
                if not ms[(y - 1) * w + x]:
                    edge[w * y + x].append((y - 1) * w + x)
            if y != h - 1:
                if not ms[(y + 1) * w + x]:
                    edge[w * y + x].append((y + 1) * w + x)
        else:
            if x != 0:
                if ms[w * y + x - 1]:
                    edge[w * y + x].append(w * y + x - 1)
            if x != w - 1:
                if ms[w * y + x + 1]:
                    edge[w * y + x].append(w * y + x + 1)
            if y != 0:
                if ms[(y - 1) * w + x]:
                    edge[w * y + x].append((y - 1) * w + x)
            if y != h - 1:
                if ms[(y + 1) * w + x]:
                    edge[w * y + x].append((y + 1) * w + x)

used=set()

def countwb(start):

    w = 0
    b = 1
    used.add(start)
    for etow in edge[start]:
        # already traversed
        if etow in used:
            continue

        used.add(etow)
        w += 1
        for etob in edge[etow]:
            if etob in used:
                continue
            v = countwb(etob)
            w += v[0]
            b += v[1]
    return (w, b)

count=0
for i in range(0, h * w):
    if not ms[i]:
        continue
    if i not in used:
        (w,b) = countwb(i)
        count += w * b
print(count)