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:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
alp = "abcdefghijklmnopqrstuvwxyz"
dir = [(-1,0),(0,-1),(1,0),(0,1)]

#UnionFindのクラス,0-indexed
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())

def main():
    h,w = map(int,ipt().split())
    brd = [input()+"-" for i in range(h)]
    brd.append("-"*(w+1))
    d = {"#":0, ".":1, "-":-4}
    al = [True]*(h*w)
    ans = 0

    for i in range(h):
        for j in range(w):
            if al[i*w+j]:
                q = [(i,j)]
                al[i*w+j] = False
                nm = [0,0]
                nm[d[brd[i][j]]] += 1
                while q:
                    qi,qj = q.pop()
                    qs = d[brd[qi][qj]]
                    for di,dj in dir:
                         ni = qi+di
                         nj = qj+dj
                         if d[brd[ni][nj]] == 1-qs and al[ni*w+nj]:
                             al[ni*w+nj] = False
                             nm[1-qs] += 1
                             q.append((ni,nj))
                ans += nm[0]*nm[1]

    print(ans)





    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w=map(int,input().split())

maze=[list(input()) for _ in range(h)]

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

group_no=0
color_cnt=[]

for y in range(h):
    for x in range(w):
        if group[y][x]==0:
            stack=[(y,x)]
            group_no+=1

            color_cnt_tmp=[0,0]

            while len(stack)>0:
                tmp=stack.pop()
                group[tmp[0]][tmp[1]]=group_no
                #print(tmp)
                if maze[tmp[0]][tmp[1]]=="#":
                    color_cnt_tmp[0]+=1
                else:
                    color_cnt_tmp[1]+=1

                for (ny,nx) in [(0,1),(1,0),(-1,0),(0,-1)]:
                    my=ny+tmp[0]
                    mx=nx+tmp[1]
                    if 0<=my<h and 0<=mx<w:
                        if group[my][mx]==0:
                            if maze[tmp[0]][tmp[1]]!=maze[my][mx]:
                                stack.append((my,mx))
                                group[my][mx]=group_no
            color_cnt.append(color_cnt_tmp)

ans=0
for (b,w) in color_cnt:
    ans+=b*w

print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import deque

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

    ans = 0
    for row in range(1, h + 1):
        for col in range(1, w + 1):
            if grid[row][col] != "!":
                black, white = 0, 0
                que = deque()
                que.append((row, col))
                while que:
                    cr, cc = que.popleft()
                    if grid[cr][cc] == "#":
                        black += 1
                        if grid[cr + 1][cc] == ".":
                            que.append((cr + 1, cc))
                        if grid[cr - 1][cc] == ".":
                            que.append((cr - 1, cc))
                        if grid[cr][cc + 1] == ".":
                            que.append((cr, cc + 1))
                        if grid[cr][cc - 1] == ".":
                            que.append((cr, cc - 1))
                    elif grid[cr][cc] == ".":
                        white += 1
                        if grid[cr + 1][cc] == "#":
                            que.append((cr + 1, cc))
                        if grid[cr - 1][cc] == "#":
                            que.append((cr - 1, cc))
                        if grid[cr][cc + 1] == "#":
                            que.append((cr, cc + 1))
                        if grid[cr][cc - 1] == "#":
                            que.append((cr, cc - 1))
                    grid[cr][cc] = "!"

                ans += white * black
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

n = h*w

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

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

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

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

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

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

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

ans = 0
#print(par)
X = [[0, 0] for _ in range(n)]
K = []

for i in range(n):
    y, x = divmod(i, w)
    if par[i] < 0:
        K.append(i)
        if S[y][x] == '#':
            X[i][0] += 1
        else:
            X[i][1] += 1
    else:
        if S[y][x] == '#':
            X[Find(i, par)][0] += 1
        else:
            X[Find(i, par)][1] += 1

ans = 0
for k in K:
    ans += X[k][0]*X[k][1]
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import collections
import bisect
import copy

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    h, w = ns()
    mat = [list(input()) for _ in range(h)]
    visited = [[False for _ in range(w)] for __ in range(h)]

    B, W = 0, 1
    for y in range(h):
        for x in range(w):
            if mat[y][x] == "#":
                mat[y][x] = B
            else:
                mat[y][x] = W

    cnt = [0, 0]
    pos = [[0, 1], [0, -1], [1, 0], [-1, 0]]

    def bfs(y, x, here):
        visited[y][x] = True
        cnt[here] += 1

        for yi, xi in pos:
            ty = y + yi
            tx = x + xi
            if 0 <= ty < h and 0 <= tx < w:
                if not visited[ty][tx] and mat[ty][tx] == here ^ 1:
                    bfs(ty, tx, here ^ 1)

    ans = 0
    for y in range(h):
        for x in range(w):
            if not visited[y][x]:
                cnt = [0, 0]
                bfs(y, x, mat[y][x])
                ans += cnt[B] * cnt[W]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

q=deque([])
T=[]
seen=[[0]*W for _ in range(H)]
step=[[0,1],[0,-1],[1,0],[-1,0]]
for h in range(H):
    for w in range(W):
        temp=[]
        if seen[h][w]==0:
            temp.append(S[h][w])
            seen[h][w]=1
            q.append([h,w,S[h][w]])
            while q:
                oh,ow,m=q.popleft()
                for dh,dw in step:
                    if 0<=oh+dh<H and 0<=ow+dw<W:
                        if seen[oh+dh][ow+dw]==0 and m!=S[oh+dh][ow+dw]:
                            temp.append(S[oh+dh][ow+dw])
                            seen[oh+dh][ow+dw]=1
                            q.append([oh+dh,ow+dw,S[oh+dh][ow+dw]])
            T.append(temp)

ans=0
for i in range(len(T)):
    black=0
    white=0
    for s in T[i]:
        if s=="#":
            black+=1
        else:
            white+=1
    ans+=black*white

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000)


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

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


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


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

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

print(ans)

Submission status: Accepted

Solution code:
#

import sys
from collections import deque
input=sys.stdin.readline

def main():
    H,W=map(int,input().split())
    masu=[input().strip("\n") for i in range(H)]
    
    di=[(-1,0), (1,0), (0,-1), (0,1)]
    dist=[[-1]*W for i in range(H)]
    ans=0
    
    for i in range(H):
        for j in range(W):
            if masu[i][j]=="#" and dist[i][j]==-1:
                bcnt=0
                wcnt=0
                qu=deque([(i,j)])
                dist[i][j]=0
                while(len(qu)>0):
                    v=qu.popleft()
                    if masu[v[0]][v[1]]=="#":
                        nex="."
                        bcnt+=1
                    else:
                        nex="#"
                        wcnt+=1
                    for d in di:
                        nv=(v[0]+d[0],v[1]+d[1])
                        if 0<=nv[0]<H and 0<=nv[1]<W and dist[nv[0]][nv[1]]==-1 and masu[nv[0]][nv[1]] == nex:
                            dist[nv[0]][nv[1]]=dist[v[0]][v[1]]+1
                            qu.append(nv)
                ans+=bcnt*wcnt
    print(ans)
    
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

s = [0]*(h+2)
for i in range(1,h+1):
    s[i] = [0] + list(input()) + [0]
s[0] = [0]*(w+2)
s[-1] = [0]*(w+2)

reach = [[-1 for j in range(w+2)] for i in range(h+2)]
lis = []

for i in range(1,h+1):
    for j in range(1,w+1):
        if reach == 0:
            pass
        else:
            black = 0
            white = 0
            if s[i][j] == "#":
                state = 1
                black += 1
            else:
                state = 0
                white += 1
                
            q = deque()
            q.append([i,j,state])
            reach[i][j] = 0
            
            while q:
                [x,y,state] = q.popleft()
                
                if reach[x-1][y] == -1:
                    if state == 0 and s[x-1][y] == "#":
                        reach[x-1][y] = 0
                        q.append([x-1, y ,1])
                        black += 1
                    elif  state == 1 and s[x-1][y] == ".":
                        reach[x-1][y] = 0
                        q.append([x-1, y ,0])
                        white += 1
                
                if reach[x+1][y] == -1:
                    if state == 0 and s[x+1][y] == "#":
                        reach[x+1][y] = 0
                        q.append([x+1, y ,1])
                        black += 1
                    elif  state == 1 and s[x+1][y] == ".":
                        reach[x+1][y] = 0
                        q.append([x+1, y ,0])
                        white += 1
                        
                if reach[x][y-1] == -1:
                    if state == 0 and s[x][y-1] == "#":
                        reach[x][y-1] = 0
                        q.append([x, y-1 ,1])
                        black += 1
                    elif  state == 1 and s[x][y-1] == ".":
                        reach[x][y-1] = 0
                        q.append([x, y-1 ,0])
                        white += 1
                    
                if reach[x][y+1] == -1:
                    if state == 0 and s[x][y+1] == "#":
                        reach[x][y+1] = 0
                        q.append([x, y+1 ,1])
                        black += 1
                    elif  state == 1 and s[x][y+1] == ".":
                        reach[x][y+1] = 0
                        q.append([x, y+1 ,0])
                        white += 1
                
            lis.append([black,white])
ans = 0
for s,t in lis:
    ans += s*t
print(ans)

Submission status: Accepted

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

def main():
  h, w = map(int, input().split())
  s = [input() for _ in range(h)]
  
  ans = 0
  already = [[False]*w for _ in range(h)]
  for i in range(h):
    for j in range(w):
      if already[i][j] or s[i][j] == ".":
        continue
      already[i][j] = True
      black, white = 0, 0
      not_yet = deque([(i, j)])
      while not_yet:
        p, q = not_yet.pop()
        if s[p][q] == "#":
          black += 1
        else:
          white += 1
        if p > 0 and s[p-1][q] != s[p][q] and not already[p-1][q]:
          not_yet.append((p-1, q))
          already[p-1][q] = True
        if p < h-1 and s[p+1][q] != s[p][q] and not already[p+1][q]:
          not_yet.append((p+1, q))
          already[p+1][q] = True
        if q > 0 and s[p][q-1] != s[p][q] and not already[p][q-1]:
          not_yet.append((p, q-1))
          already[p][q-1] = True
        if q < w-1 and s[p][q+1] != s[p][q] and not already[p][q+1]:
          not_yet.append((p, q+1))
          already[p][q+1] = True
      ans += black*white
  
  print(ans)

  
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
G=[["@"]*(w+2) for i in range(h+2)]
for i in range(1,h+1):
  G[i]=["@"]+list(input())+["@"]
V=[[0]*(w+2) for i in range(h+2)]
X=deque([])
Y=deque([])
XX=[-1,0,0,1]
YY=[0,-1,1,0]
ans=0
for i in range(h+2):
  for j in range(w+2):
    if V[i][j]==0 and G[i][j]=="#":
      X.append(i)
      Y.append(j)
      V[i][j]=1
      C=[1,0]
      while len(X)>0:
        x=X[0]
        y=Y[0]
        X.popleft()
        Y.popleft()
        if G[x][y]=="#":
          for k in range(4):
            if V[x+XX[k]][y+YY[k]]==0 and G[x+XX[k]][y+YY[k]]==".":
              X.append(x+XX[k])
              Y.append(y+YY[k])
              V[x+XX[k]][y+YY[k]]=1
              C[1]+=1
        else:
          for k in range(4):
            if V[x+XX[k]][y+YY[k]]==0 and G[x+XX[k]][y+YY[k]]=="#":
              X.append(x+XX[k])
              Y.append(y+YY[k])
              V[x+XX[k]][y+YY[k]]=1
              C[0]+=1
      ans=ans+C[0]*C[1]
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline


def main():
    H, W = map(int, input().split())
    S = [None] * (H + 2)
    S[0] = S[-1] = "x" * (W + 2)
    for i in range(1, H + 1):
        S[i] = "".join(["x", input().rstrip(), "x"])

    group = []
    visited = [[True] + [False] * W + [True] for _ in range(H + 2)]
    visited[0] = visited[-1] = [True] * (W + 2)
    for h in range(1, H + 1):
        for w in range(1, W + 1):
            if visited[h][w]:
                continue
            queue = deque([(h, w, S[h][w])])
            group.append({"#": 0, ".": 0})
            while queue:
                y, x, s = queue.popleft()
                if visited[y][x]:
                    continue
                visited[y][x] = True
                group[-1][s] += 1
                for i, j in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                    yy, xx = y + i, x + j
                    if visited[yy][xx]:
                        continue
                    if s == "#" and S[yy][xx] == ".":
                        queue.append((yy, xx, "."))
                    elif s == "." and S[yy][xx] == "#":
                        queue.append((yy, xx, "#"))

    ans = 0
    for g in group:
        ans += g["#"] * g["."]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
belong=list()
group=list()
C=list()

def init(X):
  global belong,group,C
  belong=list(range(X))
  group=[[i] for i in range(X)]
  C=[[S[i//W][i%W]=='#',S[i//W][i%W]=='.'] for i in range(X)]

def unite(x,y):
  if len(group[belong[x]])<len(group[belong[y]]):
    x,y=y,x
  if belong[x]==belong[y]:
    return True
  z=belong[y]
  for i in range(len(group[z])):
    belong[group[z][-1]]=belong[x]
    group[belong[x]].append(group[z][-1])
    del group[z][-1]
  for i in range(2):
    C[belong[x]][i]+=C[z][i]
    C[z][i]=0
  return False

H,W=map(int,input().split())
S=[input() for i in range(H)]
init(H*W)
for i in range(H):
  for j in range(W):
    if i:
      if S[i][j]!=S[i-1][j]:
        unite(i*W+j,i*W+j-W)
    if j:
      if S[i][j]!=S[i][j-1]:
        unite(i*W+j,i*W+j-1)
    if i+1<H:
      if S[i][j]!=S[i+1][j]:
        unite(i*W+j,i*W+j+W)
    if j+1<W:
      if S[i][j]!=S[i][j+1]:
        unite(i*W+j,i*W+j+1)
P=0
for i in range(H*W):
  P+=C[i][0]*C[i][1]
print(P)

Submission status: Accepted

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

G = [[None for j in range(W)] for i in range(H)]

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

count = 0

for i in range(H):
    for j in range(W):
        if G[i][j] is not None:
            continue
        if S[i][j] == '#':
            color = 1
        else:
            color = 0
        stack = [(i, j, color)]
        G[i][j] = count
        while stack:
            x, y, c = stack.pop()
            for k in range(4):
                nx, ny = x + dx[k], y + dy[k]
                if not (0 <= nx < H and 0 <= ny < W):
                    continue
                if G[nx][ny] is not None:
                    continue
                if S[nx][ny] == '#':
                    nc = 1
                else:
                    nc = 0
                if nc == c:
                    continue
                G[nx][ny] = count
                stack.append((nx, ny, nc))
        count += 1

C = [[0, 0] for _ in range(count)]

for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            C[G[i][j]][0] += 1
        else:
            C[G[i][j]][1] += 1

res = 0

for b, w in C:
    res += b * w

print(res)

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

H, W = map(int, input().split())
S = [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 = deque()
        q.append((i, j))
        visited[i][j] = True
        n = defaultdict(int)
        while len(q) > 0:
            si, sj = q.popleft()
            n[S[si][sj]] += 1
            for di, dj in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
                if 0 <= si + di < H and 0 <= sj + dj < W and S[si][sj] != S[si + di][sj + dj] and not visited[si + di][sj + dj]:
                    q.append((si + di, sj + dj))
                    visited[si + di][sj + dj] = True
        ans += n['#'] * n['.']

print(ans)

Submission status: Accepted

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

def C(i, j):
    p = [1, 0]
    q = deque([(i, j, ".")])
    while q:
        x, y, c = q.popleft()
        for u, v in d:
            dx, dy = x + u, y + v
            if 0 <= dx < h and 0 <= dy < w and s[dx][dy] != c and use[dx][dy]:
                use[dx][dy] = False
                p[s[dx][dy] == "#"] += 1
                q.append((dx, dy, s[dx][dy]))
    return p[0]*p[1]


h, w = map(int, input().split())
s = [input() for i in range(h)]
use = [[1] * w for i in range(h)]
d = [(0, 1), (1, 0), (0, -1), (-1, 0)]
ans = 0
for i in range(h):
    for j in range(w):
        if use[i][j] and s[i][j] == ".":
            use[i][j] = False
            ans += C(i, j)
print(ans)

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 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 = map(int,input().split())
N = H*W
def num(i,j):
    return i*W+j
def coo(num):
    i = num // W
    j = num % W
    return(i,j)

uf = UnionFind(N)
color = [-1]*N
grid = []
for i in range(H):
    grid.append(list(input()))
for i in range(H):
    for j in range(W):
        color[num(i,j)]= grid[i][j]
for i in range(H):
    for j in range(W-1):
        if grid[i][j] != grid[i][j+1]:
            uf.union(num(i,j),num(i,j+1))
for i in range(H-1):
    for j in range(W):
        if grid[i][j] != grid[i+1][j]:
            uf.union(num(i,j),num(i+1,j))
ans = 0
BW = [[0,0] for _ in range(N)]
for i in range(N):
    root = uf.find(i)
    if color[i] == "#":
        BW[root][0] += 1
    else:
        BW[root][1] += 1
for root in uf.roots():
    ans += BW[root][0]*BW[root][1]
print(ans)

Submission status: Accepted

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

def C(i, j):
    p = [1, 0]
    q = deque([(i, j, ".")])
    while q:
        x, y, c = q.popleft()
        for u, v in d:
            dx, dy = x + u, y + v
            if 0 <= dx < h and 0 <= dy < w and s[dx][dy] != c and use[dx][dy]:
                use[dx][dy] = False
                p[s[dx][dy] == "#"] += 1
                q.append((dx, dy, s[dx][dy]))
    return p[0]*p[1]


h, w = map(int, input().split())
s = [input() for i in range(h)]
use = [[1] * w for i in range(h)]
d = [(0, 1), (1, 0), (0, -1), (-1, 0)]
ans = 0
for i in range(h):
    for j in range(w):
        if use[i][j] and s[i][j] == ".":
            use[i][j] = False
            ans += C(i, j)
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W = map(int, input().split())
    grid = list(list(input()) for _ in range(H))

    res = [[0] * W for _ in range(H)]
    visited = [[False] * W for _ in range(H)]
    for y in range(H):
        for x in range(W):
            if grid[y][x] == "#":
                visited[y][x] = True
                que = deque([[y, x]])
                cnt = 1
                tmp = []
                while que:
                    h, w = que.popleft()
                    for dh, dw in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                        next_h, next_w = h + dh, w + dw
                        if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                            continue
                        if grid[h][w] == "#" and grid[next_h][next_w] == ".":
                            if not visited[next_h][next_w]:
                                que.append([next_h, next_w])
                                tmp.append([next_h, next_w])
                                visited[next_h][next_w] = True
                        elif grid[h][w] == "." and grid[next_h][next_w] == "#":
                            if not visited[next_h][next_w]:
                                cnt += 1
                                que.append([next_h, next_w])
                                visited[next_h][next_w] = True
                for h, w in tmp:
                    res[h][w] = cnt
    ans = 0
    for h in range(H):
        ans += sum(res[h])
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def check_path(mp, is_archive, wi, hi):
	w = len(mp[0])
	h = len(mp)
	nb = 0
	nw = 0
	qq=collections.deque()
	st_color = mp[hi][wi]
	nb+=1
	qq.append((wi, hi, st_color))
	is_archive[hi][wi] = 1
	while qq:
		pw, ph, pc = qq.popleft()
		for dw, dh in ((1,0), (-1,0), (0,1),(0,-1)):
			if pw+dw<0 or pw+dw>=w or ph+dh < 0 or ph+dh >= h:
				continue
			if is_archive[ph+dh][pw+dw]>0:
				continue
			if mp[ph+dh][pw+dw]==pc:
				continue
			nc = mp[ph+dh][pw+dw]
			if nc == st_color:
				nb += 1
			else:
				nw += 1
			
			qq.append((pw+dw, ph+dh, nc))
			is_archive[ph+dh][pw+dw]=1
	
	return nb*nw

def main():
	#a = int(input())
	h, w = tin()
	#s = input()
	mp = [input() for _ in range(h)]
	is_archive = [[-1]*w for _ in range(h)]
	ret = 0
	for wi in range(w):
		for hi in range(h):
			if is_archive[hi][wi] != -1:
				continue
			nn = check_path(mp, is_archive, wi, hi)
			ret += nn
	print(ret)
			
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)