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: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

h,w = li()
inp = [lc() for _ in range(h)]
grid = [[-1]*w for _ in range(h)]
for i, row in enumerate(inp):
    for j, col in enumerate(row):
        if inp[i][j] == ".":
            grid[i][j] = 0
        else:
            grid[i][j] = 1

dis = [-1, 0, 1, 0]
djs = [0, -1, 0, 1]
hasVisited = [[False]*w for _ in range(h)]

def dfs(sti, stj, h, w):
    stack = [(sti, stj)]
    cnt_white = 0
    cnt_black = 0
    while stack:
        i,j = stack.pop()
        for di, dj in zip(dis, djs):
            if 0 <= i+di < h and 0 <= j+dj < w:
                if (not hasVisited[i+di][j+dj]) and (grid[i+di][j+dj] != grid[i][j]):
                    hasVisited[i+di][j+dj] = True
                    if grid[i+di][j+dj] == 0:
                        cnt_white += 1
                    else:
                        cnt_black += 1
                    stack.append((i+di, j+dj))
               
    return cnt_white * cnt_black

ans = 0
for r in range(h):
    for c in range(w):
        if hasVisited[r][c]:
            continue
        
        cnt = dfs(r,c,h,w)
        ans += cnt
        
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

uf = UnionFind(H*W)

for i in range(H):
    for j in range(W):
        if j < W-1 and S[i][j] != S[i][j+1]:
            uf.unite(i*W+j, i*W+j+1)
        if i < H-1 and S[i][j] != S[i+1][j]:
            uf.unite(i*W+j, (i+1)*W+j)
for i in range(H*W):
    uf.root(i)

c1 = Counter()
c2 = Counter()

for i in range(H):
    for j in range(W):
        k = i*W+j
        if S[i][j] == '.':
            c1[uf.root(k)] += 1
        else:
            c2[uf.root(k)] += 1

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)
h, w = map(int, input().split())
s = []
for i in range(h):
    s.append(input())

ans = 0

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

was = [[0 for i in range(w)] for j in range(h)]

def dfs(x, y):
    global cc
    global was
    was[x][y] = 1
    if s[x][y] == '#':
        cc[1] += 1
    else:
        cc[0] += 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx >= 0 and ny >= 0 and nx < h and ny < w and s[nx][ny] != s[x][y] and not was[nx][ny]:
            dfs(nx, ny)

for i in range(h):
    for j in range(w):
        if not was[i][j]:
            cc = [0] * 2
            dfs(i, j)
            ans += cc[1] * cc[0]
print(ans)

Submission status: Accepted

Solution code:
h, w = list(map(int, input().split()))
sss = ['x' * (w + 2)] + list('x' + input() + 'x' for _ in range(h)) + ['x' * (w + 2)]
checked = [[False] * (w + 2) for _ in range(h + 2)]
ans = 0
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]


def dfs(i, j):
    w_cnt, b_cnt = 0, 0
    q = [(i, j, sss[i][j] == '.')]
    while q:
        y, x, is_white = q.pop()
        if checked[y][x]:
            continue
        checked[y][x] = True
        if is_white:
            w_cnt += 1
        else:
            b_cnt += 1

        for di, dj in move:
            ni = y + di
            nj = x + dj
            if checked[ni][nj]:
                continue
            nc = sss[ni][nj]
            if nc == 'x':
                continue
            elif (nc == '.') == is_white:
                continue
            else:
                q.append((ni, nj, nc == '.'))
    return w_cnt * b_cnt


for i in range(1, h + 1):
    for j in range(1, w + 1):
        if checked[i][j]:
            continue
        ans += dfs(i, j)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
index = ".#".index
S = [list(map(index, input())) for i in range(H)]

dd = ((-1, 0), (0, -1), (1, 0), (0, 1))

used = [[0]*W for i in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if used[i][j]:
            continue
        que = deque([(i, j)])
        used[i][j] = 1
        C = [0, 0]
        C[S[i][j]] += 1
        f = ((i + j) & 1) ^ S[i][j]
        while que:
            x, y = que.popleft()
            s = ((x + y) & 1) ^ 1
            for dx, dy in dd:
                nx = x + dx; ny = y + dy
                if not 0 <= nx < H or not 0 <= ny < W or used[nx][ny] or (s ^ S[nx][ny]) != f:
                    continue
                que.append((nx, ny))
                used[nx][ny] = 1
                C[S[nx][ny]] += 1
        ans += C[0] * C[1]
print(ans)

Submission status: Runtime Error

Solution code:
def aising19_c():
    h, w = (int(x) for x in input().split())
    grid = [[s for s in str(input())] for _ in range(h)]
    visited = [[False]*w for _ in range(h)]
    ans = 0

    def dfs(x, y):
        nonlocal ans
        visited[x][y] = True
        for dx, dy in ((-1,0),(0,-1),(0,1),(1,0)):
            nx, ny = x+dx, y+dy
            if nx < 0 or h <= nx or ny < 0 or w <= ny: continue
            if grid[nx][ny] == grid[x][y]: continue
            if visited[nx][ny]: continue
            if grid[nx][ny] == '.': ans += 1
            dfs(nx, ny)

    for i in range(h):
        for j in range(w):
            if grid[i][j] == '#':
                dfs(i, j)
                visited = [[False]*w for _ in range(h)]
    print(ans)

if __name__ == '__main__':
    aising19_c()

Submission status: Runtime Error

Solution code:
def dfs(i, j, c):
    visited[i][j] = 1
    current.append((i, j))
    for di, dj in (1, 0), (-1, 0), (0, 1), (0, -1):
        ni, nj = i + di, j + dj
        if not (0 <= ni < H and 0 <= nj < W and not visited[ni][nj]):
            continue
        if S[ni][nj] == c:
            continue
        dfs(ni, nj, not c)


H, W = map(int, input().split())
S = [[c == "#" for c in input()] for _ in range(H)]

ans = 0
visited = [[0] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j] and not visited[i][j]:
            current = []
            dfs(i, j, True)
            b, w = 0, 0
            for k, l in current:
                if S[k][l]:
                    b += 1
                else:
                    w += 1
            ans += b * w
print(ans)

Submission status: Runtime Error

Solution code:
def dfs(x, y, matrix, visited, isWhite):
    global black, white
    dxy = [[1, 0], [-1, 0], [0, -1], [0, 1]]
    visited[y][x] = True
    w = len(matrix[0])
    h = len(matrix)

    for dx, dy in dxy:
        nx = x + dx
        ny = y + dy

        if nx < 0 or w <= nx or ny < 0 or h <= ny:
            continue

        if visited[ny][nx] is True:
            continue

        if (matrix[ny][nx] == "#" and isWhite is False) or (
            matrix[ny][nx] == "." and isWhite is True
        ):
            continue

        if matrix[ny][nx] == "#":
            black += 1
        else:
            white += 1

        isWhite = not isWhite
        dfs(nx, ny, matrix, visited, isWhite)
        isWhite = not isWhite

    return


h, w = map(int, input().split())
matrix = [""] * h
for i in range(h):
    matrix[i] = input()

ans = 0
visited = [[False] * w for _ in range(h)]

for i in range(h):
    for j in range(w):
        if matrix[i][j] == "#" and visited[i][j] is False:
            black = 1
            white = 0
            dfs(j, i, matrix, visited, False)
            ans += black * white

print(ans)

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
s = [input() for i in range(h)]
t = [[None] * w for i in range(h)]
d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
def dfs(i, j, bw):
    global h, w
    if not (0 <= i < h and 0 <= j < w) or s[i][j] == bw or t[i][j]:
        return 0, 0
    t[i][j] = True
    W, b = 0, 0
    if s[i][j] == "#":
        b += 1
    else:
        W += 1
    for k in d:
        n, m = dfs(i + k[0], j + k[1], s[i][j])
        W += n
        b += m
    return W, b
ans = 0
for i in range(h):
    for j in range(w):
        X, Y = dfs(i, j, "u shi ta pu ni chi a ku n wara")
        ans += X * Y
print(ans)

Submission status: Runtime Error

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

#g = [[] for _ in range(h*w)]

n = h*w

def Find(x, par):
    if par[x] < 0:
        return x
    else:
        par[x] = Find(par[x], par)
        return par[x]

def Unite(x, y, par, rank):
    x = Find(x, par)
    y = Find(y, par)

    if x != y:
        if rank[x] < rank[y]:
            par[y] += par[x]
            par[x] = y
        else:
            par[x] += par[y]
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

def Same(x, y, par):
    return Find(x, par) == Find(y, par)

def Size(x, par):
    return -par[Find(x, par)]

par = [-1]* n
rank = [0]*n

for y in range(h):
    for x in range(w):
        idx1 = y*w+x
        for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
            ny, nx = y+dy, x+dx
            if 0 <= ny < h and 0 <= nx < w:
                idx2 = ny*w+nx
                if S[y][x] != S[ny][nx]:
                    Unite(idx1, idx2, par, rank)

ans = 0
print(par)
d = {}
for i in range(n):
    if par[i] < 0:
        d[i] = [0, 0]

for i in range(n):
    y, x = divmod(i, w)
    if i in d:
        if S[y][x] == '#':
            d[i][0] += 1
        else:
            d[i][1] += 1
    else:
        if S[y][x] == '#':
            d[par[i]][0] += 1
        else:
            d[par[i]][1] += 1

ans = 0
for k, v in d.items():
    ans += v[0]*v[1]
print(ans)

Submission status: Runtime Error

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

#g = [[] for _ in range(h*w)]

n = h*w

def Find(x, par):
    if par[x] < 0:
        return x
    else:
        par[x] = Find(par[x], par)
        return par[x]

def Unite(x, y, par, rank):
    x = Find(x, par)
    y = Find(y, par)

    if x != y:
        if rank[x] < rank[y]:
            par[y] += par[x]
            par[x] = y
        else:
            par[x] += par[y]
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

def Same(x, y, par):
    return Find(x, par) == Find(y, par)

def Size(x, par):
    return -par[Find(x, par)]

par = [-1]* n
rank = [0]*n

for y in range(h):
    for x in range(w):
        idx1 = y*w+x
        for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
            ny, nx = y+dy, x+dx
            if 0 <= ny < h and 0 <= nx < w:
                idx2 = ny*w+nx
                if S[y][x] != S[ny][nx]:
                    Unite(idx1, idx2, par, rank)

ans = 0
#print(par)
d = {}
for i in range(n):
    if par[i] < 0:
        d[i] = [0, 0]

for i in range(n):
    y, x = divmod(i, w)
    if i in d:
        if S[y][x] == '#':
            d[i][0] += 1
        else:
            d[i][1] += 1
    else:
        if S[y][x] == '#':
            d[par[i]][0] += 1
        else:
            d[par[i]][1] += 1

ans = 0
for k, v in d.items():
    ans += v[0]*v[1]
print(ans)

Submission status: Runtime Error

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0
  for i in range(h):
    for j in range(w):
      if field[i][j]=='#':
        q=collections.deque()
        visited=[[False]*w for _ in range(h)]
        q.append((i,j))
        while q:
          y,x=q.popleft()
          if visited[y][x]:
            continue
          visited[y][x]=True
          for dy,dx in dd:
            ny=y+dy
            nx=x+dx
            if 0<=ny<h and 0<=nx<w:
              if field[y][x]==field[ny][nx]:
                continue
              if visited[ny][nx]:
                continue
              if field[ny][nx]=='.':
                # ans+=1
              q.append((ny,nx))
    # print(ans)
  return ans

# main()
print(main())

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(100000)


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

def DFS(h,w,black,white,m):
    black,white=BorW(h,w,black,white)
    step=[[0,1],[0,-1],[1,0],[-1,0]]
    seen[h][w]=1
    for dh,dw in step:
        nh=h+dh
        nw=w+dw
        if 0<=nh<H and 0<=nw<W:
            if seen[nh][nw]==0 and m!=S[nh][nw]:
                seen[nh][nw]=1
                black,white=DFS(nh,nw,black,white,S[nh][nw])
    return black,white


def BorW(h,w,black,white):
    if S[h][w]=="#":
        black+=1
    else:
        white+=1
    return black,white


seen=[[0]*W for _ in range(H)]

L=[]
for h in range(H):
    for w in range(W):
        black=0
        white=0
        if seen[h][w]==0:
            black,white=DFS(h,w,black,white,S[h][w])
            L.append([black,white])
ans=0
for b,w in L:
     ans+=b*w

print(ans)

Submission status: Runtime Error

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

def DFS(h,w,black,white,m):
    black,white=BorW(h,w,black,white)
    step=[[0,1],[0,-1],[1,0],[-1,0]]
    seen[h][w]=1
    for dh,dw in step:
        nh=h+dh
        nw=w+dw
        if 0<=nh<H and 0<=nw<W:
            if seen[nh][nw]==0 and m!=S[nh][nw]:
                seen[nh][nw]=1
                black,white=DFS(nh,nw,black,white,S[nh][nw])
    return black,white


def BorW(h,w,black,white):
    if S[h][w]=="#":
        black+=1
    else:
        white+=1
    return black,white


seen=[[0]*W for _ in range(H)]

L=[]
for h in range(H):
    for w in range(W):
        black=0
        white=0
        if seen[h][w]==0:
            black,white=DFS(h,w,black,white,S[h][w])
            L.append([black,white])
ans=0
for b,w in L:
     ans+=b*w

print(ans)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(8000)


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

def rec(h,w):
    seen[h][w]=1
    step=[[0,1],[0,-1],[1,0],[-1,0]]
    ret=0
    for dh,dw in step:
        nh=h+dh
        nw=w+dw
        if 0<=nh<H and 0<=nw<W:
            if seen[nh][nw]==0 and S[nh][nw]==".":
                ret+=1
                seen[nh][nw]=1
                for ddh,ddw in step:
                    if 0<=nh + ddh<H and 0<=nw + ddw < W:
                        if seen[nh+ddh][nw+ddw]==0 and S[nh+ddh][nw+ddw]=="#":
                            ret+=rec(nh+ddh,nw+ddw)
    return ret


ans=0
for h in range(H):
    for w in range(W):
        seen=[[0]*W for _ in range(H)]
        if S[h][w]=="#":
            ans+=rec(h,w)

print(ans)

Submission status: Runtime Error

Solution code:
H, W = list(map(int, input().split()))
S = [""]*H
score = 0

def DFS(start):
    tempVisited.add(start)
    current = S[start[0]][start[1]]
    global bp
    global wp
    if current == "#":
        bp += 1
    else:
        wp += 1
    for ii in [-1,1]:
        if start[0]+ii >= 0 and start[0]+ii < H:
            if S[start[0]+ii][start[1]] != current:
                if not {(start[0]+ii, start[1])} & set(tempVisited):
                    DFS((start[0]+ii,start[1]))
    for jj in [-1,1]:
        if start[1]+jj >= 0 and start[1]+jj < W:
            if S[start[0]][start[1]+jj] != current:
                if not {(start[0], start[1]+jj)} & set(tempVisited):
                    DFS((start[0],start[1]+jj))

for i in range(H):
    S[i] = str(input())

visited = set()

for i in range(H):
    for j in range(W):
        if not ({(i, j)} & visited):
            tempVisited = set()
            bp = 0
            wp = 0
            DFS((i,j))
            score += bp*wp
            # if len(tempVisited) > 1:
            visited = visited | tempVisited

print(score)

Submission status: Runtime Error

Solution code:
H, W = list(map(int, input().split()))
S = [""]*H
score = 0

def DFS(start):
    tempVisited.add(start)
    current = S[start[0]][start[1]]
    global bp
    global wp
    if current == "#":
        bp += 1
    else:
        wp += 1
    for ii in [-1,1]:
        if start[0]+ii >= 0 and start[0]+ii < H:
            if S[start[0]+ii][start[1]] != current:
                if not {(start[0]+ii, start[1])} & set(tempVisited):
                    DFS((start[0]+ii,start[1]))
    for jj in [-1,1]:
        if start[1]+jj >= 0 and start[1]+jj < W:
            if S[start[0]][start[1]+jj] != current:
                if not {(start[0], start[1]+jj)} & set(tempVisited):
                    DFS((start[0],start[1]+jj))

for i in range(H):
    S[i] = str(input())

visited = set()

for i in range(H):
    for j in range(W):
        if not ({(i, j)} & visited):
            tempVisited = set()
            bp = 0
            wp = 0
            DFS((i,j))
            score += bp*wp
            if len(tempVisited) > 1:
                visited = visited | tempVisited

print(score)

Submission status: Runtime Error

Solution code:
H, W = list(map(int, input().split()))
S = [""]*H
score = 0

def DFS(start):
    tempVisited.add(start)
    current = S[start[0]][start[1]]
    # if current == "#":
    #     bp += 1
    # else:
    #     wp += 1
    for ii in [-1,1]:
        if start[0]+ii >= 0 and start[0]+ii < H:
            if S[start[0]+ii][start[1]] != current:
                if not {(start[0]+ii, start[1])} & set(tempVisited):
                    DFS((start[0]+ii,start[1]))
    for jj in [-1,1]:
        if start[1]+jj >= 0 and start[1]+jj < W:
            if S[start[0]][start[1]+jj] != current:
                if not {(start[0], start[1]+jj)} & set(tempVisited):
                    DFS((start[0],start[1]+jj))

for i in range(H):
    S[i] = str(input())

visited = set()

for i in range(H):
    for j in range(W):
        if not ({(i, j)} & visited):
            tempVisited = set()
            DFS((i,j))
            bp = 0
            wp = 0
            for item in tempVisited:
                if S[item[0]][item[1]] == '#':
                    bp += 1
                else:
                    wp += 1
            score += bp*wp
            if len(tempVisited) > 1:
                visited = visited | tempVisited

print(score)

Submission status: Runtime Error

Solution code:
H, W = list(map(int, input().split()))
S = [""]*H
count = 0

def DFS(start):
    visited.add(start)
    current = S[start[0]][start[1]]
    for ii in [-1,1]:
        if start[0]+ii >= 0 and start[0]+ii < H:
            if S[start[0]+ii][start[1]] != current:
                if not {(start[0]+ii, start[1])} & set(visited):
                    DFS((start[0]+ii,start[1]))
    for jj in [-1,1]:
        if start[1]+jj >= 0 and start[1]+jj < W:
            if S[start[0]][start[1]+jj] != current:
                if not {(start[0], start[1]+jj)} & set(visited):
                    DFS((start[0],start[1]+jj))

for i in range(H):
    S[i] = str(input())

for i in range(H):
    for j in range(W):
        visited = set()
        removal = 0
        DFS((i,j))
        for item in visited:
            # print(S[item[0]][item[1]],S[i][j])
            if S[item[0]][item[1]] == S[i][j]:
                removal += 1
        count += len(visited) - removal
        # print(visited, len(visited),removal)

print(count//2)

Submission status: Runtime Error

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

is_used = [[False] * w for _ in range(h)]

di = [+1, 0, -1, 0]
dj = [0, +1, 0, -1]


def dfs(i, j):
    if s[i][j] == '#':
        cnt_w, cnt_b = 0, 1
    else:
        cnt_w, cnt_b = 1, 0

    for k in range(4):
        ni = i + di[k]
        nj = j + dj[k]
        if ni < 0 or ni >= h or nj < 0 or nj >= w:
            continue
        if is_used[ni][nj]:
            continue
        if s[i][j] == s[ni][nj]:
            continue

        is_used[ni][nj] = True
        cw, cb = dfs(ni, nj)
        cnt_w += cw
        cnt_b += cb
    return (cnt_w, cnt_b)


ans = 0
for i in range(h):
    for j in range(w):
        if not is_used[i][j]:
            is_used[i][j] = True
            cnt_w, cnt_b = dfs(i, j)
            ans += cnt_w * cnt_b

print(ans)

Submission status: Runtime Error

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

move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
seen = [[0] * W for _ in range(H)]

# Fの点を頂点とするグラフを考える。グラフの連結成分に'#'がbコ, '.'がwコある場合、
# b*wが条件を満たす

def dfs(sy, sx):
    seen[sy][sx] = 1
    b, w = 1, 0
    
    for dy, dx in move:
      ny = sy + dy
      nx = sx + dx
      if 0 <= ny < H and 0 <= nx < W and F[ny][nx] != F[sy][sx] and not seen[ny][nx]:
        p = dfs(ny, nx)
        b += p[1]  # 逆にしている
        w += p[0]  # 天才か？
    return (b, w)
        
count = 0
for i in range(H):
    for j in range(W):
        if not seen[i][j]:
            b, w = dfs(i, j)
            count += b * w

print(count)

Submission status: Runtime Error

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


def rec(h,w,seen):
	if S[h][w] == '.':
		res = [1, 0]
	else:
		res = [0, 1]
	dh = [-1, 1, 0, 0]
	dw = [0, 0, -1, 1] 
	seen[h][w] = 1
	for i in range(4):
		nh = h+dh[i]
		nw = w+dw[i]
		if 0 <= nh <= H-1 and 0 <= nw <= W-1:
			if seen[nh][nw] == 0 and S[nh][nw] != S[h][w]:
				r0, r1 = rec(nh, nw, seen)
				res[0] += r0
				res[1] += r1
					
	return res

ans = 0
for h in range(H):
	for w in range(W):
		if seen[h][w] != 1:
			t0, t1 = rec(h, w, seen)
			ans += t0 * t1
print(ans)

Submission status: Runtime Error

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

move = (-1, 1)
count = []

def dfs(i, j, seen):
    seen.add((i, j))
    if F[i][j] == '#':
        next = '.'
    else:
        next = '#'

    for m in move:
        if 0 <= i+m < H and F[i+m][j] == next and (i+m, j) not in seen:
            seen.add((i+m, j))
            if F[i][j] == '#':
                count.append((i+m, j))

            dfs(i+m, j, seen)
        if 0 <= j+m < W and F[i][j+m] == next and (i, j+m) not in seen:
            seen.add((i, j+m))
            if F[i][j] == '#':
                count.append((i, j+m))
            dfs(i, j+m, seen)

for i in range(H):
    for j in range(W):
        if F[i][j] == '#':
            dfs(i, j, set())

print(len(count))

Submission status: Runtime Error

Solution code:
H, W = map(int,input().split())
S = [input() for _ in range(H)]
#%%
visited = [[False]*W for _ in range(H)]
dx = [1,0,-1,0]
dy = [0,1,0,-1]

def dfs(x,y,res, numW,numK,state):
    # print(x,y,res)
    # state=0: next=Black
    # state=1: next=White
    newres = 0
    flag = True
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if nx<0 or nx>=H or ny<0 or ny>=W:
            continue
        if visited[nx][ny]:
            continue
        if state==0 and S[nx][ny]=='#':
            visited[nx][ny] = True
            newres += dfs(nx,ny,res+numW,numW,numK+1,1)
            flag = False
        elif state==1 and S[nx][ny]=='.':
            visited[nx][ny] = True
            newres += dfs(nx,ny,res+numK,numW+1,numK,0)
            flag = False
    
    # if flag:
    #     visited[x][y] = False
    if S[x][y]=='.':
        return newres + numK
    elif S[x][y]=='#':
        return newres + numW

ans = 0
for i in range(H):
    for j in range(W):
        if not visited[i][j]:
            numW = S[i][j]=='.'
            numK = S[i][j]=='#'
            visited[i][j] = True
            ans += dfs(i,j,0,numW,numK,numK)
            # print('X,Y =',i,j,ans)

print(ans)

Submission status: Runtime Error

Solution code:
from numba import jit
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline

@jit
def DFS(add,next):
    global cnt
    x,y=add
    for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
        X,Y=x+i,y+j
        if 0<=X<h and 0<=Y<w:
            if S[X][Y]==next and color[X][Y]=="white":
                color[X][Y]="black"
                DFS([X,Y],"." if next=="#" else "#")
                if next==".":cnt +=1


h,w=map(int,input().split())
S=[list(input()) for _ in range(h)]
cnt=0

for i in range(h):
    for j in range(w):
        if S[i][j]=="#":
            color=[["white" for _ in range(w)] for _ in range(h)]
            color[i][j]="black"
            DFS([i,j],".")

print(cnt)

Submission status: Runtime Error

Solution code:
def DFS(add,next):
    global cnt
    x,y=add
    for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
        X,Y=x+i,y+j
        if 0<=X<h and 0<=Y<w:
            if S[X][Y]==next and color[X][Y]=="white":
                color[X][Y]="black"
                DFS([X,Y],"." if next=="#" else "#")
                if next==".":cnt +=1


h,w=map(int,input().split())
S=[list(input()) for _ in range(h)]
cnt=0

for i in range(h):
    for j in range(w):
        if S[i][j]=="#":
            color=[["white" for _ in range(w)] for _ in range(h)]
            color[i][j]="black"
            DFS([i,j],".")

print(cnt)

Submission status: Runtime Error

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

for i in range(w):
    for j in range(h):
        for di in [-1,0,1]:
            for dj in [-1,0,1]:
                if abs(di)+abs(dj)!=1:
                    continue
                if 0<=i+di<w and 0<=j+dj<h:
                    if s[j][i]!=s[j+dj][i+di]:
                        g[j*w+i].append(i+di+(j+dj)*w)

visit=[0]*(h*w)
ans=0
black=[0]*(h*w)
white=[0]*(h*w)

def rec(j,i,rj,ri):
    if s[j][i]=='#':
        black[rj*w+ri]+=1
    else:
        white[rj*w+ri]+=1
    
    for n in g[j*w+i]:
        if visit[n]==1:
            continue

        nj=n//w
        ni=n%w

        visit[n]=1

        rec(nj,ni,rj,ri)

for i in range(w):
    for j in range(h):
        if visit[w*j+i]:
            continue
        visit[w*j+i]=1

        rec(j,i,j,i)
        
        ans+=black[w*j+i]*white[w*j+i]

print(ans)

Submission status: Runtime Error

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

for i in range(w):
    for j in range(h):
        for di in [-1,0,1]:
            for dj in [-1,0,1]:
                if abs(di)+abs(dj)!=1:
                    continue
                if 0<=i+di<w and 0<=j+dj<h:
                    if s[j][i]!=s[j+dj][i+di]:
                        g[j*w+i].append(i+di+(j+dj)*w)

visit=[0]*(h*w)
ans=0
black=[0]*(h*w)
white=[0]*(h*w)

def rec(j,i,rj,ri):
    if s[j][i]=='#':
        black[rj*w+ri]+=1
    else:
        white[rj*w+ri]+=1
    
    for n in g[j*w+i]:
        if visit[n]==1:
            continue

        nj=n//w
        ni=n%w

        visit[n]=1

        rec(nj,ni,rj,ri)

for i in range(w):
    for j in range(h):
        if visit[w*j+i]:
            continue
        visit[w*j+i]=1

        if s[j][i]=='#':
            rec(j,i,j,i)
        else:
            rec(j,i,j,i)
        
        ans+=black[w*j+i]*white[w*j+i]

print(ans)

Submission status: Runtime Error

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

C = [[1 for i in range(W)] for j in range(H)]
L = ['.', '#']
D = {'.':0, '#':1}
tx = [1, 0, -1, 0]
ty = [0, 1, 0, -1]

def dfs(x, y, c, l):
    C[x][y] = 0
    l[c] += 1
    for i in range(4):
        nx = x + tx[i]
        ny = y + ty[i]
        if 0 <= nx < H and 0 <= ny < W and C[nx][ny] and L[c] != S[nx][ny]:
            l = dfs(nx, ny, 1 - c, l)
    return l

ans = 0
for i in range(H):
    for j in range(W):
        l = dfs(i, j, D[S[i][j]], [0, 0])
        ans += l[0] * l[1]

print(ans)

Submission status: Runtime Error

Solution code:
h,w = map(int,input().split())
L = []
for i in range(h):
    L.append(input())
visited = [[False]*w for i in range(h)]
def black(y,x):
    li = ((1,0),(0,1),(-1,0),(0,-1))
    for dy,dx in li:
        ny,nx = y+dy,x+dx
        if not 0<=ny<h or not 0<=nx<w or visited[ny][nx] == True:
            continue
        if L[ny][nx] == ".":
            visited[ny][nx] = True
            #print(L[ny][nx])
            white(ny,nx)
        else:
            cnt +=1
            return
def white(y,x):
    li = ((1,0),(0,1),(-1,0),(0,-1))
    for dy,dx in li:
        ny,nx = y+dy,x+dx
        if not 0<=ny<h or not 0<=nx<w or visited[ny][nx] == True:
            continue
        if L[ny][nx] == "#":
            visited[ny][nx] = True
            #print(L[ny][nx])
            black(ny,nx)
        else:
            return
cnt = 0
for j in range(h):
    for i in range(w):
        if L[j][i] == "#":
            black(j,i)
            cnt +=1
print(cnt)

Submission status: Runtime Error

Solution code:
import sys
#sys.setrecursionlimit(10 ** 7)

dct = {"#": 0, ".": 1, "-": 2}


def f(c):
    return dct[c]


h, w = map(int, input().split())
s = [[2] * (w + 2)]
for _ in range(h):
    s.append([2] + list(map(f, input())) + [2])
s.append([2] * (w + 2))

d = [(-1, 0), (1, 0), (0, -1), (0, 1)]


def dfs(col, hh, ww):
    if s[hh][ww] != col:
        return

    cnt[col] += 1
    s[hh][ww] = 2

    for dh, dw in d:
        nh = hh + dh
        nw = ww + dw
        dfs(1-col, nh, nw)


ans = 0
for hi in range(1, h + 1):
    for wi in range(1, w + 1):
        cnt = [0, 0]
        if s[hi][wi] != 2:
            dfs(s[hi][wi], hi, wi)
        ans += cnt[0] * cnt[1]

print(ans)