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:
#木の根を求める
def find(x,par):
    if par[x] == x:
        return x
    else:
        return find(par[x],par)

#xとyの属する集合の併合
def unite(x,y,par,rank):
    x = find(x,par)
    y = find(y,par)
    
    if x != y:
        #xとyの属している集合が異なる時
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x]==rank[y]:
                rank[x] += 1

#xとyが同じ集合に属するかの判定
def same(x,y,par):
    return find(x,par) == find(y,par)
    
h, w = map(int,input().split())
s = [["dammy"] * (w+2)]
for i in range(h):
    s.append(["dammy"]+list(input())+["dammy"])
s.append(["dammy"] * (w+2))

par = [i for i in range(h*w+1)] #index調整
rank = [1] * (h*w+1) #index調整

for i in range(1,h+1):
    for j in range(1,w+1):
        index = w*(i-1)+j
        if s[i][j] == "#": #黒
            if s[i-1][j] == ".":
                unite(index, index-w, par, rank)
            if s[i+1][j] == ".":
                unite(index, index+w, par, rank)
            if s[i][j-1] == ".":
                unite(index, index-1, par, rank)
            if s[i][j+1] == ".":
                unite(index, index+1, par, rank)
        elif s[i][j] == ".": #白
            if s[i-1][j] == "#":
                unite(index, index-w, par, rank)
            if s[i+1][j] == "#":
                unite(index, index+w, par, rank)
            if s[i][j-1] == "#":
                unite(index, index-1, par, rank)
            if s[i][j+1] == "#":
                unite(index, index+1, par, rank)

bw = [[0,0] for i in range(h*w+1)]
parset = set()

for i in range(1,h+1):
    for j in range(1, w+1):
        index = w*(i-1)+j
        parent = find(index,par)
        if not parent in parset:
            parset.add(parent)
        if s[i][j] == "#":
            bw[parent][0] += 1
        elif s[i][j] == ".":
            bw[parent][1] += 1

ans = 0

for i in list(parset):
    ans += (bw[i][0] * bw[i][1])
    
print(ans)

Submission status: Accepted

Solution code:
# Union-Findデータ構造
class UnionFind:
    def __init__(self, numV):
        self.pars = list(range(numV))
        self.ranks = [0] * numV
    def find(self, x):
        if self.pars[x] == x: return x
        else:
            self.pars[x] = self.find(self.pars[x])
            return self.pars[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        if self.ranks[x] < self.ranks[y]:
            self.pars[x] = y
        else:
            self.pars[y] = x
            if self.ranks[x] == self.ranks[y]:
                self.ranks[x] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)

def conv(i, j):
    return (i-1)*W + j-1

H, W = map(int, input().split())
Sss = ['_' + input() + '_' for _ in range(H)]
Sss = ['_' * (W + 2)] + Sss + ['_' * (W + 2)]

N = H * W
UF = UnionFind(N)
for i in range(1, H+1):
    for j in range(1, W+1):
        revS = '.' if Sss[i][j] == '#' else '#'
        for di, dj in [(-1,0), (1,0), (0,-1), (0,1)]:
            if Sss[i+di][j+dj] == revS:
                UF.union(conv(i, j), conv(i+di, j+dj))

numBs, numWs = [0]*N, [0]*N
for i in range(1, H+1):
    for j in range(1, W+1):
        no = UF.find(conv(i, j))
        if Sss[i][j] == '#':
            numBs[no] += 1
        else:
            numWs[no] += 1

ans = 0
for numB, numW in zip(numBs, numWs):
    ans += numB * numW
print(ans)

Submission status: Accepted

Solution code:
def main():
    h, w = [int(x) for x in input().rstrip("\n").split(" ")]

    from collections import defaultdict
    blacks = []
    board_bw = defaultdict(str)
    board_count = defaultdict(int)
    grouped = {}
    for r in range(h):
        line = input().rstrip("\n")
        for c in range(w):
            board_bw[r,c] = line[c]
            if line[c] == '#':
                blacks.append((r,c))
    offsets = [(1,0), (-1, 0), (0, 1), (0, -1)]
    
    groups = []
    group_no = 0
    total = 0
    for (r,c) in blacks:
        if not (r, c) in grouped:
            group_no += 1
            group_black = 1
            group_white = 0
            black_nexts = [(r, c)]
            grouped[(r,c)] = 1
            while black_nexts:
                white_nexts = []
                for black_r, black_c in black_nexts:
                    for offset_r, offset_c in offsets:
                        white_next = (black_r + offset_r),(black_c + offset_c)
                        if board_bw[white_next] == "." and not white_next in grouped:
                            group_white += 1
                            grouped[white_next] = group_no
                            white_nexts.append(white_next)
                black_nexts = []
                for white_r, white_c in white_nexts:
                    for offset_r, offset_c in offsets:
                        black_next = (white_r + offset_r),(white_c + offset_c)
                        if board_bw[black_next] == "#" and not black_next in grouped:
                            group_black += 1
                            grouped[black_next] = group_no
                            black_nexts.append(black_next)
            total += group_black * group_white
    print(total)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

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

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

def func(y, x, c):
    if y < 0 or x < 0 or y >= H or x >= W:
        return 0, 0
    if used[y][x] or S[y][x] == c:
        return 0, 0

    used[y][x] = True

    rw, rb = 0, 0
    if S[y][x] == '.':
        rw = 1
    else:
        rb = 1
    ret = func(y - 1, x, S[y][x])
    rw += ret[0]
    rb += ret[1]
    ret = func(y + 1, x, S[y][x])
    rw += ret[0]
    rb += ret[1]
    ret = func(y, x - 1, S[y][x])
    rw += ret[0]
    rb += ret[1]
    ret = func(y, x + 1, S[y][x])
    rw += ret[0]
    rb += ret[1]
    return rw, rb

ans = 0

for i in range(H):
    for j in range(W):
        ret = func(i, j, ' ')
        ans += ret[0] * ret[1]

print ans

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

"""
・幅優先
"""

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H, W = MAP()

# 右左上下
directions = [(0,1),(0,-1),(1,0),(-1,0)]
# 四方に一回り大きいグリッドを作る
grid = [['*'] * (W+2) for i in range(H+2)]
for i in range(1,H+1):
    row = list(input())
    for j in range(1, W+1):
        grid[i][j] = row[j-1]

visited = list2d(H+2, W+2, False)

def bfs(start):
    que = deque()
    # スタート位置
    que.append(start)
    # 白マス通過カウント
    w_cnt = 0
    # 黒マス通過カウント
    b_cnt = 0
    while len(que):
        cur = que.popleft()
        # 見終わった場所はもうやらない
        if visited[cur[0]][cur[1]]:
            continue
        # 訪問済にする
        visited[cur[0]][cur[1]] = True
        # 今のマスのカウント追加
        if grid[cur[0]][cur[1]] == '.':
            w_cnt += 1
        elif grid[cur[0]][cur[1]] == '#':
            b_cnt += 1
        # 4方向見る
        for direction in directions:
            # 上下左右に1つずつ動かした座標
            nxt = list(map(lambda x,y: x+y, cur, direction))
            # 壁か今のマスと同じ色はスキップ
            if grid[nxt[0]][nxt[1]] == '*' or grid[cur[0]][cur[1]] == grid[nxt[0]][nxt[1]]:
                continue
            # キューに次のマスを足す
            que.append(nxt)
    # 今回調べた範囲で得られるカウントを返却
    return w_cnt * b_cnt

cnt = 0
for i in range(H+2):
    for j in range(W+2):
        if grid[i][j] == '#' and not visited[i][j]:
            cnt += bfs((i, j))
print(cnt)

Submission status: Accepted

Solution code:
from collections import deque

BLACK = '#'
WHITE = '.'
vec_x = [1, 0, -1, 0]
vec_y = [0, 1, 0, -1]
vec_num = len(vec_x)

def solve():
    count = 0
    for i in range(H):
        for j in range(W):
            if used[i][j]:
                continue
            b = 0
            w = 0
            que = deque([(i, j)])
            used[i][j] = True

            while que:
                next_i, next_j = que.popleft()

                #黒か白かをカウント
                if(S[next_i][next_j] == BLACK):
                    b += 1
                else:
                    w += 1

                #隣接するマスの色が現在のマスと違うならキューに追加
                for d in range(vec_num):
                    d_i = next_i + vec_y[d]
                    d_j = next_j + vec_x[d]
                    if not check(next_i, next_j, d_i, d_j) or used[d_i][d_j]:
                        continue
                    que.append((d_i, d_j))
                    used[d_i][d_j] = True
            count += b * w
    return count

def check(i, j, d_i, d_j):
    if not (0 <= d_i < H and 0 <= d_j < W):
        return False
    if S[i][j] == S[d_i][d_j]:
        return False
    return True



if __name__ == "__main__":
    H, W = map(int, input().split())
    S = [[]] * H
    used = [[]] * H
    for h in range(H):
        S[h] = list(input())
        used[h] = [False] * W
    print(solve())

Submission status: Accepted

Solution code:
from collections import deque

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

explored = [[False for i in range(W)] for j in range(H)]
dxy = [(-1,0),(1,0),(0,-1),(0,1)]
ans = 0

for h in range(H) :
    for w in range(W) :
        if not explored[h][w] :
            q = deque([(h,w)])
            black = 0
            white = 0
            
            while q :
                y,x = q.popleft()
                explored[y][x] = True
                if MAP[y][x] == "#" :
                    black += 1
                else :
                    white += 1
                
                for dy,dx in dxy :
                    ny = y+dy
                    nx = x+dx
                    
                    if (ny < 0) or (ny >= H) or (nx < 0) or (nx >= W) :
                        continue
                    if explored[ny][nx] :
                        continue
                    if MAP[ny][nx] == MAP[y][x] :
                        continue
                    explored[ny][nx] = True
                    q.append((ny,nx))
                    
            ans += black*white

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
seen = [[False for __ in range(w)] for _ in range(h)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
black_count = 0
white_count = 0


def dfs(x: int, y: int):
    global black_count, white_count

    if s[x][y] == '#':
        black_count += 1
    else:
        white_count += 1

    seen[x][y] = True

    for k in range(4):
        next_x = x + dx[k]
        next_y = y + dy[k]

        if 0 <= next_x < h and 0 <= next_y < w:
            if s[x][y] != s[next_x][next_y] and not seen[next_x][next_y]:
                dfs(next_x, next_y)


def main():
    from sys import setrecursionlimit
    setrecursionlimit(200000)

    global black_count, white_count
    ans = 0

    # See:
    # http://drken1215.hatenablog.com/entry/2019/01/13/035500
    for i in range(h):
        for j in range(w):
            if s[i][j] == '#' and not seen[i][j]:
                black_count = 0
                white_count = 0
                dfs(i, j)
                ans += black_count * white_count

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    h,w = LI()
    a = [[c == '#' for c in S()] for _ in range(h)]
    b = [[None] * w for _ in range(h)]

    def f(i,j,k):
        if b[i][j] or a[i][j] != k:
            return (0,0)
        b[i][j] = 1
        r = [1,0]
        for di,dj in dd:
            ni = i + di
            nj = j + dj
            if ni < 0 or ni >= h or nj < 0 or nj >= w:
                continue
            res = f(ni,nj,not k)
            r[0] += res[1]
            r[1] += res[0]
        return r

    r = 0
    for i in range(h):
        for j in range(w):
            t = f(i,j,a[i][j])
            r += t[0] * t[1]

    return r



print(main())

Submission status: Accepted

Solution code:
from collections import Counter
class uf(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(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 x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
    def is_same(self, x, y):
        return self.find(x) == self.find(y)

def alte(h,w,s):
    ufa=uf(h*w)

    for x in range(h):
        for y in range(w):
            if s[x][y]!=s[min(x+1,h-1)][y]:
                ufa.union(x*w+y,x*w+y+w)
            if s[x][y]!=s[x][min(y+1,w-1)]:
                ufa.union(x*w+y,x*w+y+1)

    cnta=Counter()
    cntb=Counter()

    for x in range(h):
        for y in range(w):
            k = x*w+y
            if s[x][y] == '.':
                cnta[ufa.find(k)] += 1
            else:
                cntb[ufa.find(k)] += 1

    cnt=0
    for i in range(h*w):
        cnt+=cnta[i]*cntb[i]

    return cnt

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

Submission status: Accepted

Solution code:
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(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 x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

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

h,m=map(int, input().split())
s=[list(input()) for i in range(h)]
uf1=UnionFind(h*m)
for i in range(h):
    for j in range(m):
        if s[i][j]!=s[min(i+1,h-1)][j]:uf1.union(i*m+j,i*m+j+m)
        if s[i][j]!=s[i][min(j+1,m-1)]:uf1.union(i*m+j,i*m+j+1)
from collections import Counter
c1=Counter()
c2=Counter()
for i in range(h):
    for j in range(m):
        k = i*m+j
        if s[i][j] == '.':c1[uf1.find(k)] += 1
        else:c2[uf1.find(k)] += 1
ans=0
for i in range(h*m):
    ans+=c1[i]*c2[i]
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

def search_obj(x,y,grids):
    ans = [0,0]
    curr_state = grids[y][x]
    grids[y][x] = '0'    
    obj_state = '.'
    if(curr_state == '.'):
        ans[0] += 1
        obj_state = '#'
    elif(curr_state == '#'):
        ans[1] += 1
    
    if(grids[y-1][x] == obj_state):
        a,b = search_obj(x,y-1,grids)
        ans[0] += a
        ans[1] += b

    if(grids[y][x-1] == obj_state):
        a,b = search_obj(x-1,y,grids)
        ans[0] += a
        ans[1] += b

    if(grids[y+1][x] == obj_state):
        a,b = search_obj(x,y+1,grids)
        ans[0] += a
        ans[1] += b

    if(grids[y][x+1] == obj_state):
        a,b = search_obj(x+1,y,grids)
        ans[0] += a
        ans[1] += b

    return ans
    

H,W = (int(x) for x in input().split())
s = ""
ans = 0
for _ in range(W+2):
    s+="0"
s = list(s)
grids = [s]

for _ in range(H):
    si = input()
    si = "0"+si+"0"
    grids.append(list(si))
    
grids.append(s)

for i in range(W):
    for j in range(H):
        if(grids[j+1][i+1]!='0'):
            a,b = search_obj(i+1,j+1,grids)
            ans += a*b

print(ans)

Submission status: Accepted

Solution code:
#from collections import deque
H,W=map(int,input().split())
S=[input() for i in range(H)]
visit=[[False]*W for i in range(H)]
par=[[None]*W for i in range(H)]
dd={}
X=[-1,0,1,0]
Y=[0,-1,0,1]
for j in range(H):
    for i in range(W):
        if visit[j][i]:
            continue
        if S[j][i]=='.':
            continue
        lH=[]
        lH.append((j,i,0))#0が黒
        par[j][i]=(i,j)
        num=0
        while lH:
            y,x,t=lH.pop()
            visit[y][x]=True
            for k in range(4):
                nx=x+X[k]
                ny=y+Y[k]
                if 0<=nx<W and 0<=ny<H:
                    if visit[ny][nx]:
                        continue
                    if t==0 and S[ny][nx]=='.':
                        visit[ny][nx]=True
                        num+=1
                        lH.append((ny,nx,1))
                    elif t==1 and S[ny][nx]=='#':
                        visit[ny][nx] = True
                        par[ny][nx]=(i,j)
                        lH.append((ny,nx,0))
        dd[(i,j)]=num
#print(par)
#print(dd)
ans=0
for j in range(H):
    for i in range(W):
        if S[j][i]=='#':
            x,y=par[j][i]
            ans+=dd[(x,y)]
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
X = [[[0, 1][a=="#"] for a in input()] for i in range(H)]

ch = [[0] * W for _ in range(H)]
move = [(-1,0), (1,0), (0,-1), (0,1)]
ans = 0
for i in range(H):
    for j in range(W):
        if ch[i][j]:
            continue
            
        q = deque([(i,j)])
        a = [0, 0]
        while q:
            x, y = q.popleft()
            ch[x][y] = 1
            a[(x+y)%2] += 1
            for m in move:
                nx = x + m[0]
                ny = y + m[1]
                if nx >= 0 and nx < H and ny >= 0 and ny < W and X[x][y] != X[nx][ny]:
                    if ch[nx][ny] == 0:
                        q.append((nx,ny))
                        ch[nx][ny] = 1
        ans += a[0] * a[1]

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
X = [[[0, 1][a=="#"] for a in input()] for i in range(H)]

ch = [[0] * W for _ in range(H)]
move = [[-1,0], [1,0], [0,-1], [0,1]]
ans = 0
for i in range(H):
    for j in range(W):
        if ch[i][j]:
            continue
            
        ch[i][j] = 1
        q = deque([[i,j]])
        a = [0, 0]
        while q:
            t = q.popleft()
            x = t[0]
            y = t[1]
            ch[x][y] = 1
            a[(x+y)%2] += 1
            for m in move:
                nx = x + m[0]
                ny = y + m[1]
                if nx >= 0 and nx < H and ny >= 0 and ny < W and X[x][y] != X[nx][ny]:
                    if ch[nx][ny] == 0:
                        q.append([nx,ny])
                        ch[nx][ny] = 1
        ans += a[0] * a[1]

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
X = [[[0, 1][a=="#"] for a in input()] for i in range(H)]

ch = [[0] * W for _ in range(H)]
move = [[-1,0], [1,0], [0,-1], [0,1]]
ans = 0
for i in range(H):
    for j in range(W):
        if ch[i][j]:
            continue
            
        q = deque([[i,j]])
        a = [0, 0]
        while q:
            t = q.popleft()
            x = t[0]
            y = t[1]
            ch[x][y] = 1
            a[(x+y)%2] += 1
            for m in move:
                nx = x + m[0]
                ny = y + m[1]
                if nx >= 0 and nx < H and ny >= 0 and ny < W and X[x][y] != X[nx][ny]:
                    if ch[nx][ny] == 0:
                        q.append([nx,ny])
                        ch[nx][ny] = 1
        ans += a[0] * a[1]

print(ans)

Submission status: Accepted

Solution code:
def find(x):
  if x==Tree[x]:
      return x
  else:
      Tree[x]=find(Tree[x])
      return Tree[x]
def unite(x,y):
  s1=find(x)
  s2=find(y)
  if s1!=s2:
    Tree[s2]=s1
    size[s1][0]+=size[s2][0]
    size[s1][1]+=size[s2][1]
H,W=map(int,input().split())
Tree=[i for i in range(H*W)]
S=[]
size=[[0,0] for i in range(H*W)]
for i in range(H):
  S.append(input())
  for j in range(W):
    t=i*W+j
    if S[-1][j]==".":
      size[t][0]=1
    else:
      size[t][1]=1
for i in range(1,W):
  if S[0][i]!=S[0][i-1]:
    unite(i,i-1)
for i in range(1,H):
  if S[i][0]!=S[i-1][0]:
    unite(i*W,(i-1)*W)
for i in range(1,H):
  for j in range(1,W):
    if S[i][j]!=S[i][j-1]:
      t=i*W+j
      unite(t,t-1)
    if S[i][j]!=S[i-1][j]:
      t=i*W+j
      unite(t,t-W)
ans=0
for i in range(H*W):
  if i==Tree[i]:
    ans+=size[i][0]*size[i][1]
print(ans)

Submission status: Accepted

Solution code:

import numpy as np
from collections import deque
import sys

def parse(inp):
    H, W = map(int, next(inp).split())
    return np.array([list(next(inp).strip()) for _ in range(H)])

dis = [0, 0, 1, -1]
djs = [1, -1, 0, 0]

def search(S, i, j, Q, R):
    H, W = S.shape
    R[i, j] = True
    Q.append((i, j))
    n0 = 0
    n1 = 0
    while Q:
        i, j = Q.popleft()
        if S[i, j] == "#":
            n1 += 1
        else:
            n0 += 1
        gen = ((i + di, j + dj) for di, dj in zip(dis, djs))
        ijs = (g for g in gen if 0 <= g[0] and g[0] < H and 0 <= g[1] and g[1] < W)
        for ni, nj in ijs:
            if not R[ni, nj] and S[ni, nj] != S[i, j]:
                R[ni, nj] = True
                Q.append((ni, nj))
    return n0 * n1


def test(S):
    i, j = 0, 0
    Q = deque()
    R = np.full(S.shape, False)
    H, W = S.shape
    n = 0
    for i in range(H):
        for j in range(W):
            if not R[i, j]:
                n += search(S, i, j, Q, R)
    return n

print(test(parse(sys.stdin)))

Submission status: Accepted

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

import sys
sys.setrecursionlimit(500000)

itta = [[0] * W for i in range(H)]

def search(x, y, z):
    if y >= H or x >= W or x < 0 or y <  0:
        return
    elif C[y][x] == z:
        return
    elif itta[y][x] == 1:
        return
    elif C[y][x] == z:
        return
    else:
        itta[y][x] = 1
        
        if C[y][x] == '.':
            bw_count[0] += 1
        else:
            bw_count[1] += 1
        
        prez = C[y][x]
        
    search(x+1, y, prez)
    search(x-1, y, prez)
    search(x, y+1, prez)
    search(x, y-1, prez) 

ans = 0

for y in range(H):
    for x in range(W):
        if itta[y][x] ==1:
            pass
        else:
            bw_count = [0, 0]
            search(x, y, '-')
            
            ans += bw_count[0] * bw_count[1]  

print(ans)

Submission status: Accepted

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

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

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

    for x, y in box:
        tmp1, tmp2 = dfs(i+x, j+y, 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 math
H,W = list(map(int,input().split()))
data = [list(input()) for l in range(H)]
check = [[0 for s in range(W)] for k in range(H)]
sum = 0

def search(i,j,H,W,data,check):
    stack = [[i,j]]
    check[i][j] = 1 
    tempSum = 0
    numW = 0
    numB = 0
    while True:
        if len(stack) != 0:
            s = stack[-1]
            hNow,wNow = s[0],s[1]
            WB = data[hNow][wNow]
            if WB == '.':
                numW += 1
            else:
                numB += 1
        else:
            return (numW*numB),check


        stack.pop()

        if hNow < H-1:
            if (data[hNow+1][wNow] != WB) and (check[hNow+1][wNow] == 0):
                stack.append([hNow+1,wNow])
                check[hNow+1][wNow] = 1
        if wNow < W-1:
            if (data[hNow][wNow+1] != WB) and (check[hNow][wNow+1] == 0):
                stack.append([hNow,wNow+1])
                check[hNow][wNow+1] = 1

        if hNow > 0:
            if (data[hNow-1][wNow] != WB) and (check[hNow-1][wNow] == 0):
                stack.append([hNow-1,wNow])
                check[hNow-1][wNow] = 1

        if wNow > 0:
            if (data[hNow][wNow-1] != WB) and (check[hNow][wNow-1] == 0):
                stack.append([hNow,wNow-1])
                check[hNow][wNow-1] = 1
        
for i in range(H):
    for j in range(W):
        if (check[i][j] == 0):
            temp,check = search(i,j,H,W,data,check)
            sum += temp

print(sum)

Submission status: Accepted

Solution code:
h,w = map(int, input().split())
a = [list("*"*(w+2))]
for i in range(h):
  a.append(['*'] + list(input()) + ['*'])
a.append(list("*"*(w+2)))

b = [[0]*(w+2) for _ in range(h+2)]
direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]
ans=0
for i in range(1,h+1):
  for j in range(1,w+1):
    if a[i][j]=='#' and b[i][j]==0:
      countw = countb = 0
      stackb = [(i, j)]
      stackw = []
      while stackb:
        xb, yb = stackb.pop(-1)
        if b[xb][yb] != 0: continue
        countb+=1
        b[xb][yb]=1
        for d in direction:
          p, q = xb + d[0], yb + d[1]
          if a[p][q]=='.' and b[p][q]==0:
            stackw.append((p, q))
        while stackw:
          xw, yw = stackw.pop(-1)
          if b[xw][yw] != 0: continue
          countw+=1
          b[xw][yw]=1
          for d in direction:
            p, q = xw + d[0], yw + d[1]
            if a[p][q]=='#' and b[p][q]==0:
              stackb.append((p, q))
      ans += countb*countw
print(ans)

Submission status: Accepted

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
H,W      = list(map(int, input().split()))
S        =  [ list(input()) for _ in range(H)]

import sys
sys.setrecursionlimit(2600000)

united_count = [ ]
# [ (黒1個、白2個) ,... k 個] 

directions = [(1,0), (0,1), (-1,0), (0,-1)] # y,x の順番


def dfs(pos, c, now_k):
    # pos : (1,2)
    # 引数は現在の連結成分の番号
    # 座標と、現在の1,0 が渡される
    # 渡されたnow_kで塗りつぶす
    y,x = pos
    for d in directions:
        try:
            if y+d[0] < 0 or x+d[1] < 0:
                continue
            content = S[y+d[0]][x+d[1]] 

            if c != content and (content == "#" or content == ".") :
                S[y+d[0]][x+d[1]] = now_k
                inplace_tuple     = united_count[now_k]
                united_count[now_k]     = ( inplace_tuple[0] + 1, inplace_tuple[1]) if content == "#" else \
                                    ( inplace_tuple[0]    , inplace_tuple[1]+1) # タプルなので新しく作る

                dfs( (y+d[0], x+d[1]),  content,  now_k)  # DFSかける

            else:
                continue
        except:
            continue



now_k = 0
for y in range(H):
    for x in range(W):
        c = S[y][x]  
        if c == "#" or c == "." :
            united_count.append( (1,0) if  c == "#" else (0,1) ) # now_k番目
            S[y][x] = now_k  # cの値は黒だったら、1 を入れてdfsに投げる

            pos = (y,x)
            dfs(pos, c, now_k)
            now_k         += 1

        else:
            continue # もう数字が入っている場合は、パス


answer = 0
for uni in united_count:
    answer = ((uni[0]*uni[1]) + answer) 

print(answer)

Submission status: Accepted

Solution code:
h,w = map(int, input().split())
s = []
for i in range(h):
    s.append(input())
import sys
sys.setrecursionlimit(200000)
dy = [0,0,1,-1]
dx = [1,-1,0,0]
def dfs(y,x):
    global check
    global was
    was[y][x] = 1
    if s[y][x] == "#":
        check[0] += 1
    else:
        check[1] += 1
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if nx >= 0 and ny >= 0 and nx < w and ny < h and s[ny][nx] != s[y][x] and not was[ny][nx]:
            dfs(ny,nx)
ans = 0
was = [[0 for i in range(w)] for j in range(h)]
for i in range(w):
    for j in range(h):
        if not was[j][i]:
            check = [0,0]
            dfs(j,i)
            ans += check[0] * check[1]
print(ans)