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

H,W = map(int,input().split())
grid = [["&"] * (W+2) for i in range(H+2)]
visited = [[False] * (W+2) for i in range(H+2)]
# debug: visited_count = [[0] * (W+2) for i in range(H+2)]
start = []
for i in range(H):
    s = input()
    for j in range(W):
        grid[i+1][j+1] = s[j]

ans = 0
b = 0
w = 0
def dfs(p_i,p_j):
    if visited[p_i][p_j] is True:
        global ans
        return
    visited[p_i][p_j] = True
    if grid[p_i][p_j] == "#":
        # debug: visited_count[p_i][p_j] += 1
        global b
        b += 1
    elif grid[p_i][p_j] == ".":
        # debug: visited_count[p_i][p_j] += 1
        global w
        w += 1
    around = [[p_i,p_j+1],[p_i+1,p_j],[p_i,p_j-1],[p_i-1,p_j]]
    for i,j in around:
        if grid[p_i][p_j] == "#" and grid[i][j] == ".":
            dfs(i,j)
        elif grid[p_i][p_j] == "." and grid[i][j] == "#":
            dfs(i,j)

for i in range(1,H+1):
    for j in range(1,W+1):
        if visited[i][j] is False:
            dfs(i,j)
            ans += b * w
            b = 0
            w = 0

print(ans)

""" debug
print(start)
for line in visited_count:
    print(line)
print("b = {}".format(b))
print("w = {}".format(w)) """

Submission status: Accepted

Solution code:
import sys
from itertools import product

sys.setrecursionlimit(200000)


def input():
    return sys.stdin.readline()[:-1]


def ii(t: type = int):
    return t(input())


def il(t: type = int):
    return list(map(t, input().split()))


def imi(N: int, t: type = int):
    return [ii(t) for _ in range(N)]


def iml(N: int, t: type = int):
    return [il(t) for _ in range(N)]


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

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


H, W = il()
S = imi(H, str)
tree = UnionFind(H * W)
for i, j in product(range(H), range(W)):
    for d in ((-1, 0), (0, -1), (1, 0), (0, 1)):
        x = i + d[0]
        y = j + d[1]
        if 0 <= x < H and 0 <= y < W:
            if S[i][j] != S[x][y]:
                tree.union((i * W + j), (x * W + y))

k = set(tree.par)
dot = {i: 0 for i in k}
sharp = {i: 0 for i in k}
for i, j in product(range(H), range(W)):
    if S[i][j] == ".":
        dot[tree.find(i * W + j)] += 1
    else:
        sharp[tree.find(i * W + j)] += 1

ans = 0
for i in k:
    ans += dot[i] * sharp[i]
print(ans)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
S=[list(input()) for i in range(H)]
N=H*W
par=[0 for i in range(N)]
rnk=[0 for i in range(N)]
def init(n):
    for i in range(N):
        par[i]=i
        rnk[i]=0
def find(x):
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def unite(x,y):
    x=find(x)
    y=find(y)
    if x==y:
        return
    if (rnk[x]<rnk[y]):
        par[x]=y
    else:
        par[y]=x
        if(rnk[x]==rnk[y]):
            rnk[x]+=1
def same(x,y):
    return find(x)==find(y)
init(N)
dx=[0,0,1,-1]
dy=[1,-1,0,0]
for i in range(H):
    for j in range(W):
        for k in range(4):
            nx=dx[k]+i
            ny=dy[k]+j
            if 0<=nx<H and 0<=ny<W:
                if S[nx][ny]!=S[i][j]:
                    p=i*W+j
                    q=nx*W+ny
                    unite(p,q)
A=[find(i) for i in range(N)]
D=dict()
for j in range(N):
    i=A[j]
    if not(i in D):
        D[i]=[0,0]
    if S[j//W][j%W]=="#":
        D[i][1]+=1
    else:
        D[i][0]+=1
ans=0
for i in D:
    seq=D[i]
    ans+=seq[0]*seq[1]
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import product

sys.setrecursionlimit(200000)


def input():
    return sys.stdin.readline()[:-1]


def ii(t: type = int):
    return t(input())


def il(t: type = int):
    return list(map(t, input().split()))


def imi(N: int, t: type = int):
    return [ii(t) for _ in range(N)]


def iml(N: int, t: type = int):
    return [il(t) for _ in range(N)]


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [0] * (n + 1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


H, W = il()
S = imi(H, str)
tree = UnionFind(H * W)
for i, j in product(range(H), range(W)):
    for d in ((-1, 0), (0, -1), (1, 0), (0, 1)):
        x = i + d[0]
        y = j + d[1]
        if 0 <= x < H and 0 <= y < W:
            if S[i][j] != S[x][y]:
                tree.union((i * W + j), (x * W + y))

dot = [0] * (H * W)
sharp = [0] * (H * W)
for i, j in product(range(H), range(W)):
    if S[i][j] == ".":
        dot[tree.find(i * W + j)] += 1
    else:
        sharp[tree.find(i * W + j)] += 1

ans = 0
for i in range(H * W):
    ans += dot[i] * sharp[i]
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

def dfs(i,j,color): # i,jの色がcolorと同じなら0, colorと異なるなら連結成分でまだカウントされていない要素を数えてその白黒の数を返す
    if not(0<=i<h and 0<=j<w): return 0,0 # i,jが意味をなさないとき
    if s[i][j]==color: return 0,0 # i,jの色がcolorと同じとき
    if t[i][j]: return 0,0 # すでにカウントしたi,jであったとき
    
    t[i][j]=True
    c = s[i][j]
    bl, wh=0,0
    if c=='#':
        bl+=1
    else:
        wh+=1
    

    # tmp1,tmp2=dfs(i+1,j,c)
    # bl,wh=bl+tmp1,wh+tmp2

    # tmp1,tmp2=dfs(i-1,j,c)
    # bl,wh=bl+tmp1,wh+tmp2
            
    # tmp1,tmp2=dfs(i,j-1,c)
    # bl,wh=bl+tmp1,wh+tmp2

    # tmp1,tmp2=dfs(i,j+1,c)
    # bl,wh=bl+tmp1,wh+tmp2

    # return bl,wh

    tmp1, tmp2 = dfs(i-1,j,s[i][j])
    bl,wh = bl+tmp1, wh+tmp2

    tmp1, tmp2 = dfs(i+1,j,s[i][j])
    bl,wh = bl+tmp1, wh+tmp2

    tmp1, tmp2 = dfs(i,j-1,s[i][j])
    bl,wh = bl+tmp1, wh+tmp2

    tmp1, tmp2 = dfs(i,j+1,s[i][j])
    bl,wh = bl+tmp1, wh+tmp2

    return bl,wh

ans = 0
for i in range(h):
    for j in range(w):
        a,b = dfs(i,j,'!')
        ans += a*b
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

def dfs(i,j,color): # i,jの色がcolorと同じなら0, colorと異なるなら連結成分でまだカウントされていない要素を数えてその白黒の数を返す
    if not(0<=i<h and 0<=j<w): return 0,0 # i,jが意味をなさないとき
    if s[i][j]==color: return 0,0 # i,jの色がcolorと同じとき
    if t[i][j]: return 0,0 # すでにカウントしたi,jであったとき
    
    t[i][j]=True
    c = s[i][j]
    bl, wh=0,0
    if c=='#':
        bl+=1
    else:
        wh+=1
    

    tmp1,tmp2=dfs(i+1,j,c)
    bl,wh=bl+tmp1,wh+tmp2

    tmp1,tmp2=dfs(i-1,j,c)
    bl,wh=bl+tmp1,wh+tmp2
            
    tmp1,tmp2=dfs(i,j-1,c)
    bl,wh=bl+tmp1,wh+tmp2

    tmp1,tmp2=dfs(i,j+1,c)
    bl,wh=bl+tmp1,wh+tmp2

    return bl,wh

    # tmp1, tmp2 = dfs(i-1,j,s[i][j])
    # bl,wh = bl+tmp1, wh+tmp2

    # tmp1, tmp2 = dfs(i+1,j,s[i][j])
    # bl,wh = bl+tmp1, wh+tmp2

    # tmp1, tmp2 = dfs(i,j-1,s[i][j])
    # bl,wh = bl+tmp1, wh+tmp1

    # tmp1, tmp2 = dfs(i,j+1,s[i][j])
    # bl,wh = bl+tmp1, wh+tmp2

    # return bl,wh

ans = 0
for i in range(h):
    for j in range(w):
        a,b = dfs(i,j,'!')
        ans += a*b
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

def dfs(i,j,color): # i,jの色がcolorと同じなら0, colorと異なるなら連結成分でまだカウントされていない要素を数えてその白黒の数を返す
    if not(0<=i<h and 0<=j<w): return 0,0 # i,jが意味をなさないとき
    if s[i][j]==color: return 0,0 # i,jの色がcolorと同じとき
    if t[i][j]: return 0,0 # すでにカウントしたi,jであったとき
    
    t[i][j]=True
    c = s[i][j]
    wh, bl=0,0
    if c=='#':
        bl+=1
    else:
        wh+=1
    

    tmp1,tmp2=dfs(i+1,j,c)
    wh,bl=wh+tmp1,bl+tmp2

    tmp1,tmp2=dfs(i-1,j,c)
    wh,bl=wh+tmp1,bl+tmp2
            
    tmp1,tmp2=dfs(i,j-1,c)
    wh,bl=wh+tmp1,bl+tmp2

    tmp1,tmp2=dfs(i,j+1,c)
    wh,bl=wh+tmp1,bl+tmp2

    return wh,bl

    # tmp1, tmp2 = dfs(i-1,j,s[i][j])
    # bl,wh = bl+tmp1, wh+tmp2

    # tmp1, tmp2 = dfs(i+1,j,s[i][j])
    # bl,wh = bl+tmp1, wh+tmp2

    # tmp1, tmp2 = dfs(i,j-1,s[i][j])
    # bl,wh = bl+tmp1, wh+tmp1

    # tmp1, tmp2 = dfs(i,j+1,s[i][j])
    # bl,wh = bl+tmp1, wh+tmp2

    # return bl,wh

ans = 0
for i in range(h):
    for j in range(w):
        a,b = dfs(i,j,'!')
        ans += a*b
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

def dfs(i,j,color): # i,jの色がcolorと同じなら0, colorと異なるなら連結成分でまだカウントされていない要素を数えてその白黒の数を返す
    if not(0<=i<h and 0<=j<w): return 0,0 # i,jが意味をなさないとき
    if s[i][j]==color: return 0,0 # i,jの色がcolorと同じとき
    if t[i][j]: return 0,0 # すでにカウントしたi,jであったとき
    
    t[i][j]=True
    #c = s[i][j]
    wh, bl=0,0
    if s[i][j]=='#':
        bl+=1
    else:
        wh+=1
    

    tmp1,tmp2=dfs(i+1,j,s[i][j])
    wh,bl=wh+tmp1,bl+tmp2

    tmp1,tmp2=dfs(i-1,j,s[i][j])
    wh,bl=wh+tmp1,bl+tmp2
            
    tmp1,tmp2=dfs(i,j-1,s[i][j])
    wh,bl=wh+tmp1,bl+tmp2

    tmp1,tmp2=dfs(i,j+1,s[i][j])
    wh,bl=wh+tmp1,bl+tmp2

    return wh,bl

    # tmp1, tmp2 = dfs(i-1,j,s[i][j])
    # bl,wh = bl+tmp1, wh+tmp2

    # tmp1, tmp2 = dfs(i+1,j,s[i][j])
    # bl,wh = bl+tmp1, wh+tmp2

    # tmp1, tmp2 = dfs(i,j-1,s[i][j])
    # bl,wh = bl+tmp1, wh+tmp1

    # tmp1, tmp2 = dfs(i,j+1,s[i][j])
    # bl,wh = bl+tmp1, wh+tmp2

    # return bl,wh

ans = 0
for i in range(h):
    for j in range(w):
        a,b = dfs(i,j,'!')
        ans += a*b
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

def dfs(i,j,color):

  if not (0<=i<h and 0<=j<w):return 0,0
  if s[i][j]==color: return 0,0
  if t[i][j]:return 0,0

  t[i][j]=True
  wh,bl=0,0
  if s[i][j]=="#":
    bl+=1
  else:
    wh+=1

  tmp1,tmp2=dfs(i+1,j,s[i][j])
  wh,bl=wh+tmp1,bl+tmp2

  tmp1,tmp2=dfs(i-1,j,s[i][j])
  wh,bl=wh+tmp1,bl+tmp2
        
  tmp1,tmp2=dfs(i,j-1,s[i][j])
  wh,bl=wh+tmp1,bl+tmp2

  tmp1,tmp2=dfs(i,j+1,s[i][j])
  wh,bl=wh+tmp1,bl+tmp2

  return wh,bl

ans=0
for i in range(h):
  for j in range(w):
    a,b=dfs(i,j,"!")
    ans+=a*b

print(ans)

Submission status: Accepted

Solution code:
import sys
c=0
b=0
wi=0
x=[-1,0,1,0]
y=[0,-1,0,1]
buf=[]
def one():
    return -1
def count(h,w,S,table,H,W,index):
    global buf,x,y,b,wi
    if index==1:
        b+=1
    else:
        wi+=1
    if index==1:
        S[h][w]='@'
    for i in range(4):
        if h+y[i]>=0 and h+y[i]<H and w+x[i]>=0 and w+x[i]<W:
            if table[h+y[i]][w+x[i]]==-1:
                if index==0 and S[h+y[i]][w+x[i]]=='#':
                    table[h+y[i]][w+x[i]]=1
                    buf.append([h+y[i],w+x[i],1])
                elif index==1 and S[h+y[i]][w+x[i]]=='.':
                    table[h+y[i]][w+x[i]]=1
                    buf.append([h+y[i],w+x[i],0])
    if buf:
        a=buf.pop(0)
        count(a[0],a[1],S,table,H,W,a[2])
sys.setrecursionlimit(10000000)
H,W=map(int,input().split())
T=[]
table=[[-1 for j in range(W)] for i in range(H)]
for i in range(H):
    T.append(input())
S=[['' for j in range(W)]for i in range(H)]
for h in range(H):
    for w in range(W):
        S[h][w]=T[h][w]
for h in range(H):
    for w in range(W):
        if S[h][w]=='#':
            table[h][w]=0
            count(h,w,S,table,H,W,1)
            c+=b*wi
            b=0
            wi=0
print(c)

Submission status: Accepted

Solution code:
from collections import deque

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


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

result = 0
for i in range(H):
    for j in range(W):

        if visited[i][j]:
            continue
        visited[i][j] = True

        b, w = 0, 0

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

            for d in range(4):

                ni, nj = ci + di[d], cj + dj[d]
                if not (0 <= ni < H and 0 <= nj < W):
                    continue

                if S[ci][cj] == S[ni][nj]:
                    continue

                if visited[ni][nj]:
                    continue
                visited[ni][nj] = True

                que.append((ni, nj))

        result += b * w


print(result)

Submission status: Accepted

Solution code:
class UnionFind:
    """
    - sizeを指定
    - 要素をグループにまとめる(unite) 
    - 要素同士が同じグループか判定する(isSame)
    - 分離はできない
    - par: 親の番号(はじめ par[i]==i つまりすべての頂点が根)
    - 始め各要素は別々のグループ"""
    def __init__(self, size: int):
        self.par = [-1]*size
        for i in range(size):
            self.par[i] = i 
    
    def root(self, x: int) -> int:
        """根を求める"""
        if self.par[x] == x: # if root
            return x
        else:
            self.par[x] = self.root(self.par[x]) # 経路圧縮
            return self.par[x]
    
    def isSame(self, x:int, y:int)->bool:
        """x と y が同じ集合に属するか否か"""
        return self.root(x)==self.root(y)
    
    def unite(self, x:int, y:int):
        """x と y の属する集合を併合"""
        x = self.root(x)
        y = self.root(y)
        if x == y: return
        self.par[x] = y


H,W = map(int, input().split())
s = [input() for _ in range(H)]
uf = UnionFind(H*W) 

def pos2int(h,w):
    # 座標->[0 - H*W]
    return h*W + w

for h in range(H):
    for w in range(W):        
        for dh, dw in zip((0, 1), (1, 0)):
            if not(0<=h+dh<H and 0<=w+dw<W):
                continue
            if s[h][w] != s[h+dh][w+dw]: # 同じグループにする
                uf.unite(pos2int(h, w), pos2int(h+dh, w+dw))
                
white = [0] * H*W
black = [0] * H*W
 
for h in range(H):
    for w in range(W):
        n = pos2int(h, w)
        r = uf.root(n)
        # print(n, r)
        if s[h][w] == ".":
            white[r] += 1
        else:
            black[r] += 1
# print(white)
# print(black)
ans = 0
for h in range(H):
    for w in range(W):
        n = pos2int(h, w)
        ans += white[n] * black[n]
print(ans)

Submission status: Accepted

Solution code:
from collections import deque


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


di = (1, 0, -1, 0)
dj = (0, 1, 0, -1)

def is_valid(i, j, d):
    ni = i + di[d]
    nj = j + dj[d]
    if not (0 <= ni < H and 0 <= nj < W):
        return False
    if S[i][j] == S[ni][nj]:
        return False
    return True


result = 0
visited = [[False] * W for _ in range(H)]
for i in range(H):
    for j in range(W):

        if visited[i][j]:
            continue
        visited[i][j] = True

        b = 0
        w = 0
        que = deque()
        que.append((i, j))
        while que:
            (ci, cj) = que.pop()
            if S[ci][cj] == '#':
                b += 1
            else:
                w += 1

            for d in range(4):
                if not is_valid(ci, cj, d):
                    continue
                ni = ci + di[d]
                nj = cj + dj[d]
                if visited[ni][nj]:
                    continue
                visited[ni][nj] = True
                que.append((ni, nj))

        result += b * w


print(result)

Submission status: Accepted

Solution code:
def c_alternating_path(H, W, Grid):
    from itertools import product
    from collections import deque

    ans = 0
    is_visited = [[False] * W for _ in range(H)]
    for h, w in product(range(H), range(W)):
        if Grid[h][w] == '#' and not is_visited[h][w]:
            count_white, count_black = 0, 0
            q = deque([(h, w)])
            while q:
                row, col = q.popleft()
                if is_visited[row][col]:
                    continue

                is_visited[row][col] = True
                if Grid[row][col] == '#':
                    count_black += 1
                else:
                    count_white += 1

                for dr, dc in [(0, -1), (1, 0), (0, 1), (-1, 0)]:
                    nr, nc = row + dr, col + dc
                    if (0 <= nr < H and 0 <= nc < W
                        and Grid[row][col] != Grid[nr][nc]
                            and not is_visited[nr][nc]):
                        q.append((nr, nc))
            ans += count_black * count_white
    return ans

H, W = [int(i) for i in input().split()]
Grid = [input() for _ in range(H)]
print(c_alternating_path(H, W, Grid))

Submission status: Accepted

Solution code:
H, W = map(int, input().split())

X = [[0] * W for i in range(H)]
G = [[0,0] for i in range(W*H)] 
L = [[-1] * W for i in range(H)] # Group ID

for i in range(H):
    s = input()
    for j in range(W):
        if (i+j) % 2 == 0:
            if s[j] == "#":
                X[i][j] = 1
        else:
            if s[j] != "#":
                X[i][j] = 1



g = -1
for i in range(H):
    for j in range(W):
        if L[i][j] < 0:
            g += 1
            L[i][j] = g
            post = [[i,j]]
            G[g][(i+j)%2] += 1
            while post:
                pre = post
                post = []
                for ggg in pre:
                    i0, j0 = ggg
                    if i0>0 and L[i0-1][j0] < 0 and X[i0][j0] == X[i0-1][j0]:
                        post.append([i0-1,j0])
                        L[i0-1][j0] = g
                        G[g][(i0+j0+1)%2] += 1
                    if i0<H-1 and L[i0+1][j0] < 0 and X[i0][j0] == X[i0+1][j0]:
                        post.append([i0+1,j0])
                        L[i0+1][j0] = g
                        G[g][(i0+j0+1)%2] += 1
                    if j0>0 and L[i0][j0-1] < 0 and X[i0][j0] == X[i0][j0-1]:
                        post.append([i0,j0-1])
                        L[i0][j0-1] = g
                        G[g][(i0+j0+1)%2] += 1
                    if j0<W-1 and L[i0][j0+1] < 0 and X[i0][j0] == X[i0][j0+1]:
                        post.append([i0,j0+1])
                        L[i0][j0+1] = g
                        G[g][(i0+j0+1)%2] += 1
                        
            # print(GGG)
# print(G)
ans = 0
for t in G:
    aa, bb = t
    ans += aa * bb
    
print(ans)

Submission status: Accepted

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

def path(i,j):
    p=[]
    for k in [1,-1]:
        if 0<=i+k<H:
            if S[i][j]!=S[i+k][j]:
                p.append((i+k,j))
        if 0<=j+k<W:
            if S[i][j]!=S[i][j+k]:
                p.append((i,j+k))
    return p
f = [[0 for i in range(W)] for j in range(H)]
ans=0

for i in range(H):
    for j in range(W):
        if f[i][j]==0:
            f[i][j]=1
            b=0
            w=0
            if S[i][j]=='#':
                b+=1
            else:
                w+=1
            que=path(i,j)

            while len(que)>0:
                tmp=[]
                for q in que:
                    q0,q1=q
                    if f[q0][q1]==0:
                        f[q0][q1]=1
                        if S[q0][q1]=='#':
                            b+=1
                        else:
                            w+=1
                        for p in path(q0,q1):
                            if f[p[0]][p[1]]==0:
                                tmp.append(p)
                que=tmp
            ans+=b*w
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]

H, W = map(int, input().split())
a = [[None for _ in range(W)] for _ in range(H)]  # black == True
reached = [[False for _ in range(W)] for _ in range(H)]
for r in range(H):
    s = input()
    for c in range(W):
        a[r][c] = (s[c] == '#')

ans = 0
for r in range(H):
    for c in range(W):
        if reached[r][c]: continue
        reached[r][c] = True

        b = 0
        w = 0

        dq = deque()
        dq.append((r, c))

        while dq:
            rr, cc = dq.popleft()
            if a[rr][cc]:
                b += 1
            else:
                w += 1
            for di in range(4):
                nr = rr + dr[di]
                if not (0 <= nr < H): continue

                nc = cc + dc[di]
                if not (0 <= nc < W): continue

                if a[rr][cc] == a[nr][nc]: continue

                if reached[nr][nc]: continue
                reached[nr][nc] = True

                dq.append((nr, nc))
        ans += b * w

print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
S = ['' for i in range(H)]
for i in range(H):
  S[i] = input()
R = [[[i, j] for j in range(W)] for i in range(H)]
U = [[1 for j in range(W)] for i in range(H)]
def root(A):
  if R[A[0]][A[1]] == A:
    return A
  else:
    R[A[0]][A[1]] = root(R[A[0]][A[1]])
    return R[A[0]][A[1]]
def union(A, B):
  rA = root(A)
  rB = root(B)
  if rA[0] < rB[0]:
    R[rB[0]][rB[1]] = rA
    U[rA[0]][rA[1]] += U[rB[0]][rB[1]]
  elif rB[0] < rA[0]:
    R[rA[0]][rA[1]] = rB
    U[rB[0]][rB[1]] += U[rA[0]][rA[1]]
  elif rA[1] < rB[1]:
    R[rB[0]][rB[1]] = rA
    U[rA[0]][rA[1]] += U[rB[0]][rB[1]]
  elif rB[1] < rA[1]:
    R[rA[0]][rA[1]] = rB
    U[rB[0]][rB[1]] += U[rA[0]][rA[1]]
for i in range(H):
  for j in range(W):
    if S[i][j] == ".":
      if i > 0 and S[i - 1][j] == "#":
        if j > 0 and S[i - 1][j - 1] == ".":
          union([i, j], [i - 1, j - 1])
        if i > 1 and S[i - 2][j] == ".":
          union([i, j], [i - 2, j])
        if j < W - 1 and S[i - 1][j + 1] == ".":
          union([i, j], [i - 1, j + 1])
      if j > 0 and S[i][j - 1] == "#":
        if i > 0 and S[i - 1][j - 1] == ".":
          union([i, j], [i - 1, j - 1])
        if j > 1 and S[i][j - 2] == ".":
          union([i, j], [i, j - 2])
        if i < H - 1 and S[i + 1][j - 1] == ".":
          union([i, j], [i + 1, j - 1])
      if j < W - 1 and S[i][j + 1] == "#":
        if i > 0 and S[i - 1][j + 1] == ".":
          union([i, j], [i - 1, j + 1])
for i in range(H):
  for j in range(W):
    root([i, j])
cnt = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == "#":
      if i > 0 and S[i - 1][j] == ".":
        r = R[i - 1][j]
        cnt += U[r[0]][r[1]]
      elif i < H - 1 and S[i + 1][j] == ".":
        r = R[i + 1][j]
        cnt += U[r[0]][r[1]]
      elif j > 0 and S[i][j - 1] == ".":
        r = R[i][j - 1]
        cnt += U[r[0]][r[1]]
      elif j < W - 1 and S[i][j + 1] == ".":
        r = R[i][j + 1]
        cnt += U[r[0]][r[1]]
print(cnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
H, W = list(map(int, input().split()))
Sn = [input() for _ in range(H)]

def func(h,w): # 黒のみ
    move = [(0,-1),(-1,0),(0,1),(1,0)]
    w_cnt = 0
    b_cnt = 0
    que = deque()
    que.append((h,w))
    while len(que) > 0:
        xh,xw = que.popleft()
        if visited[xh][xw] == 0:
            visited[xh][xw] = 1
            if Sn[xh][xw] == "#":
                b_cnt += 1
            else:
                w_cnt += 1
        else:
            continue
            
        for mh, mw in move:
            if 0 <= xh + mh < H and 0 <= xw + mw < W:
                if Sn[xh][xw] != Sn[xh + mh][xw + mw] and visited[xh + mh][xw + mw] == 0:
                    que.append((xh + mh, xw + mw))

    return b_cnt, w_cnt

cnt = 0
visited = [[0 for _ in range(W)] for _ in range(H)]

for i in range(H):
    for j in range(W):
        if Sn[i][j] == "#" and visited[i][j]==0:
            b_cnt, w_cnt = func(i, j)
            cnt += b_cnt*w_cnt
            
print(cnt)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/aising2019/submissions/3986315
# 解説のように 連結成分を求めてから、bfsする
import sys
sys.setrecursionlimit(2 * 10 ** 5)

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

ans = 0

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

un_reached = [[True for i in range(W)] for j in range(H)]


def isIn(x, y):
    return 0 <= x < H and 0 <= y < W


def dfs(x, y):
    un_reached[x][y] = False
    if s[x][y] == '#':
        cc[1] += 1
    else:
        cc[0] += 1

    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if isIn(nx, ny) and s[nx][ny] != s[x][y] and un_reached[nx][ny]:
            dfs(nx, ny)


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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)


class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n + 1)]
        self.rank = [0 for _ in range(n + 1)]
        self.size = [1] * (n + 1)

    def find(self, x):
        # If x is root
        if self.parent[x] == x:
            return x
        # If x is not root, search again by using x's parent
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        # Make an edge from the root of lower tree to the root of higher tree
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.size[y] += self.size[x]
        else:
            self.parent[y] = x
            self.size[x] += self.size[y]
            # If the height of tree the tree is the same, increase one of the heights by 1
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

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


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

brack_list = []
union_find = UnionFind(H * W)
for i in range(H):
    for j in range(W):
        if s_list[i][j] == "#":
            brack_list.append(i * W + j)
            if i - 1 >= 0 and s_list[i - 1][j] == ".":
                union_find.union(i * W + j, (i - 1) * W + j)
            if i + 1 < H and s_list[i + 1][j] == ".":
                union_find.union(i * W + j, (i + 1) * W + j)
            if j - 1 >= 0 and s_list[i][j - 1] == ".":
                union_find.union(i * W + j, i * W + j - 1)
            if j + 1 < W and s_list[i][j + 1] == ".":
                union_find.union(i * W + j, i * W + j + 1)


black = {}
white = {}
for i in range(H):
    for j in range(W):
        p = union_find.find(i * W + j)
        if s_list[i][j] == "#":
            if p in black:
                black[p] += 1
            else:
                black[p] = 1
        else:
            if p in white:
                white[p] += 1
            else:
                white[p] = 1

p = set(union_find.parent[:-1])
count = 0
for i in p:
    if i in black and i in white:
        count += white[i] * black[i]
print(count)

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(200000)
#input = sys.stdin.readline
h,w = map(int,input().split())
a = [[j for j in input()] for i in range(h)]
used = [[0]*w for i in range(h)]
def dfs(x,y):
    if used[x][y]:
        return 0
    global go
    used[x][y] = 1
    if x-1 >=0 and a[x-1][y] != a[x][y]:
            go.add((x-1,y))
            dfs(x-1,y)
    if y-1 >=0 and a[x][y-1] != a[x][y]:
            go.add((x,y-1))
            dfs(x,y-1)
    if x+1 <h and a[x+1][y] != a[x][y]:
            go.add((x+1,y))      
            dfs(x+1,y)
    if y+1 <w and a[x][y+1] != a[x][y]:
            go.add((x,y+1))
            dfs(x,y+1)
ans = 0
for i in range(h):
    for j in range(w):
        go = set()
        if used[i][j]:
            continue
        dfs(i,j)
        kuro = 0
        siro = 0
        for k,l in go:
            if a[k][l] == "#":
                kuro += 1
            else:
                siro += 1
        ans += kuro*siro

print(ans)

Submission status: Accepted

Solution code:
import heapq

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

L = [["N" for j in range(W)] for i in range(H)]
c = 0

for i in range(H):
	for j in range(W):
		if L[i][j] == "N":
			L[i][j] = c
			Q = []
			heapq.heappush(Q, (i, j))
			while Q:
				x, y = heapq.heappop(Q)
				if x - 1 >= 0:
					if Sl[x][y] != Sl[x - 1][y] and L[x - 1][y] == "N":
						L[x - 1][y] = c
						heapq.heappush(Q, (x - 1, y))
				if x + 1 <= H - 1:
					if Sl[x][y] != Sl[x + 1][y] and L[x + 1][y] == "N":
						L[x + 1][y] = c
						heapq.heappush(Q, (x + 1, y))
				if y - 1 >= 0:
					if Sl[x][y] != Sl[x][y - 1] and L[x][y - 1] == "N":
						L[x][y - 1] = c
						heapq.heappush(Q, (x, y - 1))
				if y + 1 <= W - 1:
					if Sl[x][y] != Sl[x][y + 1] and L[x][y + 1] == "N":
						L[x][y + 1] = c
						heapq.heappush(Q, (x, y + 1))
			c += 1

xl = []
for i in range(c):
	xl.append([0, 0])

for i in range(H):
	for j in range(W):
		if Sl[i][j] == "#":
			xl[L[i][j]][0] += 1
		else:
			xl[L[i][j]][1] += 1

ans = 0
for i in range(c):
	ans += xl[i][0] * xl[i][1]

print(ans)