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:
def main():
    from collections import defaultdict
    import sys
    sys.setrecursionlimit(10 ** 9)
    
    H, W = list(map(int, raw_input().split()))
    G = [list(raw_input()) for i in range(H)]
    
    Visited = [[0] * W for i in range(H)]
    direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    
    
    def dfs(ny, nx, color):
        for dy, dx in direction:
            if not ((0 <= ny + dy < H) and (0 <= nx + dx < W)):
                continue
    
            if G[ny + dy][nx + dx] == G[ny][nx]:
                continue
    
            if Visited[ny + dy][nx + dx] != 0:
                continue
    
            if G[ny + dy][nx + dx] == '#':
                Visited[ny + dy][nx + dx] = color
            else:
                Visited[ny + dy][nx + dx] = -color
    
            dfs(ny + dy, nx + dx, color)
    
    
    Color = 1
    for y in range(H):
        for x in range(W):
            if Visited[y][x] == 0:
                if G[y][x] == '#':
                    Visited[y][x] = Color
                else:
                    Visited[y][x] = -Color
                dfs(y, x, Color)
                Color += 1
    
    D = defaultdict(int)
    for i in range(1, Color + 1):
        D[i] = 0
        D[-i] = 0
    
    for row in Visited:
        for data in row:
            D[data] += 1
    
    ans = 0
    for key in D.keys():
        ans += D[key] * D[-key]
    
    print(ans // 2)
    
main()

Submission status: Accepted

Solution code:
def main():
    from collections import defaultdict
    import sys
    sys.setrecursionlimit(10 ** 9)
    
    H, W = list(map(int, input().split()))
    G = [list(input()) for i in range(H)]
    
    Visited = [[0] * W for i in range(H)]
    direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    
    
    def dfs(ny, nx, color):
        for dy, dx in direction:
            if not ((0 <= ny + dy < H) and (0 <= nx + dx < W)):
                continue
    
            if G[ny + dy][nx + dx] == G[ny][nx]:
                continue
    
            if Visited[ny + dy][nx + dx] != 0:
                continue
    
            if G[ny + dy][nx + dx] == '#':
                Visited[ny + dy][nx + dx] = color
            else:
                Visited[ny + dy][nx + dx] = -color
    
            dfs(ny + dy, nx + dx, color)
    
    
    Color = 1
    for y in range(H):
        for x in range(W):
            if Visited[y][x] == 0:
                if G[y][x] == '#':
                    Visited[y][x] = Color
                else:
                    Visited[y][x] = -Color
                dfs(y, x, Color)
                Color += 1
    
    D = defaultdict(int)
    for i in range(1, Color + 1):
        D[i] = 0
        D[-i] = 0
    
    for row in Visited:
        for data in row:
            D[data] += 1
    
    ans = 0
    for key in D.keys():
        ans += D[key] * D[-key]
    
    print(ans // 2)
    
main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)


h, w = map(int, input().split())
s_array = ["+" * (w + 2)]
for i in range(h):
    s_array.append("+" + input() + "+")
else:
    s_array.append("+" * (w + 2))
moving = [[0, 1], [0, -1], [1, 0], [-1, 0]]
visit = [[False for x in range(w+2)] for x in range(h+2)]


def recursive(mark_point, mark_sharp, row, point):
    # 訪問済みならreturn
    if visit[row][point]:
        return mark_point, mark_sharp
    else:
        visit[row][point] = True

    for x, y in moving:
        # 範囲外かどうかと連結かどうか
        if s_array[row + x][point + y] != "+" and s_array[row + x][point + y] != s_array[row][point]:
            if visit[row+x][point+y]:
                continue
            # 移動先のマークの確認
            if s_array[row + x][point + y] == "#":
                mark_sharp += 1
            else:
                mark_point += 1
            mark_point, mark_sharp = recursive(mark_point, mark_sharp, row + x, point + y)
    else:
        return mark_point, mark_sharp


res = 0
for row in range(1, h + 1):
    for point in range(1, w + 1):
        m, n = recursive(s_array[row][point].count("."), s_array[row][point].count("#"), row, point)
        res += m*n
print(res)

Submission status: Accepted

Solution code:
from collections import deque

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

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


def bfs(i, j):
    # print('探索from', i, j)
    # i,jで指定されたマスが属するregionに含まれる黒白の個数をかける
    if visited[i][j]:
        return 0
    else:
        cnt1, cnt2 = 0, 0
        que = deque([(i, j)])
        while que:
            # print(que)
            i, j = que.popleft()
            # print('now', i, j)
            if S[i][j] == '#':
                cnt1 += 1
            else:
                cnt2 += 1
            visited[i][j] = True
            # print(visited)
            # print(cnt1, cnt2)

            # 周りを探索
            for (dh, dw) in move:
                if ((-1 < (i + dh) < H) and (-1 < (j + dw) < W)):
                    # print(i + dh, j + dw)
                    if not visited[i + dh][j + dw]:
                        if S[i][j] != S[i + dh][j + dw]:
                            visited[i + dh][j + dw] = True
                            que.append((i + dh, j + dw))

        return cnt1 * cnt2


ans = 0
for i in range(H):
    for j in range(W):
        ans += bfs(i, j)
        # print('in for loop', i, j, ans)


print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 9)
 
H, W = list(map(int, input().split()))
G = [list(input()) for i in range(H)]
 
Visited = [[0] * W for i in range(H)]
direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]
 
 
def dfs(ny, nx, color):
    for dy, dx in direction:
        if not ((0 <= ny + dy < H) and (0 <= nx + dx < W)):
            continue
 
        if G[ny + dy][nx + dx] == G[ny][nx]:
            continue
 
        if Visited[ny + dy][nx + dx] != 0:
            continue
 
        if G[ny + dy][nx + dx] == '#':
            Visited[ny + dy][nx + dx] = color
        else:
            Visited[ny + dy][nx + dx] = -color
 
        dfs(ny + dy, nx + dx, color)
 
 
Color = 1
for y in range(H):
    for x in range(W):
        if Visited[y][x] == 0:
            if G[y][x] == '#':
                Visited[y][x] = Color
            else:
                Visited[y][x] = -Color
            dfs(y, x, Color)
            Color += 1
 
 
D = defaultdict(int)
for row in Visited:
    for data in row:
        D[data] += 1
 
ans = 0
for key in D.keys():
    if -key in D.keys():
        ans += D[key] * D[-key]
 
print(ans // 2)

Submission status: Accepted

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

sys.setrecursionlimit(10**9)

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

memo = [[0] * w for _ in range(h)]

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

def dfs(i, j, color):
    if not (0 <= i <= h-1 and 0 <= j <= w-1):
        return 0, 0
    if memo[i][j] == 1:
        return 0, 0
    if s[i][j] == color:
        return 0, 0
    memo[i][j] = 1
    white, black = 0, 0
    if s[i][j] == ".":
        white += 1
    else:
        black += 1
    for dx, dy in dir:
        cur_w, cur_b = dfs(i + dx, j + dy, s[i][j])
        white += cur_w
        black += cur_b
    return white, black

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

        ans += white * black

print(ans)

Submission status: Accepted

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

sys.setrecursionlimit(10**9)

from collections import deque

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

memo = [[0] * w for _ in range(h)]

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

def dfs(i, j, color):
    if not (0 <= i <= h-1 and 0 <= j <= w-1):
        return 0, 0
    if memo[i][j] == 1:
        return 0, 0
    if s[i][j] == color:
        return 0, 0
    memo[i][j] = 1
    white, black = 0, 0
    if s[i][j] == ".":
        white += 1
    else:
        black += 1
    for dx, dy in dir:
        cur_w, cur_b = dfs(i + dx, j + dy, s[i][j])
        white += cur_w
        black += cur_b
    return white, black

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

        ans += white * black

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

H,W=map(int,input().split())

board=[]
check=[[None]*W for i in range(H)]
answer=0

for i in range(H):
  S=list(input())
  board.append(S)
  
def dfs(i,j,color):
  if not (0<=i<H and 0<=j<W):
    return 0,0
  if board[i][j]==color:
    return 0,0
  if check[i][j]:
    return 0,0
  
  check[i][j]=True
  black,white=0,0
  
  if board[i][j]=='#':
  	black+=1
  else:
    white+=1
 
  tempblack,tempwhite=dfs(i+1,j,board[i][j])
  black+=tempblack
  white+=tempwhite
  
  tempblack,tempwhite=dfs(i-1,j,board[i][j])
  black+=tempblack
  white+=tempwhite
  
  tempblack,tempwhite=dfs(i,j+1,board[i][j])
  black+=tempblack
  white+=tempwhite

  tempblack,tempwhite=dfs(i,j-1,board[i][j])
  black+=tempblack
  white+=tempwhite
  return black,white

for i in range(H):
  for j in range(W):
    black,white=dfs(i,j,"!")
    answer+=black*white
print(answer)

Submission status: Accepted

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

from collections import deque

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

memo = [[0] * w for _ in range(h)]

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

ans = 0
for i in range(h):
    for j in range(w):
        if memo[i][j] == 1:
            continue
        memo[i][j] = 1
        black = 0
        white = 0
        if s[i][j] == ".":
            white += 1
        else:
            black += 1
        q = deque([(i, j)])

        while q:
            x, y = q.popleft()
            for dx, dy in dir:
                if not ((0 <= x + dx <= h-1) and (0 <= y + dy <= w-1)):
                    continue
                if memo[x + dx][y + dy] == 0 and s[x][y] != s[x+dx][y+dy]:
                    memo[x + dx][y + dy] = 1
                    if s[x + dx][y + dy] == ".":
                        white += 1
                    else:
                        black += 1
                    q.append((x+dx, y+dy))

        ans += black * white

print(ans)

Submission status: Accepted

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

from collections import deque

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

memo = [[0] * w for _ in range(h)]


ans = 0
for i in range(h):
    for j in range(w):
        if memo[i][j] == 1:
            continue
        memo[i][j] = 1
        black = 0
        white = 0
        if s[i][j] == ".":
            white += 1
        else:
            black += 1
        q = deque([(i, j)])

        while q:
            x, y = q.popleft()
            if x > 0:
                if memo[x - 1][y] == 0 and s[x - 1][y] != s[x][y]:
                    memo[x - 1][y] = 1
                    if s[x - 1][y] == ".":
                        white += 1
                    else:
                        black += 1
                    q.append((x - 1, y))
            if x < h - 1:
                if memo[x + 1][y] == 0 and s[x + 1][y] != s[x][y]:
                    memo[x + 1][y] = 1
                    if s[x + 1][y] == ".":
                        white += 1
                    else:
                        black += 1
                    q.append((x + 1, y))
            if y > 0:
                if memo[x][y - 1] == 0 and s[x][y - 1] != s[x][y]:
                    memo[x][y - 1] = 1
                    if s[x][y - 1] == ".":
                        white += 1
                    else:
                        black += 1
                    q.append((x, y - 1))
            if y < w - 1:
                if memo[x][y + 1] == 0 and s[x][y + 1] != s[x][y]:
                    memo[x][y + 1] = 1
                    if s[x][y + 1] == ".":
                        white += 1
                    else:
                        black += 1
                    q.append((x, y + 1))

        ans += black * white

print(ans)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
s = [None]*h
for i in range(h):
    s[i]=list(input())
    
###########
#Union Find
par = [] #親
rank = [] #木の深さ

#初期化
for i in range(h*w):
    #par[i]:i rank[i]:0
    par.append(i)
    rank.append(0)

#木の根を求める
def find(x,par):
    if par[x] == x:
        return x
    else:
        return find(par[x],par)

#xとyの属する集合の併合
def unite(x,y,par,rank):
    x = find(x,par)
    y = find(y,par)
    
    if x != y:
        #xとyの属している集合が異なる時
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x]==rank[y]:
                rank[x] += 1

#xとyが同じ集合に属するかの判定
def same(x,y,par):
    return find(x,par) == find(y,par)
###############
for i in range(h*w):
    if i//w + 1 < h and s[i//w][i%w] != s[i//w+1][i%w]:
        unite(i,i+w,par,rank)
    if i%w +1 < w and s[i//w][i%w] != s[i//w][i%w+1]:
        unite(i,i+1,par,rank)

res = [[0,0] for i in range(w*h)] #[".","#"]
for i in range(h*w):
    r = find(i,par)
    if s[i//w][i%w] ==".":
        res[r][0]+=1
    else:
        res[r][1]+=1

ans = 0
for i in range(h*w):
    ans += res[i][0]*res[i][1]
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int, input().split())
s = [input() for _ in range(H)]
visited = [[False]*W for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        stk = deque([(i,j)]) # stack
        visited[i][j] = True
        black,white = 0,0
        while stk: # なくなるまで
            y,x = stk.popleft()
            # print("now: ",y,x)
            from_ = s[y][x]
            if from_==".": white += 1
            else:          black += 1
            for dy,dx in ([1,0],[0,1],[-1,0],[0,-1]): 
                if not (0<=y+dy<H and 0<=x+dx<W):
                    continue
                to_   = s[y+dy][x+dx]
                if ((from_=="." and to_ == "#")
                 or (from_=="#" and to_ == ".") ):
                    if visited[y+dy][x+dx]: continue
                    stk.append([y+dy,x+dx])
                    visited[y+dy][x+dx] = True
        # print("black:{}, white:{}".format(black,white))
        ans += black*white
print(ans)

Submission status: Accepted

Solution code:
#深さ優先探索(DFS)

import sys
sys.setrecursionlimit(1000000)

h,w = map(int,input().split())
s = [input() for _ in range(h)]
t = [[None]*w for _ in range(h)]


def dfs(i,j,color):

  if not (0<=i<h and 0<=j<w):return 0,0
  if s[i][j]==color: return 0,0
  if t[i][j]:return 0,0
 
  t[i][j]=True
  wh,bl=0,0
  
  if s[i][j]=="#":
    bl+=1
  else:
    wh+=1

  #再起呼び出し
  tmp1,tmp2=dfs(i+1,j,s[i][j])
  wh,bl=wh+tmp1,bl+tmp2
 
  tmp1,tmp2=dfs(i-1,j,s[i][j])
  wh,bl=wh+tmp1,bl+tmp2
        
  tmp1,tmp2=dfs(i,j-1,s[i][j])
  wh,bl=wh+tmp1,bl+tmp2
 
  tmp1,tmp2=dfs(i,j+1,s[i][j])
  wh,bl=wh+tmp1,bl+tmp2
 
  return wh,bl
 
ans=0
for i in range(h):
  for j in range(w):
    a,b=dfs(i,j,"!")
    ans+=a*b
 
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline

H, W = map(int, input().split())
S = []
for i in [0]*H:
    l = input()
    S.append([1 if x == "#" else -1 for x in l])

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

cnt = 0
for y in range(H):
    for x in range(W):
        if S[y][x] == 1:
            check(S, x, y)
            cnt += wh*bk
            wh = 0
            bk = 0
            
print(cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)

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


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

used = [[False for _ in range(W)] for _ in range(H)]


def dfs(x, y):
    global nb, nw
    if S[y][x] == '#':
        nb += 1
    if S[y][x] == '.':
        nw += 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or nx >= W or ny < 0 or ny >= H:
            continue
        if used[ny][nx]:
            continue
        if S[y][x] == '#' and S[ny][nx] == '#':
            continue
        if S[y][x] == '.' and S[ny][nx] == '.':
            continue
        used[ny][nx] = True
        dfs(nx, ny)

ans = 0
for i in range(H):
    for j in range(W):
        if not used[i][j]:
            used[i][j] = True
            nb = 0
            nw = 0
            dfs(j, i)
            ans += nb*nw
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)

H, W = map(int, input().split())
s_list = []
for i in range(H):
    s_list.append(input())
check = [[False for _ in range(W)] for _ in range(H)]
move_x = [1, 0, -1, 0]
move_y = [0, 1, 0, -1]


def dfs(i, j):
    check[i][j] = True

    if s_list[i][j] == "#":
        cnt[0] += 1
    else:
        cnt[1] += 1

    for m in range(4):
        next_i = i + move_y[m]
        next_j = j + move_x[m]
        if 0 <= next_i < H and 0 <= next_j < W and s_list[i][j] != s_list[next_i][next_j] \
                and not check[next_i][next_j]:
            dfs(next_i, next_j)


ans = 0
for i in range(H):
    for j in range(W):
        cnt = [0] * 2
        dfs(i, j)
        ans += cnt[0] * cnt[1]
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
s_list = []
for i in range(H):
    s_list.append(input())
check = [[False for _ in range(W)] for _ in range(H)]
move_x = [1, 0, -1, 0]
move_y = [0, 1, 0, -1]
import sys
sys.setrecursionlimit(10**9)

def dfs(i, j):
    check[i][j] = True

    if s_list[i][j] == "#":
        cnt[0] += 1
    else:
        cnt[1] += 1

    for m in range(4):
        next_i = i + move_y[m]
        next_j = j + move_x[m]
        if 0 <= next_i < H and 0 <= next_j < W  and s_list[i][j] != s_list[next_i][next_j] \
                and not check[next_i][next_j]:
            dfs(next_i, next_j)


ans = 0
for i in range(H):
    for j in range(W):
        cnt = [0] * 2
        dfs(i, j)
        ans += cnt[0] * cnt[1]
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
S = []
for _ in [0]*H:
	S.append(list(input().rstrip()))

visited = []
for _ in [0]*H:
	visited.append([False] * W)

delta = [[1, 0], [0, 1], [-1, 0], [0, -1]]

ans = 0
for x in range(H):
	for y in range(W):
		if visited[x][y]: continue
		b = 0
		w = 0
		queue = deque()
		queue.append([x, y])
		visited[x][y] = True
		while len(queue) is not 0:
			px, py = queue[0]
			queue.popleft()
			if S[px][py] == '#' : b += 1
			else: w += 1
			found = False
			for dx, dy in delta:
				nx = px + dx
				ny = py + dy
				if 0 <= nx < H and 0 <= ny < W and not visited[nx][ny]:
					if S[px][py] != S[nx][ny]:
						found = True
						visited[nx][ny] = True
						queue.append([nx, ny])

		ans += b * w

print(ans)

Submission status: Accepted

Solution code:
h,w = list(map(int, input().split())) 
s=list([]) 
foot = list([False for i in range(w)] for j in range(h))

def is_new_white(i,j):
    global h,w, s, foot
    if ((i<0) or (j<0) or (i>=h) or(j>=w)):
        return False
    elif (not foot[i][j] and (s[i][j] == ".")):
        return True
    else:
        return False

def is_new_black(i,j):
    global h,w, s, foot
    if ((i<0) or (j<0) or (i>=h) or(j>=w)):
        return False
    elif (not foot[i][j] and (s[i][j] == "#")):
        return True
    else:
        return False

def check(i,j):
    global s, foot
    black = list([])
    white = list([])
    white_c = 0
    black_c = 0
    
    if foot[i][j] == True:
        return 0
    else:
        if s[i][j] == "#":
            black.append([i,j])
            foot[i][j] = True
            black_c += 1
        else:
            white.append([i,j])
            foot[i][j] = True
            white_c += 1

    while (bool(black) or bool(white)):
        while bool(black):
            pos = black.pop(0)
            tmp = [[pos[0]-1,pos[1]],[pos[0],pos[1]-1],[pos[0]+1,pos[1]],[pos[0],pos[1]+1]]
            for x in tmp:
                if is_new_white(x[0], x[1]):
                    white_c += 1
                    white.append([x[0],x[1]])
                    foot[x[0]][x[1]] = True

        while bool(white):
            pos = white.pop(0)
            tmp = [[pos[0]-1,pos[1]],[pos[0],pos[1]-1],[pos[0]+1,pos[1]],[pos[0],pos[1]+1]]
            for x in tmp:
                if is_new_black(x[0], x[1]):
                    black_c += 1
                    black.append([x[0],x[1]])
                    foot[x[0]][x[1]] = True
    return black_c * white_c


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

ans = 0
for i in range(h):
    for j in range(w):
        ans += check(i,j)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

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

def bfs(i, j):
    b, w = 0, 0
    visited[i][j] = True
    que = deque([(i, j)])

    while que:
        ci, cj = que.popleft()
        if S[ci][cj] == '#':
            b += 1
        else:
            w += 1

        for di, dj in move:
            ni, nj = ci + di, cj + dj
            if not (0 <= ni < H and 0 <= nj < W) or visited[ni][nj]:
                continue
            if S[ci][cj] != S[ni][nj]:
                visited[ni][nj] = True
                que.append((ni, nj))

    return b * w


result = 0
for i in range(H):
    for j in range(W):
        if visited[i][j]:
            continue
        result += bfs(i, j)
print(result)

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
from collections import Counter, defaultdict, deque

INF = float('inf')
MOD = 10 ** 9 + 7
dy = (0, -1, 0, 1)
dx = (1, 0, -1, 0)

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


H, W = LI()
B = [[1 if s == '#' else 0 for s in S()] for _ in range(H)]


def BFS(i, j):
    white = 0
    queue = deque([(i, j)])
    visited = set()
    visited_b = set()  # 連結されている黒マス
    while queue:
        y, x = queue.pop()
        color = B[y][x]

        if color == 0 and (y, x) not in visited:
            white += 1

        if color == 1:
            visited_b.add((y, x))
        visited.add((y, x))

        for k in range(4):
            ny = y + dy[k]
            nx = x + dx[k]
            if (ny, nx) in visited:
                continue

            if ny < 0 or ny >= H or nx < 0 or nx >= W:
                continue

            if B[ny][nx] == color:
                continue

            queue.append((ny, nx))

    return white, visited_b


ans = 0
visited_b = set()
for h in range(H):
    for w in range(W):
        if B[h][w] == 1 and (h, w) not in visited_b:
            tmp, v = BFS(h, w)
            ans += tmp * len(v)
            visited_b |= v

print(ans)

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
from collections import Counter, defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

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


# UnionFind
class UnionFind:
    # 負: ルートで値は木の深さを表す
    # 正: 子で値は次のノードを表す
    def __init__(self, size: int) -> None:
        self.nodes = [-1] * size  # 初期状態では全てのノードがルート

    def get_root(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            self.nodes[x] = self.get_root(self.nodes[x])
            return self.nodes[x]

    def unite(self, x: int, y: int) -> None:
        root_x, root_y = self.get_root(x), self.get_root(y)
        if root_x != root_y:
            if self.nodes[root_x] != self.nodes[root_y]:  # グラフの高さが異なる場合
                # 木のランクが高い方のルートに併合させる
                # 併合後にランクの変動はない
                if self.nodes[root_x] < self.nodes[root_y]:
                    self.nodes[root_y] = root_x
                else:
                    self.nodes[root_x] = root_y
            else:
                # ランクが等しい木同士を併合させるので
                # 併合後は木のランクが1つ上がる
                self.nodes[root_x] += -1
                self.nodes[root_y] = root_x


H, W = LI()
B = [[1 if s == '#' else 0 for s in S()] for _ in range(H)]

uf = UnionFind(H * W)

for h in range(H):
    for w in range(W):
        if w < W - 1 and B[h][w] != B[h][w + 1]:
            uf.unite(h * W + w, h * W + w + 1)
        if h < H - 1 and B[h][w] != B[h + 1][w]:
            uf.unite(h * W + w, (h + 1) * W + w)

black = defaultdict(int)
white = defaultdict(int)
for h in range(H):
    for w in range(W):
        i = h * W + w
        if B[h][w] == 1:
            black[uf.get_root(i)] += 1
        else:
            white[uf.get_root(i)] += 1

ans = 0
for n in black.keys():
    ans += black[n] * white[n]

print(ans)

Submission status: Accepted

Solution code:
def getminLT(i):
  if LT[i] == i:
    return i
  else:
    return getminLT(LT[i])

H, W = list(map(int, input().split()))

D = []
for i in range(H):
  D.append(input())

M = [[0] * W for i in range(H)]
LT = [0]
for i in range(H):
  for j in range(W):
    if i == 0 and j == 0:
      continue
    flag = False
    if i != 0:
      if D[i][j] != D[i-1][j]:
        M[i][j] = M[i-1][j]
        flag = True
    if j != 0:
      if D[i][j] != D[i][j-1]:
        M[i][j] = M[i][j-1]
        if flag == True:
          
          LT[max(getminLT(M[i-1][j]), getminLT(M[i][j-1]))] = LT[min(getminLT(M[i][j-1]), getminLT(M[i-1][j]))]
        flag = True
    if flag == False:
        M[i][j] = len(LT)
        LT.append(len(LT))
for i in range(len(LT)):
  LT[i] = getminLT(LT[i])
  
L = [[] for i in range(len(LT))]
for i in range(H):
  for j in range(W):
  	L[LT[M[i][j]]].append((i, j))
#print(M)
#print(LT)
#print(L)
cnt = 0
for i in L:
  E = 0
  A = 0
  for j in i:
    if (j[0] + j[1]) % 2 == 0:
      E += 1
    else:
      A += 1
  cnt += E * A
print(cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline


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

move = ((1, 0), (-1, 0), (0, 1), (0, -1))
visited = [[False] * W for _ in range(H)]
b, w = 0, 0

def dfs(i, j):
    if visited[i][j]:
        return (0, 0)

    visited[i][j] = True

    if S[i][j] == '#':
        b, w = 1, 0
    else:
        b, w = 0, 1

    for di, dj in move:
        ni, nj = i + di, j + dj
        if not (0 <= ni < H and 0 <= nj < W):
            continue
        if S[i][j] != S[ni][nj]:
                db, dw = dfs(ni, nj)
                b, w = b + db, w + dw

    return (b, w)


result = 0
for i in range(H):
    for j in range(W):
        b, w = dfs(i, j)
        result += b * w
print(result)

Submission status: Accepted

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

ans = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == "x":
            continue
        q = deque()
        q.append((h, w))
        shw = S[h][w]
        bl = wh = 0
        while len(q):
            i, j = q.popleft()
            if not 0 <= i < H or not 0 <= j < W:
                continue
            if S[i][j] == "x":
                continue
            dist = i + j - h - w
            if dist % 2 == 0 and shw != S[i][j]:
                continue
            if dist % 2 == 1 and shw == S[i][j]:
                continue
            if S[i][j] == "#":
                bl += 1
            else:
                wh += 1
            S[i][j] = "x"
            q.append((i-1, j))
            q.append((i+1, j))
            q.append((i, j-1))
            q.append((i, j+1))
        ans += bl * wh

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(180000)

def dfs(i,j):
    for m in move:
        ni = i + m[0]
        nj = j + m[1]
        if ni < 0 or ni >= H or nj < 0 or nj >= W:
            continue
        if ch[ni][nj]:
            continue
        if X[i][j] == X[ni][nj]:
            continue
            
        ch[ni][nj] = 1
        K[(ni+nj)%2] += 1
        dfs(ni, nj)
        
H, W = map(int, input().split())
X = [[[0, 1][a=="#"] for a in input()] for i in range(H)]
ch = [[0] * W for _ in range(H)]
    
move = [[0,1], [0,-1], [1,0], [-1,0]]

K = [0, 0]
ans = 0
for i in range(H):
    for j in range(W):
        if ch[i][j] > 0:
            continue
        ch[i][j] = 1
        K = [0, 0]
        K[(i+j)%2] = 1
        dfs(i, j)
        ans += K[0] * K[1]
        
print(ans)

Submission status: Accepted

Solution code:
from itertools import chain, product
H,W = map(int,input().split())
grid = list(chain(
    ([None,]*(W+2),),
    (list(chain(
      (None,),
      map(lambda x: x=='#', input()),
      (None,),
      )) for _ in range(H)),
    ([None,]*(W+2),),
    ))

neighbors = ((1,0),(0,1),(-1,0),(0,-1))

res = 0

stack = []

for y,x in product(range(1,H+1),range(1,W+1)):
  if grid[y][x] is None:
    continue
  stack.append((y,x))
  black,white = 0,0

  while stack:
    y,x = stack.pop()
    v = grid[y][x]
    if v is None:
      continue
    grid[y][x] = None

    if v:
      black += 1
    else:
      white += 1
    v = not v

    for dy,dx in neighbors:
      w = grid[y+dy][x+dx]
      if w == v:
        stack.append((y+dy,x+dx))

  res += black*white

print(res)