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:
H, W = map(int, input().split())
m = [input() for i in range(H)]
ans = 0

import sys
sys.setrecursionlimit(10**6)

class UnionFind():
  def __init__(self, n):
    self.par = [i for i in range(n)]

  def root(self, x):
    if self.par[x] == x:
      return x
    else:
      self.par[x] = self.root(self.par[x])
      return self.par[x]
  
  def unite(self, x, y):
    x = self.root(x)
    y = self.root(y)
    self.par[y] = x

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

uf = UnionFind(H*W)

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

ansb = {}
answ = {}
for i in range(H*W):
  ir = uf.root(i)
  h, w = divmod(i, W)
  if m[h][w] == "#":
    ansb[ir] = ansb.get(ir, 0) + 1
  else:
    answ[ir] = answ.get(ir, 0) + 1


ans = 0
for k, vb in ansb.items():
  vw = answ.get(k, 0)
  ans += vb * vw

print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
grid =[list(input()) for i in range(h)]
visited=[[False]*w for i in range(h)]
ans=0
for i in range(h):
  for j in range(w):
    if visited[i][j]:
      continue
    q=[(i,j)]
    d={'#':0,'.':0}
    while q:
      cy,cx=q.pop(0)
      for ny,nx in ((cy+1,cx),(cy-1,cx),(cy,cx+1),(cy,cx-1)):
        if not(0<=ny<h and 0<=nx<w) or grid[cy][cx]==grid[ny][nx] or visited[ny][nx]:
          continue
        d[grid[ny][nx]]+=1
        visited[ny][nx]=True
        q.append((ny,nx))
    ans+=d['.']*d['#']
print(ans)

Submission status: Accepted

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

count=0
count2=0
visited=set()
for h1 in range(H):
    for w1 in range(W):
        if S[h1][w1]=="#" and checked[h1][w1]==0:
            checked[h1][w1]=1
            stack=deque([[h1,w1,"#"]])
            kuro=1
            siro=0
            count2+=1
            visited.add(h1*400+w1)
            while stack:
                h,w,iro=stack.popleft()
                for y,x in [[-1,0],[1,0],[0,1],[0,-1]]:
                    Y,X=y+h,x+w
                    visitednum=Y*400+X
                    if 0<=Y<H and 0<=X<W and not visitednum in visited:
                        if iro=="#" and S[Y][X]==".":
                            siro+=1
                            visited.add(visitednum)
                            stack.append([Y,X,"."])
                        elif iro=="." and S[Y][X]=="#" and not visitednum in visited:
                            kuro+=1
                            checked[Y][X]=1
                            visited.add(visitednum)
                            stack.append([Y,X,"#"])
            count+=kuro*siro
print(count)

Submission status: Accepted

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

count=0
count2=0
for h1 in range(H):
    for w1 in range(W):
        if S[h1][w1]=="#" and checked[h1][w1]==0:
            checked[h1][w1]=1
            stack=deque([[h1,w1,"#"]])
            kuro=1
            siro=0
            count2+=1
            visited=set([h1*400+w1])
            while stack:
                h,w,iro=stack.popleft()
                for y,x in [[-1,0],[1,0],[0,1],[0,-1]]:
                    Y,X=y+h,x+w
                    visitednum=Y*400+X
                    if 0<=Y<H and 0<=X<W and not visitednum in visited:
                        if iro=="#" and S[Y][X]==".":
                            siro+=1
                            visited.add(visitednum)
                            stack.append([Y,X,"."])
                        elif iro=="." and S[Y][X]=="#" and not visitednum in visited:
                            kuro+=1
                            checked[Y][X]=1
                            visited.add(visitednum)
                            stack.append([Y,X,"#"])
            count+=kuro*siro
print(count)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
S = [[1 if i=="#" else 0 for i in input()] for _ in range(h)]
dy = (1, 0, -1, 0)
dx = (0, 1, 0, -1)
seen = [[False]*w for _ in range(h)]

def dfs(y, x):
  white = 0
  black = 0
  stack = [(y, x)]
  seen[y][x] = True
  while stack:
    s, t = stack.pop()
    if S[s][t]:
      black += 1
    else:
      white += 1
    for di, dj in zip(dy, dx):
      ny, nx = s+di, t+dj
      if 0 <= ny < h and 0 <= nx < w:
        if seen[ny][nx]:
          continue
        if S[s][t] ^ S[ny][nx]:
          seen[ny][nx] = True
          stack.append((ny, nx))
  return black, white

ans = 0
for i in range(h):
  for j in range(w):
    if not seen[i][j]:
      black, white = dfs(i, j)
      ans += black * white
print(ans)

Submission status: Accepted

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

h,w = map(int,input().split())

sl = []

for _ in range(h):
    s = list(input())
    sl.append(s)

used = [-1 for i in range(h*w)]
def dfs(i, j):
    used[i] = j
    if i % w + 1 < w:
        if sl[i//w][i%w] != sl[i//w][i%w+1]:
            if used[i+1] == -1:
                dfs(i + 1, j)
    if i % w - 1 >= 0:
        if sl[i//w][i%w] != sl[i//w][i%w-1]:
            if used[i-1] == -1:
                dfs(i - 1, j)
    if i // w + 1 < h:
        if sl[i // w][i % w] != sl[i // w+1][i % w]:
            if used[i+w] == -1:
                dfs(i + w, j)
    if i // w - 1 >= 0:
        if sl[i // w][i % w] != sl[i // w-1][i % w]:
            if used[i-w] == -1:
                dfs(i -w, j)

while True:
    if min(used) >= 0:
        break
    for i, j in enumerate(used):
        if j == -1:
            dfs(i, i)

from collections import defaultdict
dic = defaultdict(list)

for i, j in enumerate(used):
    dic[j].append(i)

ans = 0
for group in dic.values():
    a = 0
    b = 0
    for p in group:
        i = p // w
        j = p % w
        if sl[i][j] == "#":
            a += 1
        else:
            b += 1
    ans += a*b
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

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

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

ans = 0
for i in range(H):
    for j in range(W):
        if visited[i][j]:
            continue
        else:
            whites = 0
            blacks = 0
            p = [(i,j)]
            while p:
                now = p.pop()
                if S[now[0]][now[1]]=='#':
                    blacks += 1
                else:
                    whites += 1
                visited[now[0]][now[1]] = True
                for d0 in d:
                    new = (now[0]+d0[0],now[1]+d0[1])
                    if 0<=new[0]<=H-1 and 0<=new[1]<=W-1:
                        if S[now[0]][now[1]]!=S[new[0]][new[1]] and (not visited[new[0]][new[1]]):
                            p.append(new)
                            visited[new[0]][new[1]] = True
            ans += whites*blacks
print(ans)

Submission status: Accepted

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

used=[[False for _ in range(W)] for __ in range(H)]
def dfs(sx,sy):
    global used
    if used[sy][sx]: return (0,0)
    black=white=0
    stack=[(sx,sy)]
    used[sy][sx]=True
    while stack:
        x,y=stack.pop()
        if M[y][x]=='#':
            black+=1
        else:
            white+=1
        for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:
            nx,ny=x+dx,y+dy
            if 0<=nx<W and 0<=ny<H and not used[ny][nx]:
                if M[y][x]!=M[ny][nx]:
                    stack.append((nx,ny))
                    used[ny][nx]=True
    return (black,white)

ans=0
for y in range(H):
    for x in range(W):
        black,white=dfs(x,y)
        ans+=black*white
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read

H, W = map(int, input().split())
S = tuple(map(str, read().split()))
udlr = ((1, 0), (-1, 0), (0, 1), (0, -1))

visited = [[False] * W for i in range(H)]
answer = 0
for i in range(H):
    for j in range(W):
        if visited[i][j] or S[i][j] == '.':
            continue

        visited[i][j] = True
        queue = deque([(i, j)])
        black = 1
        white = 0

        while queue:
            x, y = queue.popleft()
            if S[x][y] == '#':
                switch = 'Black'
            else:
                switch = 'White'

            for di, dj in udlr:
                new_i = x + di
                new_j = y + dj
                if 0 <= new_i < H and 0 <= new_j < W:
                    if visited[new_i][new_j]:
                        continue

                    if switch == 'Black':
                        if S[new_i][new_j] == '.':
                            white += 1
                            queue.append((new_i, new_j))
                            visited[new_i][new_j] = True
                    else:
                        if S[new_i][new_j] == '#':
                            black += 1
                            queue.append((new_i, new_j))
                            visited[new_i][new_j] = True
        answer += black * white

print(answer)

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read

H, W = map(int, input().split())
S = tuple(map(str, read().split()))
udlr = ((1, 0), (-1, 0), (0, 1), (0, -1))

visited = [[False] * W for i in range(H)]
answer = 0
for i in range(H):
    for j in range(W):
        if visited[i][j] or S[i][j] == '.':
            continue

        visited[i][j] = True
        queue = deque([(i, j)])
        black = 1
        white = 0

        while queue:
            x, y = queue.popleft()
            if S[x][y] == '#':
                switch = 'Black'
            else:
                switch = 'White'

            for di, dj in udlr:
                new_i = x + di
                new_j = y + dj
                if 0 <= new_i < H and 0 <= new_j < W:
                    if visited[new_i][new_j]:
                        continue

                    if switch == 'Black':
                        if S[new_i][new_j] == '.':
                            white += 1
                            queue.append((new_i, new_j))
                            visited[new_i][new_j] = True
                    else:
                        if S[new_i][new_j] == '#':
                            black += 1
                            queue.append((new_i, new_j))
                            visited[new_i][new_j] = True
            if switch == 'Black':
                switch = 'White'
            else:
                switch = 'Black'
        answer += black * white

print(answer)

Submission status: Accepted

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

def dfs(i, j):
    visited[i][j] = True
    res_b = 0
    res_w = 0
    if N[i][j]:
        res_b += 1
    else:
        res_w += 1
    for di, dj in d:
        if i + di < 0 or i + di >= H or j + dj < 0 or j + dj >= W:
            continue
        if N[i][j] == N[i+di][j+dj]:
            continue
        if visited[i+di][j+dj]:
            continue
        tmp_b, tmp_w = dfs(i + di, j + dj)
        res_b += tmp_b
        res_w += tmp_w
    return res_b, res_w

H, W = map(int, input().split())
N = [[False] * W for _ in range(H)]
for i in range(H):
    s = input()
    for j in range(W):
        N[i][j] = (s[j] == "#")

d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
visited = [[False] * W for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if not N[i][j]:
            continue
        if visited[i][j]:
            continue
        b, w = dfs(i, j)
        ans += (b * w)

print(ans)

Submission status: Accepted

Solution code:
def main():
    from functools import reduce
    from operator import mul
    import sys

    sys.setrecursionlimit(10 ** 7)

    def dfs(sr, sc):
        d = {'.': 0, '#': 0}
        q = [(sr, sc)]
        while q:
            r, c = q.pop()
            if checked[r][c]:
                continue
            checked[r][c] = True
            d[s[r][c]] += 1

            if r - 1 >= 0 and s[r - 1][c] != s[r][c]:
                q.append((r - 1, c))

            if c - 1 >= 0 and s[r][c - 1] != s[r][c]:
                q.append((r, c - 1))

            if r + 1 < h and s[r + 1][c] != s[r][c]:
                q.append((r + 1, c))

            if c + 1 < w and s[r][c + 1] != s[r][c]:
                q.append((r, c + 1))

        return d

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

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

    ret = 0
    for r in range(h):
        for c in range(w):
            if checked[r][c]:
                continue
            ret += reduce(mul, dfs(r, c).values())

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind():
    n=1
    par=[0]
    rnk=[0]
    def __init__(self,size):
        self.n=size
        self.par=[i for i in range(self.n)]
        self.rnk=[0 for i in range(self.n)]
    def find(self,vertex1):
        if self.par[vertex1]==vertex1:
            return vertex1
        else:
            self.par[vertex1]=self.find(self.par[vertex1])
            return self.par[vertex1]
    def unite(self,vertex1,vertex2):
        vertex1=self.find(vertex1)
        vertex2=self.find(vertex2)
        if vertex1==vertex2:
            return
        if (self.rnk[vertex1]<self.rnk[vertex2]):
            self.par[vertex1]=vertex2
        else:
            self.par[vertex2]=vertex1
            if(self.rnk[vertex1]==self.rnk[vertex2]):
                self.rnk[vertex1]+=1
    def same(self,vetrex1,vertex2):
        return self.find(vetrex1)==self.find(vertex2)
H,W=map(int,input().split())
S=[list(input()) for i in range(H)]
G=UnionFind(H*W)
#i*W+j
for i in range(H):
    for j in range(W-1):
        if S[i][j]!=S[i][j+1]:
            G.unite(i*W+j,i*W+(j+1))
for i in range(H-1):
    for j in range(W):
        if S[i][j]!=S[i+1][j]:
            G.unite(i*W+j,(i+1)*W+j)
D=dict()
for i in range(H):
    for j in range(W):
        k=G.find(i*W+j)
        if not k in D:
            D[k]=[0,0]
        if S[i][j]=="#":
            D[k][0]+=1
        else:
            D[k][1]+=1
ans=0
for k in D:
    x=D[k][0]
    y=D[k][1]
    ans+=x*y
print(ans)

Submission status: Accepted

Solution code:
dxdy = [(0, 1), (0, -1), (1, 0), (-1, 0)]
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
for i in range(h):
    for j in range(w):
        if (i + j) % 2:
            if s[i][j] == '.':
                s[i][j] = '#'
            else:
                s[i][j] = '.'
d = [[True] * w for _ in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if not d[i][j]:
            continue
        d[i][j] = False
        st = [(i, j)]
        b, wh = 0, 0
        while st:
            y, x = st.pop()
            if (x + y) % 2:
                b += 1
            else:
                wh += 1
            for dx, dy in dxdy:
                if 0 <= x + dx < w and 0 <= y + dy < h and d[y + dy][x + dx] and s[y][x] == s[y + dy][x + dx]:
                    st.append((y + dy, x + dx))
                    d[y + dy][x + dx] = False
        ans += b * wh
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))


h,w = inpl()
s = [input() for i in range(h)]
d = dict()
ld = dict()
i = 0
dx = [-1,0,1,0]
dy = [0,1,0,-1]
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())

#初期化
uf = UnionFind(h*w)
for y in range(h):
    for x in range(w):
        if s[y][x] == '.':
            d[(y,x)] = i
            i += 1
for y in range(h):
    for x in range(w):
        if s[y][x] == '.':
            continue
        l = []
        for dir in range(4):
            nx = x+dx[dir]; ny = y+dy[dir]
            if nx<0 or nx>=w or ny<0 or ny>=h:
                continue
            if s[ny][nx] == '#':
                continue
            if l == []:
                ld[(y,x)] = d[(ny,nx)]
            l.append(d[(ny,nx)])            
            uf.union(l[0],d[(ny,nx)])

# print(ld)
res = 0
for key,value in ld.items():
    res += uf.size(value)
print(res)

Submission status: Accepted

Solution code:
import collections
h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
group = [[-1 for _ in range(w)] for _ in range(h)]
group_positions = []
for h_i in range(h):
    for w_i in range(w):
      if maze[h_i][w_i] == ".":
        maze[h_i][w_i] = 0
      else:
        maze[h_i][w_i] = 1
      
def do_append(point, y_diff, x_diff):
  new_x = point[1] + x_diff
  new_y = point[0] + y_diff
  new_color = ((point[2]+1)%2)
  if new_x == -1 or new_x == w or new_y == -1 or new_y == h or new_color != maze[new_y][new_x]:
    return False, False
  elif group[new_y][new_x] != -1:
    return False, False
  else:
    return True, (new_y, new_x, new_color)

def wfs(pos, group_num):
  y_pos = pos[0]
  x_pos = pos[1]
  color = maze[y_pos][x_pos] # 0 white 1 black
  group_positions.append([(y_pos, x_pos, color)])
  
  que = collections.deque()
  que.append((y_pos, x_pos, color))
  group[y_pos][x_pos] = group_num
  while len(que) > 0:
    point = que.popleft()
    for dy in (-1, 0, 1):
      for dx in (-1, 0 , 1):
        if dx * dy != 0:
          continue
        result, new_point = do_append(point, dy, dx)
        if result:
          group[new_point[0]][new_point[1]] = group_num
          group_positions[group_num].append(new_point)
          que.append(new_point)
      
if __name__ == "__main__":
  count = 0
  group_num = 0
  for h_i in range(h):
    for w_i in range(w):
      if group[h_i][w_i] == -1:
        pos = (h_i, w_i)
        wfs(pos, group_num)
        group_num += 1
  
  for g in group_positions:
    black_num = 0
    white_num = 0
    for point in g:
      if point[2] == 0:
        white_num += 1
      else:
        black_num += 1
    count += white_num * black_num
  print(count)

Submission status: Accepted

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

dxdy = {(-1, 0), (1, 0), (0, -1), (0, 1)}

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

ans = 0

for i in range(h):
    for j in range(w):
        if ch[i][j] == 0:
            black,white = 0,0
            q = [(i,j)]
            while q:
                y,x = q.pop()
                if ch[y][x] == 0:
                    if s[y][x] == "#":black += 1
                    else:white += 1
                    ch[y][x] = 1
                    for dx,dy in dxdy:
                        if 0 <= x + dx < w and 0 <= y + dy < h and ch[y+dy][x+dx] == 0 and s[y+dy][x+dx] != s[y][x]:
                            q.append((y+dy,x+dx))
            ans += black * white

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

dxdy = {(-1, 0), (1, 0), (0, -1), (0, 1)}

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

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

ans = 0

for i in range(h):
    for j in range(w):
        if ch[i][j] == 0:
            black,white = 0,0
            q = [(i,j)]
            while q:
                y,x = q.pop()
                if ch[y][x] == 0:
                    if s[y][x] == "#":black += 1
                    else:white += 1
                    ch[y][x] = 1
                    for dx,dy in dxdy:
                        if 0 <= x + dx < w and 0 <= y + dy < h and ch[y+dy][x+dx] == 0 and s[y+dy][x+dx] != s[y][x]:
                            q.append((y+dy,x+dx))
            ans += black * white

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
H, W = map(int, input().split())
s = [input() for _ in range(H)]
visited = [[0]*W for _ in range(H)]
ans = 0

for y, x in product(range(H), range(W)):
    if visited[y][x]:
        continue
    visited[y][x] = 1
    w, b = 0, 0
    if s[y][x] == '#':
        b += 1
    else:
        w += 1
    stack = [(y, x)]

    while stack:
        cy, cx = stack.pop()
        for dy, dx in ((cy+1, cx), (cy-1, cx), (cy, cx+1), (cy, cx-1)):
            if not (0 <= dy < H and 0 <= dx < W) or visited[dy][dx] or s[cy][cx] == s[dy][dx]:
                continue
            visited[dy][dx] = 1
            if s[dy][dx] == '#':
                b += 1
            else:
                w += 1
            stack.append((dy, dx))

    ans += w * b

print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10 ** 7)
    input = sys.stdin.readline

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

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

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

    def dfs(r, c):
        sharp, dot = 0, 0
        if s[r][c] == '#':
            sharp = 1
        else:
            dot = 1

        for dr, dc in d:
            nr = r + dr
            if nr < 0 or h <= nr:
                continue
            nc = c + dc
            if nc < 0 or w <= nc:
                continue
            if s[nr][nc] == s[r][c]:
                continue
            if checked[nr][nc]:
                continue
            checked[nr][nc] = True

            res_sharp, res_dot = dfs(nr, nc)
            sharp += res_sharp
            dot += res_dot

        return sharp, dot

    ret = 0
    for r in range(h):
        for c in range(w):
            if checked[r][c]:
                continue
            checked[r][c] = True
            sharp, dot = dfs(r, c)
            ret += sharp * dot

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter


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

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

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

        if x == y:
            return False
        else:
            if self.v[x] > self.v[y]:
                x, y = y, x
            self.v[x] += self.v[y]
            self.v[y] = x
            return True

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

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


def main():
    import sys

    input = sys.stdin.readline

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

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

    uf = UnionFind(h * w * 2)
    for r in range(h):
        for c in range(w):
            id_ = (r * w + c) + (h * w if s[r][c] == '#' else 0)
            for dr, dc in d:
                nr = r + dr
                if nr < 0 or h <= nr:
                    continue
                nc = c + dc
                if nc < 0 or w <= nc:
                    continue
                if s[nr][nc] == s[r][c]:
                    continue
                nid = (nr * w + nc) + (h * w if s[nr][nc] == '#' else 0)
                uf.unite(id_, nid)

    for r in range(h):
        for c in range(w):
            id_ = (r * w + c) + (h * w if s[r][c] == '#' else 0)
            uf.find(id_)
            # 葉の親が更新されていなかったために、連結成分の大きさが小さく判定されていた

    checked = [False] * (h * w * 2)
    ctr_dot = Counter(uf.v[:h * w])
    ctr_sharp = Counter(uf.v[h * w:])

    ret = 0
    for r in range(h):
        for c in range(w):
            id_ = (r * w + c) + (h * w if s[r][c] == '#' else 0)
            root = uf.find(id_)

            if checked[root]:
                continue

            checked[root] = True

            dot = ctr_dot[root]
            sharp = ctr_sharp[root]

            if root < h * w:
                dot += 1
            else:
                sharp += 1

            ret += dot * sharp

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter


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

    def find(self, x):
        if self.v[x] < 0:  # (負)は根
            return x
        else:
            self.v[x] = self.find(self.v[x])
            return self.v[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if -self.v[x] < -self.v[y]:
            x, y = y, x
        self.v[x] += self.v[y]
        self.v[y] = x

    def root(self, x):
        return self.v[x] < 0

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


def main():
    import sys

    input = sys.stdin.readline

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

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

    uf = UnionFind(h * w * 2)
    for r in range(h):
        for c in range(w):
            id_ = (r * w + c) + (h * w if s[r][c] == '#' else 0)
            for dr, dc in d:
                nr = r + dr
                if nr < 0 or h <= nr:
                    continue
                nc = c + dc
                if nc < 0 or w <= nc:
                    continue
                if s[nr][nc] == s[r][c]:
                    continue
                nid = (nr * w + nc) + (h * w if s[nr][nc] == '#' else 0)
                uf.unite(id_, nid)

    for r in range(h):
        for c in range(w):
            id_ = (r * w + c) + (h * w if s[r][c] == '#' else 0)
            uf.find(id_)
            # 葉の親が更新されていなかったために、連結成分の大きさが小さく判定されていた

    checked = [False] * (h * w * 2)
    ctr_dot = Counter(uf.v[:h * w])
    ctr_sharp = Counter(uf.v[h * w:])

    ret = 0
    for r in range(h):
        for c in range(w):
            id_ = (r * w + c) + (h * w if s[r][c] == '#' else 0)
            root = uf.find(id_)

            if checked[root]:
                continue

            checked[root] = True

            dot = ctr_dot[root]
            sharp = ctr_sharp[root]

            if root < h * w:
                dot += 1
            else:
                sharp += 1

            ret += dot * sharp

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
h,w = map(int,input().split())
sq = [list(input()) for i in range(h)]
prt = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
  for j in range(w):
    c = i + j
    if sq[i][j] == "#":
      c += 1
    prt[i][j] = c%2
que = deque([])
ans = 0
visited = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
  for j in range(w):
    if visited[i][j] != 1:
      que.append((i,j))
      cnt = 0
      cntb = 0
      while que:
        x,y = que.popleft()
        if visited[x][y] != 1:
          cnt += 1
          if sq[x][y] == "#":
            cntb += 1
          visited[x][y] = 1
          for n_x,n_y in ((x+1,y),(x-1,y),(x,y+1),(x,y-1)):
            if 0<=n_x<h and 0<=n_y<w:
              if visited[n_x][n_y] != 1 and prt[n_x][n_y] == prt[x][y]:
                que.append((n_x,n_y))
      ans += cntb*(cnt-cntb)

print(ans)

Submission status: Accepted

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


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 main():
    H, W = map(int, input().split())
    S = []
    for h in range(H):
        S.append(input().strip())

    uf = UnionFind(H*W)
    for i in range(H):
        for j in range(W):
            if i < H-1 and S[i][j] != S[i+1][j]:
                uf.union(i*W+j, (i+1)*W+j)
            if j < W-1 and S[i][j] != S[i][j+1]:
                uf.union(i*W+j, i*W+(j+1))
    D = {}
    for i in range(H):
        for j in range(W):
            r = uf.find(i*W+j)
            if r not in D:
                D[r] = [0, 0]
            if S[i][j] == "#":
                D[r][0] += 1
            else:
                D[r][1] += 1
    ans = 0
    for d in D.values():
        ans += d[0]*d[1]
    print(ans)


if __name__ == '__main__':
    main()