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:
from itertools import groupby

class UnionFindVerSize():
    def __init__(self, N):
        global S,H,W
        """ N個のノードのUnion-Find木を作成する """
        # 親の番号を格納する。自分が親だった場合は、自分の番号になり、それがそのグループの番号になる
        self._parent = [n for n in range(0, N)]
        # グループのサイズ（個数）
        self._size = [1] * N

        self._black=[0]*N
        self._white=[0]*N

        for i in range(0,H*W):
            h=i//W
            w=i%W
            if S[h][w]=='#':
                self._black[i]=1
                self._white[i]=0
            else:
                self._black[i]=0
                self._white[i]=1

    def find_root(self, x):
        """ xの木の根(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):
        """ 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._black[gy]+=self._black[gx]
            self._white[gy]+=self._white[gx]
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._black[gx]+=self._black[gy]
            self._white[gx]+=self._white[gy]
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        """ xが属するグループのサイズ（個数）を返す """
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        """ グループ数を計算して返す """
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

    def calc_black(self,x):
        return self._black[self.find_root(x)]

    def calc_white(self,x):
        return self._white[self.find_root(x)]


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

uf=UnionFindVerSize(H*W)
for i in range(0,H*W):
    h=i//W
    w=i%W
    if W-1>=w+1:
        if S[h][w]!=S[h][w+1]:
            uf.unite(i,i+1)
    if H-1>=h+1:
        if S[h][w]!=S[h+1][w]:
            uf.unite(i,i+W)

root=[uf.find_root(i) for i in range(0,H*W)]
root.sort()

ans=0
root=groupby(root)
for key,group in root:
    black=uf.calc_black(key)
    white=uf.calc_white(key)
    ans+=black*white

print(ans)

Submission status: Accepted

Solution code:
H,W = map(int, input().split())
fields = [list(input()) for i in range(H)]
# print(fields)

# seen = [False] * (H*W+1)
seen = [[False] * W for i in range(H)]
mv = [(0,1),(0,-1),(1,0),(-1,0)]
from collections import deque
from collections import defaultdict
ans  = 0
for i in range(H):
    for j in range(W):
        if seen[i][j]: continue
        # print("i,j",i,j)
        d = defaultdict(int)
        q = deque()
        q.append((i,j))
        # d[fields[i][j]] += 1
        while len(q) > 0:
            h,w = q.popleft()
            s = fields[h][w] #そこの文字列
            for dh, dw in mv:
                if 0 <= h + dh < H and 0 <= w + dw < W:
                    if seen[h+dh][w+dw]:continue
                    t = fields[h+dh][w+dw] #隣接セルの文字
                    if t == s:continue #同じ場合は加算せず
                    # print(s,t,h,w,h+dh,w+dw,"debug")
                    d[s] += 1
                    q.append((h+dh,w+dw))
                    seen[h+dh][w+dw] = True
        ans += d["#"]*d["."]
# print(seen)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

dq = deque([])
if S[0][0] == '.':
    dq.append([0,0,'.'])
else:
    dq.append([0,0,'#'])

Visited = [[False for _ in range(w)] for _ in range(h)]
Visited[0][0] = True

All_grid = deque([])
for i in range(h):
    for j in range(w):
        if i == 0 and j == 0:
            pass
        else:
            All_grid.append([i,j])

ans = 0
black = 0
white = 0
while dq:
    now = dq.popleft()

    y = now[0]
    x = now[1]
    color = now[2]

    if color == '.':
        white += 1
    else:
        black += 1

    Nexts = [[y,x-1], [y,x+1], [y-1,x], [y+1,x]]
    for nex in Nexts:
        if nex[0] >= h or nex[0] < 0 or nex[1] >= w or nex[1] < 0:
            continue
        if Visited[nex[0]][nex[1]] == True:
            continue

        if color == '.' and S[nex[0]][nex[1]] == '.':
            continue
        elif color == '#' and S[nex[0]][nex[1]] == '#':
            continue
        elif color == '.' and S[nex[0]][nex[1]] == '#':
            dq.append([nex[0], nex[1], '#'])
            Visited[nex[0]][nex[1]] = True
        else:
            dq.append([nex[0], nex[1], '.'])
            Visited[nex[0]][nex[1]] = True

    if len(dq) == 0:
        ans += black * white
        black = 0
        white = 0

        while All_grid:
            cand = All_grid.popleft()
            i = cand[0]
            j = cand[1]
            if Visited[i][j] == False:
                c = S[i][j]
                dq.append([i,j,c])
                Visited[i][j] = True
                break

print(ans)

Submission status: Accepted

Solution code:
H,W = map(int, input().split())
grid = [-1] * (W+4) * 2
black_ind = []
for _ in range(H):
	grid += [-1]*2
	I = input()
	for i in range(W):
		if I[i] == '#':
			grid.append(1)
			black_ind.append(len(grid)-1)
		else:
			grid.append(0)
	grid += [-1]*2

grid += [-1] * (W+4) * 2

move = [1,-1,W+4,-(W+4)]
ans = 0
for b in black_ind:
	if grid[b] == 2:
		continue
	cnt_b = 1
	cnt_w = 0
	q = [b]
	grid[b] = 2
	while q:
		cp = q.pop()
		if grid[cp] == 2:
			for d in move:
				if grid[cp+d] == 0:
					grid[cp+d] = 3
					cnt_w += 1
					q.append(cp+d)
		elif grid[cp] == 3:
			for d in move:
				if grid[cp+d] == 1:
					grid[cp+d] = 2
					cnt_b += 1
					q.append(cp+d)

	ans += cnt_b * cnt_w
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
S = [input() for _ in range(H)]

ans = 0
searched = [[0]*W for _ in range(H)]
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

for i in range(H):
	for j in range(W):
		if searched[i][j] or S[i][j] == ".":
			continue
		num_b = 0
		num_w = 0
		q = deque()
		q.append((i, j))
		num_b += 1
		searched[i][j] = 1
		while q:
			y, x = q.popleft()
			for k in range(4):
				ny = y + dy[k]
				nx = x + dx[k]
				if 0 <= ny <= H-1 and 0 <= nx <= W-1 and not searched[ny][nx] and S[ny][nx] != S[y][x]:
					searched[ny][nx] = 1
					if S[ny][nx] == "#":
						num_b += 1
					else:
						num_w += 1
					q.append((ny, nx))
		ans += num_b*num_w

print(ans)

Submission status: Accepted

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

M = [[] for i in range(h*w)]

for i in range(h*w):
    a = i // w
    b = i % w
    for d in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
        aa = d[0] + a
        bb = d[1] + b
        if 0 <= aa < h and 0 <= bb < w \
            and S[a][b] != S[aa][bb]:
            M[a*w+b].append(aa*w+bb)

# print(M)

ans = 0
V = [0] * (h*w)
D = {".":0, "#":1}
for i in range(h*w):
    if V[i] == 0:
        ANS = [0, 0]
        Q = [i]
        s = 0
        V[i] = 1
        ANS[D[S[i//w][i%w]]] += 1
        while s < len(Q):
            i = Q[s]
            for x in M[i]:
                if V[x] == 0:
                    V[x] = 1
                    ANS[D[S[x//w][x%w]]] += 1
                    Q.append(x)
            s += 1
        # print(ANS)
        ans += ANS[0] * ANS[1]
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from collections import deque
    H, W = (int(i) for i in input().split())
    c = [input() for i in range(H)]
    seen = [[False]*W for _ in range(H)]
    que = deque()
    for h in range(H):
        for w in range(W):
            if c[h][w] == "#":
                que.append((h, w))

    def bfs(sy, sx):
        que = deque()
        que.append((sy, sx))
        d = ((1, 0), (0, 1), (-1, 0), (0, -1))
        flag = True  # Trueなら黒マス
        bla = 0
        whi = 0
        while que:
            uh, uw = que.popleft()
            if seen[uh][uw]:
                continue
            if c[uh][uw] == "#":
                flag = True
                bla += 1
                seen[uh][uw] = True
            else:
                flag = False
                whi += 1
                seen[uh][uw] = True
            for dy, dx in d:
                next_h = uh + dy
                next_w = uw + dx
                if not(0 <= next_h < H and 0 <= next_w < W):
                    continue
                if seen[next_h][next_w]:
                    continue
                if flag and c[next_h][next_w] == '#':
                    continue
                if not(flag) and c[next_h][next_w] == '.':
                    continue
                que.append((next_h, next_w))
        return whi*bla

    ans = 0
    for q in que:
        if seen[q[0]][q[1]]:
            continue
        ans += bfs(q[0], q[1])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import queue
def main():
    h, w = map(int, input().split())
    s = [input().rstrip() for _ in range(h)]
    g = [[0 for j in range(w)] for i in range(h)]
    num = 1
    q = queue.Queue()
    for i in range(h):
        for j in range(w):
            if g[i][j] != 0:
                continue
            q.put([i, j])
            g[i][j] = num
            while not q.empty():
                y, x = q.get()
                if 0 < y and g[y-1][x] == 0 and s[y][x] != s[y-1][x]:
                    g[y-1][x] = num
                    q.put([y-1, x])
                if y < h-1 and g[y+1][x] == 0 and s[y][x] != s[y+1][x]:
                    g[y+1][x] = num
                    q.put([y+1, x])
                if 0 < x and g[y][x-1] == 0 and s[y][x] != s[y][x-1]:
                    g[y][x-1] = num
                    q.put([y, x-1])
                if x < w-1 and g[y][x+1] == 0 and s[y][x] != s[y][x+1]:
                    g[y][x+1] = num
                    q.put([y, x+1])
            num += 1
    blk, wht = [0]*(num+1), [0]*(num+1)
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                blk[g[i][j]] += 1
            else:
                wht[g[i][j]] += 1
    ans = 0
    for i in range(num+1):
        ans += blk[i] * wht[i]
    print(ans)

if __name__ == "__main__":
    main()

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 si in range(H):
    for sj in range(W):
        if visited[si][sj]:
            continue
        visited[si][sj] = True
        queue = deque()
        queue.append((si, sj))
        black = 0
        white = 0
        while queue:
            i, j = queue.popleft()
            if S[i][j] == '#':
                black += 1
            else:
                white += 1
            for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                ni, nj = i+di, j+dj
                if 0 <= ni < H and 0 <= nj < W and not visited[ni][nj] and S[i][j] != S[ni][nj]:
                    visited[ni][nj] = True
                    queue.append((ni, nj))
        ans += black * white
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
black = 0
white = 0
#x,y渡すと、（ｈ、ｗ）に入ってるかどうか判定
def check(s,t):
    if (0 <=  s <= h - 1) and (0 <= t <= w - 1):
        return True
    else:
        return False
def bfs(que):
    finished = set()
    while que:
        x , y, color = que.popleft()
        if x+y*w not in finished:
            finished.add(x+y*w)
            for i, j in ((1, 0), (0, 1)):
                if abs(i) + abs(j) < 2 and check(y+j,x+i):
                    if (x+i)+(y+j)*w not in finished:
                        que.append([x+i,y+j,grid[y+j][x+i]])
                    if color != grid[y+j][x+i]:
                        adjacent_list[x+w*y].append((x + i)+w*(y + j))
                        adjacent_list[(x + i)+w*(y + j)].append(x+w*y)
def dfs(node):
    global white
    global black
    finished.add(node)
    y,x = divmod(node,w)
    if grid[y][x] == '#':
        black += 1
    else:
        white += 1
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i)
from collections import deque
h,w = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
ans = 0
adjacent_list = [[] for i in range(h*w)]
que = deque()
que.append([0,0,grid[0][0]])
bfs(que)
#再び初期化
finished = set()
for i in range(h*w):
    #頂点iからdfsをする。黒と白をカウントしておいて最後にかける
    black = 0
    white = 0
    if i not in finished:
        dfs(i)
        ans += black * white
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
black = 0
white = 0
#x,y渡すと、（ｈ、ｗ）に入ってるかどうか判定
def check(s,t):
    if (0 <=  s <= h - 1) and (0 <= t <= w - 1):
        return True
    else:
        return False
def bfs(que):
    finished = set()
    while que:
        x , y, color = que.popleft()
        if x+y*w not in finished:
            finished.add(x+y*w)
            for i in range(-1,2,1):
                for j in range(-1,2,1):
                    if abs(i) + abs(j) < 2 and check(y+j,x+i):
                        if (x+i)+(y+j)*w not in finished:
                            que.append([x+i,y+j,grid[y+j][x+i]])
                        if color != grid[y+j][x+i]:
                            adjacent_list[x+w*y].append((x + i)+w*(y + j))
def dfs(node):
    global white
    global black
    finished.add(node)
    y,x = divmod(node,w)
    if grid[y][x] == '#':
        black += 1
    else:
        white += 1
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i)
from collections import deque
h,w = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
ans = 0
adjacent_list = [[] for i in range(h*w)]
"""
que = deque()
que.append([0,0,grid[0][0]])
bfs(que)
"""
for y in range(h):
    for x in range(w):
        for i in range(-1,2,1):
            for j in range(-1,2,1):
                if abs(i) + abs(j) < 2 and check(y+j,x+i):
                    if grid[y][x] != grid[y+j][x+i]:
                        adjacent_list[x+w*y].append((x + i)+w*(y + j))
#再び初期化
finished = set()
for i in range(h*w):
    #頂点iからdfsをする。黒と白をカウントしておいて最後にかける
    black = 0
    white = 0
    if i not in finished:
        dfs(i)
        ans += black * white
print(ans)

Submission status: Accepted

Solution code:
# 幅優先探索か深さ優先探索で、上下左右の隣接と異なる色ならば、連続する1つの領域とする
# 各領域ごとに、白マス数×黒マス数を計算し、その合計が答え

h, w = list(map(int, input().split()))
masu = [input() for _ in range(h)]
visited = [[False for _ in range(w)] for _ in range(h)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# とりあえず周囲の番兵は使わずに書いてみよう……

# 再帰関数の呼び出し回数が多くなる時はこれが必要！！無いとruntime errorになる。
import sys
sys.setrecursionlimit(400*400 + 10)

def dfs(hi, wi, white, black):
    global colors
    global dx, dy
    global visited

    # print(hi, wi)

    visited[hi][wi] = True
    if masu[hi][wi] == '.':
        white += 1
    if masu[hi][wi] == '#':
        black += 1

    for neighbor in zip(dx, dy):
        h_new = hi + neighbor[0]
        w_new = wi + neighbor[1]
        # print("new: " , h_new, w_new)
        if 0 <= h_new <= h-1 and 0 <= w_new <= w-1:
            if not visited[h_new][w_new]:
                if masu[hi][wi] != masu[h_new][w_new]:
                    white, black = dfs(h_new, w_new, white, black)
    
    return white, black

ans = 0
for hi in range(h):
    for wi in range(w):
        if not visited[hi][wi]:
            white, black = dfs(hi, wi, 0, 0)
            ans += white * black

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int,input().split())
S = [list(input()) for i in range(H)]
blacklist = []
for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            blacklist.append((h,w))
ans = 0
alr = [[0 for i in range(W)] for j in range(H)]
h1 = [0,0,1,-1]
w1 = [1,-1,0,0]
for h,w in blacklist:
    if alr[h][w] == 0:
        bcount = 1
        wcount = 0
        que = deque()
        que.append((h,w,True))
        alr[h][w] = 1
        while que:
            hn,wn,black = que.popleft()
            black = not black
            for i in range(4):
                if 0 <= hn+h1[i] <= H-1 and 0 <= wn+w1[i] <= W-1 and not alr[hn+h1[i]][wn+w1[i]]:
                    if (not black) and S[hn+h1[i]][wn+w1[i]] == '.':
                        wcount += 1
                        que.append((hn+h1[i],wn+w1[i],black))
                        alr[hn+h1[i]][wn+w1[i]] = 1
                    elif black and S[hn+h1[i]][wn+w1[i]] == '#':
                        bcount += 1
                        que.append((hn+h1[i],wn+w1[i],black))
                        alr[hn+h1[i]][wn+w1[i]] = 1
        ans += wcount*bcount
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys

sys.setrecursionlimit(10**9)

def dfs(h,w,start):
    if S[h][w]=="#":
        black[start[0]][start[1]]+=1
    else:
        white[start[0]][start[1]]+=1
    
    visited[h][w]=1
    if h!=0:
        if visited[h-1][w]==-1 and S[h-1][w]!=S[h][w]:
            dfs(h-1,w,start)
    if w!=0:
        if visited[h][w-1]==-1 and S[h][w-1]!=S[h][w]:
            dfs(h,w-1,start)        
    if h!=H-1:
        if visited[h+1][w]==-1 and S[h+1][w]!=S[h][w]:
            dfs(h+1,w,start)        
    if w!=W-1:
        if visited[h][w+1]==-1 and S[h][w+1]!=S[h][w]:
            dfs(h,w+1,start)    
    return 

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

S=[]

for _ in range(H):
    S.append(list(input()))

visited=[[-1 for j in range(W)] for i in range(H)]
black=[[0 for j in range(W)] for i in range(H)]
white=[[0 for j in range(W)] for i in range(H)]

for i in range(H):
    for j in range(W):
        if visited[i][j]==-1:
            dfs(i,j,[i,j])
        #print(visited)

ans=0
for i in range(H):
    for j in range(W):
        ans+=black[i][j]*white[i][j]
"""
print(S)
print(black)
print(white)
"""
print(ans)

Submission status: Accepted

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

h,w = inm()
s = []
for i in range(h):
    s.append(ins())
a = [[0]*w for i in range(h)]
dir = [(0,1),(0,-1),(1,0),(-1,0)]
id = 0
for i in range(h):
    for j in range(w):
        if a[i][j]!=0:
            continue
        id += 1
        a[i][j] = id
        q = [(i,j)]
        while len(q)>0:
            x,y = q.pop()
            c = s[x][y]
            for d in dir:
                u = x+d[0]
                v = y+d[1]
                if 0<=u<h and 0<=v<w and \
                   a[u][v]==0 and s[u][v]!=c:
                    a[u][v] = id
                    q.append((u,v))
bk = [0]*(id+1)
wh = [0]*(id+1)
for i in range(h):
    for j in range(w):
        if s[i][j]=='#':
            bk[a[i][j]] += 1
        else:
            wh[a[i][j]] += 1
print(sum([bk[i]*wh[i] for i in range(1,id+1)]))

Submission status: Accepted

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def all_group_members(self):
        dic = {}
        for x in range(self.N):
            r = self.find(x)
            dic.setdefault(r, [])
            dic[r].append(x)
        return dic

H,W=map(int, input().split())
S=[input() for _ in range(H)]
D=[1,0,-1,0,1]
UF=UnionFind(H*W)
for i in range(H):
    for j in range(W):
        for k in range(4):
            x=i+D[k]
            y=j+D[k+1]
            if 0<=x<H and 0<=y<W:
                if S[i][j]!=S[x][y]:
                    UF.union(x*W+y,i*W+j)
ans=0
for g in UF.all_group_members().values():
    w=0
    b=0
    for v in g:
        x,y=divmod(v,W)
        if S[x][y]=="#":
            b+=1
        else:
            w+=1
    ans+=w*b
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict


class UnionFind():
    # nはノードの数
    def __init__(self, n):
        self.n = n
        self.parents = [-1]*n  # 根のノードは限らないので注意

    # xはノードの番号
    def find(self, x):  # あるノードの親を探すためのメソッド
        if self.parents[x] < 0:  # 親の場合、そのグラフの要素の個数を負の値で保持している
            return x
        else:
            # 再帰的に親を探しにいき、得られた値を格納する
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # x, yはノードの番号
    def union(self, x, y):
        x = self.find(x)  # 根の番号を取得
        y = self.find(y)  # 根の番号を取得
        if x == y:
            return  # 同じ親ならば合体させる必要はない

        # ※ それぞれ要素の個数が負の値で格納されている
        if self.parents[x] > self.parents[y]:
            # yのグループの方が要素の個数が多い場合 (yの方が値が小さいということは、負の世界では値が大きいため)
            # 必ずxの方が要素が多い状態にする
            x, y = y, x

        self.parents[x] += self.parents[y]  # 負の値同士だが、これで良い
        self.parents[y] = x  # yは親ではなくなったため、新しい親であるxの値を正でもつ

    # xはノードの番号
    def size(self, x):
        # 親まで辿ればグループの大きさが負の値で格納されているため、それにマイナスをつけてreturnする
        return -self.parents[self.find(x)]

    # x, yはノードの番号
    def same(self, x, y):
        # 親が同じ = 同じグループに属するならTrueがreturnされる
        return self.find(x) == self.find(y)

    # xはノードの番号
    def members(self, x):
        root = self.find(x)  # 親の値を取得する
        # findで再帰的に親の値が獲得できる
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        # 親となっているノードの番号をリストでreturnする
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_counts(self):
        # グループの数をreturnする
        return len(self.roots())

    def all_group_members(self):
        # 親のノードの番号をキーにして、子のノードの番号を対応させた辞書を返す
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        # printした時の表記
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


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

# 定義するときはUnionFind(要素数)
uf = UnionFind(H*W)
# 木を定義する
for i in range(H):
    for j in range(W):
        if 0 <= i < H-1:  # 最終行でないのであれば実行
            if gridgraph[i][j] != gridgraph[i+1][j]:
                uf.union(W*i+j, W*(i+1)+j)  # 要素の番号の振り方はこうやる

        if 0 <= j < W-1:  # 最終列でないのであれば実行
            if gridgraph[i][j] != gridgraph[i][j+1]:
                uf.union(W*i+j, W*i+j+1)  # 要素の番号の振り方はこうやる

# 根の番号をキーにして、その連結成分に黒, 白それぞれいくつ入っているかを管理する辞書
black = defaultdict(int)
white = defaultdict(int)
for i in range(H):
    for j in range(W):
        if gridgraph[i][j] == "#":
            black[uf.find(W*i+j)] += 1
        else:
            white[uf.find(W*i+j)] += 1
ans = 0
for u in uf.roots():
    ans += black[u] * white[u]
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

uf = UnionFind(H*W)

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


black = defaultdict(int)
white = defaultdict(int)
unions = set(uf.parent)
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            black[uf.root(W*i+j)] += 1
        else:
            white[uf.root(W*i+j)] += 1
ans = 0
for u in unions:
    ans += black[u] * white[u]

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

es = defaultdict(list)

for i in range(H):
    for j in range(W):
        if 0 <= i < H-1:
            if S[i][j] != S[i+1][j]:
                es[(i,j)].append((i+1, j))
                es[(i+1,j)].append((i, j))

        if 0 <= j < W-1:
            if S[i][j] != S[i][j+1]:
                es[(i,j)].append((i, j+1))
                es[(i,j+1)].append((i, j))

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

ans = 0
for i in range(H):
    for j in range(W):
        b,w = 0,0
        if not checked[i][j]:
            checked[i][j] = True
            if S[i][j] == "#":
                b += 1
            else:
                w += 1
            q = es[(i,j)]
            while q:
                y,x = q.pop()
                if not checked[y][x]:
                    checked[y][x] = True
                    if S[y][x] == "#":
                        b += 1
                    else:
                        w += 1
                    q.extend(es[(y,x)])
            ans += b * w

print(ans)

Submission status: Accepted

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
h,w = map(int, input().split())
l = [None]*h
for i in range(h):
    l[i] = list(input())

from collections import deque
b_Q = deque()
for i in range(h):
    for j in range(w):
      if l[i][j]=="#":
          b_Q.append([i,j])

ans=0
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
visited=[[0 for i in range(w)] for j in range(h)]
while b_Q:
    p = b_Q.popleft()
    now = l[p[0]][p[1]]

    if visited[p[0]][p[1]] == 1:
        continue
    visited[p[0]][p[1]] = 1
    b_cnt=1
    w_cnt=0

    search_Q = deque()
    search_Q.append([p[0],p[1]])

    while search_Q:
        sch = search_Q.popleft()
        current = l[sch[0]][sch[1]]
        for i in range(4):
            nx = sch[1] + dx[i]
            ny = sch[0] + dy[i]
            if 0 <= nx < w and 0 <= ny < h:
                if current != l[ny][nx] and visited[ny][nx] == 0: # b->w or w->b
                    if current=="#":
                        w_cnt+=1
                    else:
                        b_cnt+=1
                    search_Q.append([ny,nx])
                    visited[ny][nx]=1
    ans+= b_cnt*w_cnt
print(ans)

Submission status: Accepted

Solution code:
import sys
#input = sys.stdin.buffer.readline
from collections import deque

def main():
    H,W = map(int,input().split())
    s = [list(map(str,input())) for _ in range(H)]
    
    dist =[[] for _ in range(H*W)]
    for i in range(H*W):
        x,y = i//W,i%W
        dx,dy = [1,0,-1,0],[0,1,0,-1]
        for j in range(4):
            nx,ny = x+dx[j],y+dy[j]
            if (0<=nx<H and 0<=ny<W and s[x][y]!=s[nx][ny]):
                dist[x*W+y].append(nx*W+ny)

    ans = 0
    go = [False for _ in range(H*W)]
    for i in range(H*W):
        if go[i]:
            continue
        else:
            cc = [0,0]
            queue = deque([i])
            while queue:
                go[i] = True
                now = queue.pop()
                x,y = now//W,now%W
                if s[x][y] == "#":
                    cc[0] += 1
                else:
                    cc[1] += 1
                for fol in dist[now]:
                    if go[fol]:
                        continue
                    else:
                        queue.append(fol)
                        go[fol] = True
        ans += cc[0]*cc[1]
                        
    print(ans)

if __name__ == "__main__":
    main()