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(10000000)
H, W = map(int, input().split())
S = [input() for _ in range(H)]
seen = [[0]*W for _ in range(H)]


def rec(h,w,seen):
	if S[h][w] == '.':
		res = [1, 0]
	else:
		res = [0, 1]
	dh = [-1, 1, 0, 0]
	dw = [0, 0, -1, 1] 
	seen[h][w] = 1
	for i in range(4):
		nh = h+dh[i]
		nw = w+dw[i]
		if 0 <= nh <= H-1 and 0 <= nw <= W-1:
			if seen[nh][nw] == 0 and S[nh][nw] != S[h][w]:
				r0, r1 = rec(nh, nw, seen)
				res[0] += r0
				res[1] += r1
					
	return res

ans = 0
for h in range(H):
	for w in range(W):
		if seen[h][w] != 1:
			t0, t1 = rec(h, w, seen)
			ans += t0 * t1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H,W=map(int,input().split())
S=[]
for _ in range(H):
    s=input()
    S.append(s)
m=[[0]*W for _ in range(H)]
def DFS(y,x,S):

    d=deque([])
    d.append((y,x,0))
    white=0
    black=0
    while d:
        p,q,n=d.popleft()
        if m[p][q]==1:
            continue
        else:
            if n%2==0 and S[p][q]=='#':
                black+=1
                m[p][q]=1
                if 0<=p+1<=H-1 and S[p+1][q]=='.':
                    d.append((p+1,q,n+1))
                if 0<=p-1<=H-1 and S[p-1][q]=='.':
                    d.append((p-1,q,n+1))
                if 0<=q+1<=W-1 and S[p][q+1]=='.':
                    d.append((p,q+1,n+1))
                if 0<=q-1<=W-1 and S[p][q-1]=='.':
                    d.append((p,q-1,n+1))
            
            elif n%2==1 and S[p][q]=='.':
                white+=1
                
                m[p][q]=1
                if 0<=p+1<=H-1 and S[p+1][q]=='#':
                    d.append((p+1,q,n+1))
                if 0<=p-1<=H-1 and S[p-1][q]=='#':
                    d.append((p-1,q,n+1))
                if 0<=q+1<=W-1 and S[p][q+1]=='#':
                    d.append((p,q+1,n+1))
                if 0<=q-1<=W-1 and S[p][q-1]=='#':
                    d.append((p,q-1,n+1))
    return white,black

total=0
for i in range(H):
    for j in range(W):
        if S[i][j]=='.':
            continue
        elif m[i][j]==1:
            continue
        else:
            w,b=DFS(i,j,S)
            total+=w*b

print(total)

Submission status: Accepted

Solution code:
from collections import deque


def BFS():
    color=[["white" for _ in range(w)] for _ in range(h)]
    queue=deque([])
    ans=0

    for i in range(h):
        for j in range(w):
            if color[i][j]=="white" and S[i][j]=="#":
                queue.append([i,j])
                color[i][j]="gray"
                black,white=0,0

                while len(queue)>0:
                    c,d=queue.popleft()
                    if S[c][d]=="#":black +=1
                    else:white +=1

                    sign="." if S[c][d]=="#" else "#"
                    for a,b in [[1,0],[-1,0],[0,1],[0,-1]]:
                        X,Y=c+a,d+b
                        if 0<=X<h and 0<=Y<w:
                            if S[X][Y]==sign and color[X][Y]=="white":
                                color[X][Y]="gray"
                                queue.append([X,Y])
                    color[c][d]="black"
                ans +=black*white

    return ans


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

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    import sys
    input = sys.stdin.readline
    H, W = (int(i) for i in input().split())
    c = [[s for s in input()] for i in range(H)]
    dist = [[-1]*W for i in range(H)]

    def bfs(c, sy, sx, H, W):
        que = deque()

        dist[sy][sx] = 0
        que.append((sy, sx))
        d = ((1, 0), (0, 1), (-1, 0), (0, -1))
        flag = False  # 黒色マスにいるとき，True
        bla = 0
        whi = 0
        while que:
            uh, uw = que.popleft()
            if c[uh][uw] == "#":
                flag = True
                bla += 1
            else:
                flag = False
                whi += 1
            for dy, dx in d:
                next_h = uh + dy
                next_w = uw + dx
                if not(0 <= next_h < H and 0 <= next_w < W):
                    continue
                if dist[next_h][next_w] != -1:
                    continue
                if flag and c[next_h][next_w] == '#':
                    continue
                if not flag and c[next_h][next_w] == ".":
                    continue
                dist[next_h][next_w] = dist[uh][uw] + 1
                que.append((next_h, next_w))
        return bla * whi

    ans = 0
    for h in range(H):
        for w in range(W):
            if dist[h][w] != -1:
                continue
            if c[h][w] == "#":
                ans += bfs(c, h, w, H, W)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
class unionfind:#早いunionfind,class[i]のように要素指定すると親を得ることができる
    def __init__(self, elements=None):#elementsで初期化
        if elements is None:
            elements = ()
        self.parents = {}
        self.weights = {}
        for x in elements:
            self.weights[x] = 1
            self.parents[x] = x

    def __getitem__(self, i):
        # check for previously unknown i
        if i not in self.parents:
            self.parents[i] = i
            self.weights[i] = 1
            return i
        path = [i]
        root = self.parents[i]
        while root != path[-1]:
            path.append(root)
            root = self.parents[root]
        for ancestor in path:#縮約
            self.parents[ancestor] = root
        return root

    def __iter__(self):#for parent in Class:
        return iter(self.parents)

    def union(self, *objects):#オブジェクトをすべて結合
        roots = [self[x] for x in objects]
        heaviest = max(roots, key=lambda r: self.weights[r])
        for r in roots:
            if r != heaviest:
                self.weights[heaviest] += self.weights[r]
                self.parents[r] = heaviest

    def __len__(self):
        return len(self.parents)

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    #N = int(input())
    H,W = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    S = tuple(input() for i in range(H)) #改行行列
    uf=unionfind()
    for i in range(H):
        for j in range(W):
            x=i*W+j
            if i>0:
                if S[i][j]!=S[i-1][j]:
                    uf.union(x,(i-1)*W+j)
            if j>0:
                if S[i][j]!=S[i][j-1]:
                    uf.union(x,i*W+j-1)
    c=Counter()
    ps=set()
    for i in range(H*W):
        p=uf[i]
        ps.add(uf[i])
        if S[i//W][i%W]=="#":
            c[p*2]+=1
        else:
            c[p*2+1]+=1
        
    ans=0
    for p in ps:
        ans+=c[p*2]*c[p*2+1]
    print(ans)





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

H, W = map(int, input().split())
field = [[c == '#' for c in input()] for _ in range(H)]
counted = [[False] * W for _ in range(H)]
detected = [[False] * W for _ in range(H)]

b_count = defaultdict(int)
w_count = defaultdict(int)
another_group = [(0, 0)]
group = 0
while another_group:
    i, j = another_group.pop()
    detected[i][j] = True
    if counted[i][j]:
        continue
    
    stack = [(i, j)]
    while stack:
        i, j = stack.pop()
        if field[i][j]:
            b_count[group] += 1
        else:
            w_count[group] += 1
        #print(i, j, group)
        counted[i][j] = True
        for di, dj in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            if 0 <= i+di < H and 0 <= j+dj < W:
                if not detected[i+di][j+dj]:
                    if field[i+di][j+dj] == field[i][j]:
                        another_group.append((i+di, j+dj))
                    else:
                        detected[i+di][j+dj] = True
                        stack.append((i+di, j+dj))
                
    group += 1         

ans = 0
for bk, bv in b_count.items():
    ans += bv * w_count[bk]

print(ans)

Submission status: Accepted

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

H, W = map(int,input().split())
S = [input() for _ in range(H)]
#%%
visited = [[False]*W for _ in range(H)]
dx = [1,0,-1,0]
dy = [0,1,0,-1]

group_w = [0]*(H*W)
group_k = [0]*(H*W)

def dfs(x,y,state):
    if S[x][y]=='.':
        group_w[idx] += 1
    else:
        group_k[idx] += 1
    visited[x][y] = True
    
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if nx<0 or nx>=H or ny<0 or ny>=W:
            continue
        if visited[nx][ny]:
            continue
        if state==0 and S[nx][ny]=='#':
            dfs(nx,ny,1)
        elif state==1 and S[nx][ny]=='.':
            dfs(nx,ny,0)
    return 


ans = 0
idx = 0
for i in range(H):
    for j in range(W):
        if not visited[i][j]:
            dfs(i,j,S[i][j]=='#')
            a = group_w[idx]
            b = group_k[idx]
            ans += a*b
            idx += 1
       
print(ans)






# def dfs(x,y,res, numW,numK,state):
#     # print(x,y,res)
#     # state=0: next=Black
#     # state=1: next=White
#     newres = 0
#     flag = True
#     for i in range(4):
#         nx = x+dx[i]
#         ny = y+dy[i]
#         if nx<0 or nx>=H or ny<0 or ny>=W:
#             continue
#         if visited[nx][ny]:
#             continue
#         if state==0 and S[nx][ny]=='#':
#             visited[nx][ny] = True
#             newres += dfs(nx,ny,res+numW,numW,numK+1,1)
#             flag = False
#         elif state==1 and S[nx][ny]=='.':
#             visited[nx][ny] = True
#             newres += dfs(nx,ny,res+numK,numW+1,numK,0)
#             flag = False
    
#     # if flag:
#     #     visited[x][y] = False
#     if S[x][y]=='.':
#         return newres + numK
#     elif S[x][y]=='#':
#         return newres + numW

# ans = 0
# for i in range(H):
#     for j in range(W):
#         if not visited[i][j]:
#             numW = S[i][j]=='.'
#             numK = S[i][j]=='#'
#             visited[i][j] = True
#             ans += dfs(i,j,0,numW,numK,numK)
#             # print('X,Y =',i,j,ans)

# print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline


def DFS(add,next,cnt):
    x,y=add
    for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
        X,Y=x+i,y+j
        if 0<=X<h and 0<=Y<w:
            if S[X][Y]==next and color[X][Y]=="white":
                color[X][Y]=str(cnt)
                DFS([X,Y],"." if next=="#" else "#",cnt)


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

color=[["white" for _ in range(w)] for _ in range(h)]
for i in range(h):
    for j in range(w):
        if S[i][j]=="#" and color[i][j]=="white":
            cnt +=1
            DFS([i,j],".",cnt)

dictionary={str(i+1):[0,0] for i in range(cnt)}
for i in range(h):
    for j in range(w):
        if color[i][j]!="white":
            if S[i][j]==".":dictionary[color[i][j]][0] +=1
            else:dictionary[color[i][j]][1] +=1

ans=0
for v,m in dictionary.values():
    ans +=v*m
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500*500)

h,w=list(map(int,input().split()))
s=[[1 if c=='#' else 0 for c in input()] for _ in range(h)]
g=[[] for _ in range(h*w)]

for i in range(w):
    for j in range(h):
        for di in [-1,0,1]:
            for dj in [-1,0,1]:
                if abs(di)+abs(dj)!=1:
                    continue
                if 0<=i+di<w and 0<=j+dj<h:
                    if s[j][i]!=s[j+dj][i+di]:
                        g[j*w+i].append(i+di+(j+dj)*w)

visit=[0]*(h*w)
black=[0]*(h*w)
white=[0]*(h*w)

def rec(j,i,rj,ri):
    if s[j][i]:
        black[rj*w+ri]+=1
    else:
        white[rj*w+ri]+=1
    
    for n in g[j*w+i]:
        if visit[n]:
            continue

        visit[n]=1

        rec(n//w,n%w,rj,ri)

ans=0

for i in range(w):
    for j in range(h):
        if visit[w*j+i]:
            continue
        visit[w*j+i]=1

        rec(j,i,j,i)
        
        ans+=black[w*j+i]*white[w*j+i]

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
class UnionFind():
    def __init__(self, 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

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

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)

ans = 0

d = defaultdict(int)

for i in range(h*w):
    if S[i//w][i%w] == '.':
        d[uf.find(i)] += 1

for i, x in enumerate(uf.parents):
    if x < 0:
        # print(-x, d[i])
        cnt = -x
        ans += d[uf.find(i)] * (cnt-d[i])

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
def bfs(sl, visited, sy, sx, h, w):
    q = deque([(sy,sx,sl[sy][sx])])
    visited[sy][sx] = 0
    bh_cnt = {'#':0, '.':0}
    bh_cnt[sl[sy][sx]] += 1
    while q:
        y, x, bh = q.popleft()
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            ny, nx = y+j, x+k
            if ny >= h or nx >= w or ny < 0 or nx < 0:
                continue
            if sl[ny][nx] != bh and visited[ny][nx] == -1:
                visited[ny][nx] = visited[y][x] + 1
                bh_cnt[sl[ny][nx]] += 1
                q.append((ny,nx,sl[ny][nx]))
    return bh_cnt['#']*bh_cnt['.']


h,w = map(int, input().split())
sl = []
for _ in range(h):
    row = list(input())
    sl.append(row)
visited = [ [-1]*w for i in range(h)]

ans = 0
for hi in range(h):
    for wi in range(w):
        if visited[hi][wi] != -1: continue
        ans += bfs(sl, visited, hi, wi, h, w)
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]
dij=[(1,0),(0,1),(-1,0),(0,-1)]

def dfs(i,j):
    cnt=[0]*2
    color=ss[i][j]
    ss[i][j]=2
    cnt[color]+=1
    for di,dj in dij:
        ni,nj=i+di,j+dj
        if ni<0 or ni>=h or nj<0 or nj>=w:continue
        if ss[ni][nj]!=1-color:continue
        ret=dfs(ni,nj)
        cnt[0]+=ret[0]
        cnt[1] += ret[1]
    return cnt

h,w=MI()
ss=[[c=="#" for c in SI()] for _ in range(h)]
ans=0
for i in range(h):
    for j in range(w):
        if ss[i][j]==2:continue
        black,white=dfs(i,j)
        #print(i,j,black,white)
        ans+=black*white
print(ans)

Submission status: Accepted

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

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

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

dxdy = [(-1, 0), (1, 0), (0, -1), (0, 1)]

global ans
def dfs(x, y):
    seen[y][x] = 1
    a, b = 1, 0
    for dx, dy in dxdy:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < w and 0 <= ny < h and not seen[ny][nx] and s[y][x] != s[ny][nx]:
            p = dfs(nx, ny)
            a += p[1]
            b += p[0]
    
    return (a, b)

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

Submission status: Accepted

Solution code:


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    ################
    class UnionFind():
        """
        parents : 親要素(findしない場合は根ではないことの注意)，根の場合は"-(要素数）"
        find(x):要素xの属するグループの根を返す
        size(x):要素xの属するグループの要素数を返す
        same(x,y):x,yが同じグループに属しているか返す
        members(x):要素xが属するグループに属する要素をリストで返す
        roots:全ての根の要素を返す
        group_count():グループの数を返す
        all_group_members():{根要素：[そのグループに含まれる要素のリスト]}の辞書を返す
        """
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n

        def find(self, x):
            #根を探す&つなぎかえる
            if self.parents[x] < 0:
                return x
            else:
                self.parents[x] = self.find(self.parents[x])
                return self.parents[x]

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

            if x == y:
                return

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

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

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

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

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

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

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

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

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

    H,W=MI()
    S=[]
    for i in range(H):
        s=input()
        S.append(s)
    uf=UnionFind(H*W)
    
    dx=[0,1]
    dy=[1,0]
    
    def make(ii,jj):
        return ii*W+jj
    

    
    for i in range(H):
        for j in range(W):
            for k in range(2):
                ni=i+dx[k]
                nj=j+dy[k]
                if 0<=ni<H and 0<=nj<W:
                    if S[i][j]!=S[ni][nj]:
                        uf.union(make(i,j),make(ni,nj))
                        
    ans=0
    from collections import defaultdict
    ddb = defaultdict(int)
    ddh = defaultdict(int)
    
    for i in range(H):
        for j in range(W):
            v=make(i,j)
            root=uf.find(v)
            if S[i][j]=="#":
                ddb[root]+=1
            else:
                ddh[root]+=1
                
    for k,v in ddb.items():
        ans+=v*ddh[k]

        
        
    print(ans)
            
    
        
main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)

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

C = [[1 for i in range(W)] for j in range(H)]
L = ['.', '#']
D = {'.':0, '#':1}
tx = [1, 0, -1, 0]
ty = [0, 1, 0, -1]

def dfs(x, y, c, l):
    C[x][y] = 0
    l[c] += 1
    for i in range(4):
        nx = x + tx[i]
        ny = y + ty[i]
        if 0 <= nx < H and 0 <= ny < W and C[nx][ny] and L[c] != S[nx][ny]:
            l = dfs(nx, ny, 1 - c, l)
    return l

ans = 0
for i in range(H):
    for j in range(W):
        l = dfs(i, j, D[S[i][j]], [0, 0])
        ans += l[0] * l[1]

print(ans)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main 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 = IL()
data = SLs(H)

U = UnionFind(H*W)
for j in range(H):
  for i in range(W-1):
    if data[j][i] != data[j][i+1]:
      U.union(j*W+i,j*W+i+1)
for j in range(H-1):
  for i in range(W):
    if data[j][i] != data[j+1][i]:
      U.union(j*W+i,j*W+i+W)
dic = DD(lambda:[0,0])
for j in range(H):
  for i in range(W):
    dic[U.find(j*W+i)][int(data[j][i]==".")]+=1
ans = 0
for k in dic:
    ans += dic[k][0]*dic[k][1]
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
h, w = map(int, input().split())
n = h*w
fld = ''.join([input().rstrip()for _ in range(h)])


def to_v(i, j):
    return i*w+j


def generate_v2(v):
    i, j = divmod(v, w)
    if 0 < i:
        yield v-w
    if i < h-1:
        yield v+w
    if 0 < j:
        yield v-1
    if j < w-1:
        yield v+1


def dfs(v, c=0):
    if visited[v]:
        return
    visited[v] = 1
    cnt[c] += 1
    for v2 in generate_v2(v):
        if fld[v] == fld[v2]:
            continue
        dfs(v2, c ^ 1)


visited = [0]*n
ans = 0
for v in range(n):
    if visited[v]:
        continue
    cnt = [0, 0]
    dfs(v)
    ans += cnt[0]*cnt[1]
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
h, w = map(int, input().split())
n = h*w
fld = ''.join([input().rstrip()for _ in range(h)])
edges = [set() for _ in range(n)]


def to_v(i, j):
    return i*w+j


for i in range(h):
    for j in range(w):
        v = to_v(i, j)
        dirc = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        for di, dj in dirc:
            x, y = i+di, j+dj
            if x < 0 or h <= x or y < 0 or w <= y:
                continue
            v2 = to_v(x, y)
            if fld[v] != fld[v2]:
                edges[v].add(v2)
                edges[v2].add(v)


def dfs(v, c=0):
    if visited[v]:
        return
    visited[v] = 1
    cnt[c] += 1
    for v2 in edges[v]:
        dfs(v2, c ^ 1)


visited = [0]*n
ans = 0
for v in range(n):
    if visited[v]:
        continue
    cnt = [0, 0]
    dfs(v)
    ans += cnt[0]*cnt[1]
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
h, w = map(int, input().split())
n = h*w
fld = ''.join([input().rstrip()for _ in range(h)])
edges = [[]for _ in range(n)]


def to_v(i, j):
    return i*w+j


for i in range(h):
    for j in range(w):
        v = to_v(i, j)
        dirc = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        for di, dj in dirc:
            x, y = i+di, j+dj
            if x < 0 or h <= x or y < 0 or w <= y:
                continue
            v2 = to_v(x, y)
            if fld[v] != fld[v2]:
                edges[v].append(v2)
                edges[v2].append(v)


def dfs(v, c=0):
    if visited[v]:
        return
    visited[v] = 1
    cnt[c] += 1
    for v2 in edges[v]:
        dfs(v2, c ^ 1)


visited = [0]*n
ans = 0
for v in range(n):
    if visited[v]:
        continue
    cnt = [0, 0]
    dfs(v)
    ans += cnt[0]*cnt[1]
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

used = [[0]*w for i in range(h)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
ans = 0

for i in range(h):
    for j in range(w):
        if used[i][j]:
            continue
        cw = 0
        cb = 0
        q = deque([])
        q.append([i,j])
        used[i][j] = 1
        while q:
            x,y = q.popleft()
            if s[x][y] == "#":
                cb += 1
            else:
                cw += 1
            for k in range(4):
                nx = x+dx[k]
                ny = y+dy[k]
                if 0 <= nx < h and 0 <= ny < w:
                    if (not used[nx][ny]) and s[x][y] != s[nx][ny]:
                        used[nx][ny] = 1
                        q.append([nx,ny])
        ans += cw*cb
print(ans)