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:
class UnionFind():
    def __init__(self, n=0):
        self.d = [-1]*n
    
    def find(self, x):
        if self.d[x] < 0: return x
        self.d[x] = self.find(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x,y=self.find(x),self.find(y)
        if x==y:return False
        if self.d[x] > self.d[y]: x,y=y,x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

    def same(self, x,y): return self.find(x)==self.find(y)
    def size(self,x): return -self.d[self.find(x)]

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

def index(i,j):
  return i*W+j

dx,dy = (1,-1,0,0),(0,0,1,-1)
uf = UnionFind(H*W)
for i in range(H):
  for j in range(W):
    x1,y1 = i,j
    for k in range(4):
      x2,y2 = i+dx[k],j+dy[k]
      if 0<=x2<H and 0<=y2<W:
        if S[x1][y1] != S[x2][y2]:
          uf.unite(index(x1,y1),index(x2,y2))
  
data = {}
for k in range(H*W):
  if uf.d[k]==-1:continue
  g = uf.find(k)
  if not data.get(g):
    data[g] = [0,0]
  i,j = divmod(k,W)
  if S[i][j] == '#':
    data[g][0] += 1
  else:
    data[g][1] += 1
    
ans = 0
for k in data.keys():
  ans += data[k][0]*data[k][1]

print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import defaultdict

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

    def all_group_members(self):
        self.all_group_member=defaultdict(list)
        for i in range(self.n):
            self.all_group_member[self.find(i)].append(i)
        return self.all_group_member

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


def main():
    h, w = map(int, input().split())
    s = [list(input()) for i in range(h)]
    uf = UnionFind(h*w)
    for i in range(h):
        for j in range(w):
            if i != h-1:
                if s[i][j] != s[i+1][j]:
                    uf.union((i*w)+j, (i*w)+j+w)
            if j != w-1:
                if s[i][j] != s[i][j+1]:
                    uf.union((i*w)+j, (i*w)+j+1)
    ans=0
    for item in uf.all_group_members().values():
        A=0
        B=0
        for grid in item:
            i,j=divmod(grid,w)
            if s[i][j]=='.':
                A+=1
            else:
                B+=1
        ans+=A*B
    print(ans)
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1 for _ in range(n)]  # 各要素の親 自分が根の場合は -1 * (木の要素数)

    def root(self, x):  # xが属する木の根を返す
        if self.parents[x] < 0:  # 自分が根の場合
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def merge(self, x, y):  # xが属する木とyが属する木を合体する
        x_root = self.root(x)  # xの根
        y_root = self.root(y)  # yの根

        if x_root == y_root:  # 同じ木に属する
            return

        if self.parents[x_root] > self.parents[y_root]:  # x_rootの要素数 > y_rootの要素数 にしたい
            x_root, y_root = y_root, x_root

        self.parents[x_root] += self.parents[y_root] # x_rootにy_rootを合体
        self.parents[y_root] = x_root


def main():
    h, w = map(int, input().split())
    grid = [list(input()) for _ in range(h)]
    black_list = []
    uf = UnionFind(h * w)

    for r in range(h):
        for c in range(w):
            if grid[r][c] == "#":
                black_list.append([r, c])
            for dr, dc in [[0, 1], [1, 0]]:
                nr = r + dr
                nc = c + dc
                if not (0 <= nr < h and 0 <= nc < w):
                    continue
                if grid[r][c] != grid[nr][nc]:
                    # 0 to h*w-1 に変換
                    uf.merge(r * w + c, nr * w + nc)

    ans = 0
    black_dict = dict()
    for r, c in black_list:  # それぞれの黒マスに対して
        z = uf.root(r * w + c)  # 根を求める
        if z in black_dict:  # それぞれの木に何個黒マスがあるか
            black_dict[z] += 1
        else:
            black_dict[z] = 1

    for index, size in enumerate(uf.parents):
        if size < 0:  # それぞれの木に対して
            if index not in black_dict:  # 黒マス0コは無視
                continue
            ans += black_dict[index] * (- size - black_dict[index])  # 黒マス x 白マス

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1 for _ in range(n)]  # 各要素の親 自分が根の場合は -1 * (木の要素数)

    def root(self, x):  # xが属する木の根を返す
        if self.parents[x] < 0:  # 自分が根の場合
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def merge(self, x, y):  # xが属する木とyが属する木を合体する
        x_root = self.root(x)  # xの根
        y_root = self.root(y)  # yの根

        if x_root == y_root:  # 同じ木に属する
            return

        if self.parents[x_root] > self.parents[y_root]:  # x_rootの要素数 > y_rootの要素数 にする
            x_root, y_root = y_root, x_root

        self.parents[x_root] += self.parents[y_root]
        self.parents[y_root] = x_root


def main():
    h, w = map(int, input().split())
    grid = [list(input()) for _ in range(h)]
    black_list = []
    uf = UnionFind(h * w)

    for r in range(h):
        for c in range(w):
            if grid[r][c] == "#":
                black_list.append([r, c])
            for dr, dc in [[0, 1], [1, 0]]:
                nr = r + dr
                nc = c + dc
                if not (0 <= nr < h and 0 <= nc < w):
                    continue
                if grid[r][c] != grid[nr][nc]:
                    uf.merge(r * w + c, nr * w + nc)

    ans = 0
    black_dict = dict()
    for r, c in black_list:
        z = uf.root(r * w + c)
        if z in black_dict:
            black_dict[z] += 1
        else:
            black_dict[z] = 1

    for index, num in enumerate(uf.parents):
        if num < 0:
            if index not in black_dict:
                continue
            ans += black_dict[index] * (- num - black_dict[index])

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
MOD = 10**9+7

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

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

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

start = []
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            start.append((i,j))

not_visited = [[-1]*W for i in range(H)]
def distance(i,j):
    not_visited[i][j] = 0
    stack = deque()
    stack.append((i,j,"#"))

    b,w = 1,0

    while stack != deque([]):
        y,x,mark = stack.popleft()
        for i in range(4):
            if 0<= x+dx[i] <W and 0<= y+dy[i] <H and mark != S[y+dy[i]][x+dx[i]]  and not_visited[y+dy[i]][x+dx[i]] == -1:
                not_visited[y+dy[i]][x+dx[i]] =  not_visited[y][x] + 1
                if mark == "#":
                    stack.append((y+dy[i],x+dx[i],"."))
                    w += 1
                else:
                    stack.append((y+dy[i],x+dx[i],"#"))
                    b += 1
    
    return b*w

ans = 0
for i in range(H):
    for j in range(W):
        if not_visited[i][j] == -1 and S[i][j] == "#":
            ans += distance(i,j)
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

h,w = map(int,readline().split())
s = read().split()
color = [[0] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if(s[i][j] =='#'):
            color[i][j] = 1

ans = 0
done = [[0] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if(done[i][j]==1):
            continue

        cnt = [0]*2
        cnt[(i+j)%2] += 1
        done[i][j] = 1
        stack = [(i,j)]
        while(stack):
            x,y = stack.pop()
            for dx,dy in zip([-1,1,0,0],[0,0,-1,1]):
                dx += x
                dy += y
                if(0 <= dx < h)&(0 <= dy < w):
                    if(done[dx][dy] == 1):
                        continue
                    if(color[x][y] != color[dx][dy]):
                        done[dx][dy] = 1
                        stack.append((dx,dy))
                        cnt[(dx+dy)%2] += 1
        ans += cnt[0] * cnt[1]
        # print(i,j,cnt)

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)


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

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    H, W = [int(x) for x in input().strip().split()]
    M = [0] * (H+2)
    M[0] = ['x'] * (W+2)
    M[-1] = ['x'] * (W+2)
    for h in range(H):
        M[h+1] = ['x'] + list(input().strip()) + ['x']

    dhdw = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    ans = 0
    for i in range(1, H+1):
        for j in range(1, W+1):
            if M[i][j] == 'x':
                continue
            cnt = {'.':0, '#':0}
            q = [(i, j, M[i][j])]
            cnt[M[i][j]] = 1
            M[i][j] = 'x'
            while q:
                h, w, m = q.pop()
                # print(h, w)
                # for h_ in range(H+2):
                #     print(M[h_])
                for dh, dw in dhdw:
                    if M[h+dh][w+dw] != 'x' and m != M[h+dh][w+dw]:
                        cnt[M[h+dh][w+dw]] += 1
                        q.append((h+dh, w+dw, M[h+dh][w+dw]))
                        M[h+dh][w+dw] = 'x'
            # for h_ in range(H+2):
            #     print(M[h_])
            # print(cnt['.']*cnt['#'])
            ans += cnt['.']*cnt['#']
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
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: Accepted

Solution code:
from collections import deque
H,W=map(int,input().split())
S=["*"*(W+2) for _ in range(H+2)]
for i in range(1,H+1):
    S[i]="*"+input()+"*"

K=0
T=[[0]*(W+2) for _ in range(H+2)]
Neighborhood=[(0,1),(0,-1),(1,0),(-1,0)]
p=0

for y in range(1,H+1):
    for x in range(1,W+1):
        if T[y][x]==0:
            p+=1

            if S[y][x]=="#":
                Black,White=1,0
            elif S[y][x]==".":
                Black,White=0,1

            Q=deque([(x,y)])
            T[y][x]=p

            while Q:
                (u,v)=Q.popleft()
                for (a,b) in Neighborhood:
                    if S[v][u]=="#" and S[v+b][u+a]=="." and T[v+b][u+a]==0:
                        Q.append((u+a,v+b))
                        White+=1
                        T[v+b][u+a]=p
                    elif S[v][u]=="." and S[v+b][u+a]=="#" and T[v+b][u+a]==0:
                        Q.append((u+a,v+b))
                        Black+=1
                        T[v+b][u+a]=p

            K+=Black*White
print(K)

Submission status: Accepted

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

ans = 0

done = [[0]*W for _ in range(H)]
for sy in range(H):
    for sx in range(W):
        if done[sy][sx]:
            continue
        # 初期状態
        q = deque()
        q.append([sy,sx])
        done[sy][sx] = 1
        n_white = 0
        n_black = 0
        if grid[sy][sx] == '.':
            n_white += 1
        else:
            n_black += 1

        while q:
            y,x = q.popleft()
            for new_y, new_x in [[y+1,x],[y,x+1],[y-1,x],[y,x-1]]:
                if 0<= new_y < H and 0<= new_x < W and not done[new_y][new_x]:
                    if grid[y][x] != grid[new_y][new_x]:
                        # 色ごとの数更新
                        if grid[new_y][new_x] == '.':
                            n_white += 1
                        else:
                            n_black += 1
                        
                        done[new_y][new_x] = 1
                        q.append([new_y,new_x])
        ans += n_black*n_white
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)
def dfs(x,y):
  vis[x][y]=1
  now=s[x][y]
  b=now=='#'
  w=now=='.'
  for i in range(4):
    nx=x+dx[i]
    ny=y+dy[i]
    if not(0<=nx<r and 0<=ny<c) or vis[nx][ny] or s[nx][ny]==now:continue
    black,white=dfs(nx,ny)
    b+=black
    w+=white
  return b,w
r,c=map(int,input().split())
s=[input() for _ in range(r)]
vis=[[0]*c for _ in range(r)]
ans=0
dx=(-1,0,1,0)
dy=(0,-1,0,1)
for i in range(r):
  for j in range(c):
    if vis[i][j]:continue
    b,w=dfs(i,j)
    ans+=b*w
print(ans)

Submission status: Accepted

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

H,W=list(map(int,input().split()))
s = [ input().rstrip() for _ in range(H)]
dp = [[0]*W for _ in range(H)]

def isOK(start):
    q =  collections.deque([start])
    dp[start[0]][start[1]] = 1
    black,white=0,0
    while q:
        nowh,noww = q.popleft()
        if s[nowh][noww] == '.':
            target_mark = '#'
            white +=1
        else:
            target_mark = '.'
            black +=1
        if nowh >0 and s[nowh-1][noww] == target_mark and dp[nowh-1][noww]==0:
            q.append((nowh-1,noww))
            dp[nowh-1][noww]=1
        if nowh <H-1 and s[nowh+1][noww] == target_mark and dp[nowh+1][noww]==0:
            q.append((nowh+1,noww))
            dp[nowh+1][noww]=1
        if noww > 0 and s[nowh][noww-1] == target_mark and dp[nowh][noww-1]==0:
            q.append((nowh,noww-1))
            dp[nowh][noww-1]=1
        if noww < W-1 and s[nowh][noww+1] == target_mark and dp[nowh][noww+1]==0:
            q.append((nowh,noww+1))
            dp[nowh][noww+1]=1
            
    return black*white

cnt = 0

start_candi = []
end_candi = []
for ih in range(H):
    for iw in range(W):
        if s[ih][iw] == '#':
            start_candi.append((ih,iw))
        else:
            end_candi.append((ih,iw))

for ih in range(H):
    for iw in range(W):
        if dp[ih][iw] == 0:
            start = (ih,iw)
            cnt += isOK(start)
        else:
            continue

print(cnt)

Submission status: Accepted

Solution code:
def root(x):
    i,j = x[0],x[1]
    if (i,j) == p[i][j]:
        return (i,j)
    y = root(p[i][j])
    p[i][j]=y
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    pxi,pxj= px[0],px[1];pyi,pyj= py[0],py[1];
    rx = rank[pxi][pxj]; ry = rank[pyi][pyj]
    if ry < rx:
        p[pyi][pyj] = px
    elif rx < ry:
        p[pxi][pxj] = py
    else:
        p[pyi][pyj] = px
        rank[pxi][pxj] += 1
    return 1

h,w = map(int, input().split( ))
s = ["x"*(w+2)]+["x"+input()+"x" for _ in range(h)]+["x"*(w+2)]
p = [[(i,j) for j in range(w+2)] for i in range(h+2)]
rank = [[1]*(w+2) for _ in range(h+2)]

tonari = [(-1,0),(1,0),(0,1),(0,-1)]
for i in range(1,h+1):
    for j in range(1,w+1):
        for di,dj in tonari:
            i2 = i+di;j2 = j+dj
            if (s[i][j],s[i2][j2])==("#",".") or (s[i][j],s[i2][j2])==(".","#") :
                unite((i,j),(i2,j2))
c = [[p[i][j] for j in range(1,w+1)] for i in range(1,h+1)]
ans = 0
####
for i in range(h+2):
    for j in range(w+2):
        root((i,j))
pb = {}
pw = {}
##pb,pwの引数はroot とる
for i in range(h):
    for j in range(w):
        k = c[i][j]
        if s[i+1][j+1] =="#":
            if root(k) in pb:
                pb[root(k)]+=1
            else:
                pb[root(k)]=1
        elif s[i+1][j+1]==".":
            if root(k) in pw:
                pw[root(k)]+=1
            else:
                pw[root(k)]=1
ans = 0
c2 =  set([p[i][j] for j in range(w+2) for i in range(h+2)])

for k in c2:
    if k in pb and k in pw:
        ans += pb[k]*pw[k]
print(ans)

Submission status: Accepted

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
  visited=[[False]*w for _ in range(h)]
  for i in range(h):
    for j in range(w):
      if visited[i][j]:
        continue
      if field[i][j]!='#':
        continue
      q=collections.deque()
      q.append((i,j))
      b=0
      wh=0
      while q:
        y,x=q.popleft()
        if visited[y][x]:
          continue
        if field[y][x]=='#':
          b+=1
        else:
          wh+=1
        visited[y][x]=True
        for dy,dx in dd:
          ny=y+dy
          nx=x+dx
          if not (0<=ny<h and 0<=nx<w):
            continue
          if field[y][x]==field[ny][nx]:
            continue
          if visited[ny][nx]:
            continue
          q.append((ny,nx))
      ans+=b*wh
      # print(i,j,b,wh,ans)
  return ans

# main()
print(main())

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    H, W = LI()
    S = [SS() for _ in range(H)]

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

    def dfs(cy, cx, cnt):
        visited[cy][cx] = True
        if S[cy][cx] == '#':
            cnt[0] += 1
        else:
            cnt[1] += 1
        for dy, dx in d:
            ny = cy + dy
            nx = cx + dx
            if 0 <= ny < H and 0 <= nx < W and not visited[ny][nx] and S[ny][nx] != S[cy][cx]:
                dfs(ny, nx, cnt)

    # (黒マス数, 白マス数)
    c = []
    visited = [[False] * W for _ in range(H)]
    for i, j in itertools.product(range(H), range(W)):
        if not visited[i][j]:
            cnt = [0, 0]
            dfs(i, j, cnt)
            c.append(cnt)

    ans = sum([b * w for b, w in c])
    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import networkx as nx

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

G = nx.Graph()
G.add_nodes_from([(h, w) for h in range(H) for w in range(W)])
for h in range(H - 1):
    for w in range(W):
        if S[h][w] != S[h + 1][w]:
            G.add_edge((h, w), (h + 1, w))
for h in range(H):
    for w in range(W - 1):
        if S[h][w] != S[h][w + 1]:
            G.add_edge((h, w), (h, w + 1))

ans = 0
for component in nx.connected_components(G):
    black, white = 0, 0
    for h, w in component:
        if S[h][w] == '#':
            black += 1
        else:
            white += 1
    ans += black * white
print(ans)

Submission status: Accepted

Solution code:
def I(): return int(input())
def MI(): return map(int, input().split())
def SI(): return input().rstrip()
from collections import defaultdict

#https://note.nkmk.me/python-union-find/

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

h,w=MI()
uf=UnionFind(h*w)
lis=[[0]*w for i in range(h)]
for i in range(h):
    s=SI()
    for j in range(w):
        if s[j]=="#":
            lis[i][j]=1
step=[[0,1],[0,-1],[-1,0],[1,0]]
for i in range(h):
    for j in range(w):
        for x,y in step:
            if not (0<=i+x<h and 0<=j+y<w):
                continue
            if lis[i][j]!=lis[i+x][j+y]:
                uf.union(w*i+j,w*(i+x)+(j+y))
ans=0
dic=defaultdict(lambda:[0,0])
for i in range(h):
    for j in range(w):
        dic[uf.find(w*i+j)][lis[i][j]==1]+=1
for p in dic.keys():
    ans+=dic[p][0]*dic[p][1]
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input().rstrip())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7
    
    #https://note.nkmk.me/python-union-find/
    
    class UnionFind():
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n
    
        def find(self, x):
            if self.parents[x] < 0:
                return x
            else:
                self.parents[x] = self.find(self.parents[x])
                return self.parents[x]
    
        def union(self, x, y):
            x = self.find(x)
            y = self.find(y)
    
            if x == y:
                return
    
            if self.parents[x] > self.parents[y]:
                x, y = y, x
    
            self.parents[x] += self.parents[y]
            self.parents[y] = x
    
        def size(self, x):
            return -self.parents[self.find(x)]
    
        def same(self, x, y):
            return self.find(x) == self.find(y)
    
        def members(self, x):
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]
    
        def roots(self):
            return [i for i, x in enumerate(self.parents) if x < 0]
    
        def group_count(self):
            return len(self.roots())
    
        def all_group_members(self):
            return {r: self.members(r) for r in self.roots()}
    
        def __str__(self):
            return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    
    h,w=MI()
    uf=UnionFind(h*w)
    lis=[[0]*w for i in range(h)]
    for i in range(h):
        s=SI()
        for j in range(w):
            if s[j]=="#":
                lis[i][j]=1
    step=[[0,1],[0,-1],[-1,0],[1,0]]
    for i in range(h):
        for j in range(w):
            for x,y in step:
                if not (0<=i+x<h and 0<=j+y<w):
                    continue
                if lis[i][j]!=lis[i+x][j+y]:
                    uf.union(w*i+j,w*(i+x)+(j+y))
    ans=0
    dic=defaultdict(lambda:[0,0])
    for i in range(h):
        for j in range(w):
            dic[uf.find(w*i+j)][lis[i][j]==1]+=1
    for p in dic.keys():
        ans+=dic[p][0]*dic[p][1]
    print(ans)
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict


class UnionFind:
    def __init__(self, node):
        self.parent = [-1 for _ in range(node)]
        self.node = node

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

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

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

    def get_size(self, x):
        return -self.parent[self.find(x)]

    def get_root(self):
        return [i for i, root in enumerate(self.parent) if root < 0]

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

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


def main():
    h, w = map(int, input().split())
    grid = [["*" for _ in range(w + 2)]]
    for _ in range(h):
        grid.append(["*"] + list(input()) + ["*"])
    grid.append(grid[0])
    uf = UnionFind(h * w)
    all_black = []

    def grid_num(i, j):
        return w * (i - 1) + j - 1

    for i in range(1, h + 1):
        for j in range(1, w + 1):
            for di, dj in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
                ni = i + di
                nj = j + dj
                if grid[ni][nj] == "*":
                    continue
                elif grid[i][j] != grid[ni][nj]:
                    uf.union(grid_num(i, j), grid_num(ni, nj))
            if grid[i][j] == "#":
                all_black.append([i, j])
    ans = 0

    black = defaultdict(int)
    for i, j in all_black:
        black[uf.find(grid_num(i, j))] += 1
    for i, r in enumerate(uf.parent):
        if r < 0:
            ans += black[i] * (-r - black[i])
    print(ans)


if __name__ == '__main__':
    main()