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:
# https://atcoder.jp/contests/aising2019/submissions/3986315

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 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 0 <= nx < H and 0 <= ny < W 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)]  # [wt, bk]
            dfs(i, j)
            ans += cc[1] * cc[0]
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
sys.setrecursionlimit(200000)

H,W = map(int,input().split(' '))
S = []
for i in [0]*H:
	l = input()
	S.append([1 if x == '#' else -1 for x in l])

bk = 0
wh = 0
def check(S,x,y):
	global bk
	global wh
	if S[y][x] == 0:
		return
	if S[y][x] == 1:
		bk += 1
		S[y][x]=0
		if 0 < y and S[y-1][x] == -1:
			check(S,x,y-1)
		if 0 < x and S[y][x-1] == -1:
			check(S,x-1,y)
		if y < H-1 and S[y+1][x] == -1:
			check(S,x,y+1)
		if x < W-1 and S[y][x+1] == -1:
			check(S,x+1,y)
		return
	if S[y][x] == -1:
		wh += 1
		S[y][x]=0
		if 0 < y and S[y-1][x] == 1:
			check(S,x,y-1)
		if 0 < x and S[y][x-1] == 1:
			check(S,x-1,y)
		if y < H-1 and S[y+1][x] == 1:
			check(S,x,y+1)
		if x < W-1 and S[y][x+1] == 1:
			check(S,x+1,y)
		return

cnt = 0
for y in range(H):
	for x in range(W):
		if S[y][x] == 1:
			check(S,x,y)
			cnt += wh*bk
			wh = 0
			bk = 0
print(cnt)

Submission status: Accepted

Solution code:
import collections
H,W=map(int,input().split())
S=[input() for i in [0]*H]
M=[[-1]*W for _ in [0]*H]
k=0
for y in range(H):
    for x in range(W):
        if M[y][x]!=-1:continue #visited
        M[y][x]=k
        Q=collections.deque()
        Q.append((y,x))
        while len(Q)>0:
            i,j=Q.popleft()
            s=S[i][j]
            if i+1<H and M[i+1][j]==-1 and s!=S[i+1][j]:
                M[i+1][j]=k
                Q.append((i+1,j))
            if i-1>=0 and M[i-1][j]==-1 and s!=S[i-1][j]:
                M[i-1][j]=k
                Q.append((i-1,j))
            if j+1<W and M[i][j+1]==-1 and s!=S[i][j+1]:
                M[i][j+1]=k
                Q.append((i,j+1))
            if j-1>=0 and M[i][j-1]==-1 and s!=S[i][j-1]:
                M[i][j-1]=k
                Q.append((i,j-1))
            #print(k,M,Q)
        k+=1
ds={}
dd={}
for i in range(H):
    for j in range(W):
        m=M[i][j]
        if S[i][j]=='#':ds[m]=ds.get(m,0)+1
        else:dd[m]=dd.get(m,0)+1
r=0
for i in range(k):
    r += ds.get(i,0)*dd.get(i,0)
print(r)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [H, W] = [long(input_raw[0]), long(input_raw[1])]
    S = []
    for i in range(H):
        input_raw = read_func().strip()
        S.append(input_raw)

    move_list = [(0,1),(1,0),(0,-1),(-1,0)]
    is_visited = set([])
    count = 0
    for i in range(H):
        for j in range(W):
            path_list = [(i, j)]
            if (i, j) not in is_visited:
                is_visited.add((i, j))

                q = deque([(i, j)])
                while len(q) > 0:
                    nd = q.popleft()
                    for move in move_list:
                        new_i = nd[0] + move[0]
                        new_j = nd[1] + move[1]
                        if new_i >= 0 and new_j >= 0 and new_i < H and new_j < W:
                            if (new_i, new_j) not in is_visited:
                                if S[nd[0]][nd[1]] != S[new_i][new_j]:
                                    path_list.append((new_i, new_j))
                                    is_visited.add((new_i, new_j))
                                    q.append((new_i, new_j))
            black_num = 0
            white_num = 0
            for path in path_list:
                if S[path[0]][path[1]] == "#":
                    black_num += 1
                else:
                    white_num += 1
            count +=black_num *white_num

    print count



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
h=range(H)
w=range(W)
S=[input() for _ in h]
M=[[-1]*W for _ in h]
k=0
for y in h:
 for x in w:
  if M[y][x]!=-1:continue
  M[y][x]=k;Q=[(y,x)]
  while len(Q)>0:
   i,j=Q.pop();s=S[i][j];p=i+1;q=i-1;r=j+1;t=j-1
   if p<H and M[p][j]==-1 and s!=S[p][j]:M[p][j]=k;Q+=[(p,j)]
   if i>0 and M[q][j]==-1 and s!=S[q][j]:M[q][j]=k;Q+=[(q,j)]
   if r<W and M[i][r]==-1 and s!=S[i][r]:M[i][r]=k;Q+=[(i,r)]
   if j>0 and M[i][t]==-1 and s!=S[i][t]:M[i][t]=k;Q+=[(i,t)]
  k+=1
s={}
d={}
for i in h:
 for j in w:
  m=M[i][j]
  if S[i][j]=='#':s[m]=s.get(m,0)+1
  else:d[m]=d.get(m,0)+1
print(sum(s.get(i,0)*d.get(i,0)for i in range(k)))

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
h=range(H)
S=[input() for _ in h]
M=[[-1]*W for _ in h]
k=0
for y in h:
    for x in range(W):
        if M[y][x]!=-1:continue
        M[y][x]=k;Q=[(y,x)]
        while len(Q)>0:
            i,j=Q.pop();s=S[i][j];p=i+1;q=i-1;r=j+1;t=j-1
            if p<H and M[p][j]==-1 and s!=S[p][j]:M[p][j]=k;Q+=[(p,j)]
            if i>0 and M[q][j]==-1 and s!=S[q][j]:M[q][j]=k;Q+=[(q,j)]
            if r<W and M[i][r]==-1 and s!=S[i][r]:M[i][r]=k;Q+=[(i,r)]
            if j>0 and M[i][t]==-1 and s!=S[i][t]:M[i][t]=k;Q+=[(i,t)]
        k+=1
s={}
d={}
for i in range(H):
    for j in range(W):
        m=M[i][j]
        if S[i][j]=='#':s[m]=s.get(m,0)+1
        else:d[m]=d.get(m,0)+1
print(sum(s.get(i,0)*d.get(i,0)for i in range(k)))

Submission status: Accepted

Solution code:
from queue import Queue as Qe

H,W = map(int,input().split())

D = [[-1 for j in range(W)] for i in range(H)]
S = [input() for i in range(H)]

D[0][0] = 1
q = Qe()
q.put((0,0))
White = 1 if S[0][0] == "." else 0
Black = 1 if S[0][0] == "#" else 0
ans = 0

def_h = 0
def_w = 0
while not q.empty():
    h,w = q.get()
    #print(h,w,White,Black)
    if h-1>=0 and S[h][w]!=S[h-1][w] and D[h-1][w] == -1: #up
        if S[h-1][w]=="#":
            ans += White
            Black += 1
        else:
            ans += Black
            White += 1
        D[h-1][w] = 1
        q.put((h-1,w))
    if h+1<H and S[h][w]!=S[h+1][w] and D[h+1][w] == -1: #down
        if S[h+1][w]=="#":
            ans += White
            Black += 1
        else:
            ans += Black
            White += 1
        D[h+1][w] = 1
        q.put((h+1,w))
    if w-1>=0 and S[h][w]!=S[h][w-1] and D[h][w-1] == -1: #left
        if S[h][w-1]=="#":
            ans += White
            Black += 1
        else:
            ans += Black
            White += 1
        D[h][w-1] = 1
        q.put((h,w-1))
    if w+1<W and S[h][w]!=S[h][w+1] and D[h][w+1] == -1: #right
        if S[h][w+1]=="#":
            ans += White
            Black += 1
        else:
            ans += Black
            White += 1
        D[h][w+1] = 1
        q.put((h,w+1))
    if q.empty():
        okei = False
        for i in range(def_h,H):
            wara = def_w if i==def_h else 0
            for j in range(wara,W):
                if D[i][j] == -1:
                    D[i][j] = 1
                    q.put((i,j))
                    White = 1 if S[i][j] == "." else 0
                    Black = 1 if S[i][j] == "#" else 0
                    def_h,def_w = i,j
                    okei = True
                    break
            if okei: break
                
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.v = [-1 for _ in range(n)]  # 根(負): 連結頂点数 * (-1) / 子(正): 根の頂点番号(0-indexed)
        self.bk = [1 if s[r][c] == '#' else 0 for r in range(H) for c in range(W)]
        self.wt = [1 if s[r][c] == '.' else 0 for r in range(H) for c in range(W)]

    def find(self, x):  # xを含む木における根の頂点番号を返す
        if self.v[x] < 0:  # (負)は根
            return x
        else:  # 根の頂点番号
            self.v[x] = self.find(self.v[x])  # uniteでは, 旧根に属する頂点の根が旧根のままなので更新
            return self.v[x]

    def unite(self, x, y):  # 違う根に属していたらrankが低くなるように連結
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if -self.v[x] < -self.v[y]:  # size比較, 　(-1) * (連結頂点数 * (-1)), (正)同士の大小比較
            x, y = y, x  # 連結頂点数が少ない方をyにすると, findでの更新回数が減る？
        self.v[x] += self.v[y]  # 連結頂点数の和を取る, 連結頂点数 * (-1)
        self.v[y] = x  # 連結頂点数が少ないy(引数yの根の頂点番号)の根をx(引数xの根の頂点番号)にする

        self.bk[x % (H * W)] += self.bk[y % (H * W)]
        self.wt[x % (H * W)] += self.wt[y % (H * W)]

    def root(self, x):
        return self.v[x] < 0  # (負)は根

    def same(self, x, y):
        return self.find(x) == self.find(y)  # 同じ根に属するか

    def size(self, x):
        return -self.v[self.find(x)]  # 連結頂点数を返す

    def calc(self, x):
        return self.bk[x % (H * W)] * self.wt[x % (H * W)]

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

H, W = map(int, input().split())
s = [input() for _ in range(H)]
uf = UnionFind(2 * H * W)  # 全頂点 * 2
for r in range(H):
    for c in range(W):
        if s[r][c] == '#':
            for i in range(4):
                nr = r + dr[i]
                nc = c + dc[i]
                if 0 <= nr < H and 0 <= nc < W:
                    if s[nr][nc] == '.':
                        uf.unite(r * W + c, H * W + (nr * W + nc))  # #: *1, .: * 2
        else:
            for i in range(4):
                nr = r + dr[i]
                nc = c + dc[i]
                if 0 <= nr < H and 0 <= nc < W:
                    if s[nr][nc] == '#':
                        uf.unite(H * W + (r * W + c), nr * W + nc)  # #: *1, .: * 2

ans = 0
for r in range(H):
    for c in range(W):
        if uf.root(r * W + c):
            # print(r, c, '#')
            sz = uf.size(r * W + c)
            # print(' ', r * W + c, sz, '#')
            if sz > 1:
                ans += uf.calc(r * W + c)

        if uf.root(H * W + (r * W + c)):
            # print(r, c, '.')
            sz = uf.size(H * W + (r * W + c))
            # print(' ', r * W + c, sz, '.')
            if sz > 1:
                ans += uf.calc(H * W + (r * W + c))

print(ans)
# print(uf.v)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
s=[[0]+list(input())+[0]for i in range(h)]
s.insert(0,[0]*(w+2))
s.append([0]*(w+2))
c=["#","."]
n=0
for i in range(1,h+1):
    for j in range(1,w+1):
        g=[0,0]
        if s[i][j]!=0:
            p=c.index(s[i][j])
            g[c.index(s[i][j])]+=1
            k=[[i,j]]
            s[i][j]=0
            while len(k)>0:
                b=[]
                for f in range(len(k)):
                    if s[k[f][0]+1][k[f][1]]==c[(p+1)%2]:
                        b.append([k[f][0]+1,k[f][1]])
                        s[k[f][0]+1][k[f][1]]=0
                    if s[k[f][0]-1][k[f][1]]==c[(p+1)%2]:
                        b.append([k[f][0]-1,k[f][1]])
                        s[k[f][0]-1][k[f][1]]=0
                    if s[k[f][0]][k[f][1]+1]==c[(p+1)%2]:
                        b.append([k[f][0],k[f][1]+1])
                        s[k[f][0]][k[f][1]+1]=0
                    if s[k[f][0]][k[f][1]-1]==c[(p+1)%2]:
                        b.append([k[f][0],k[f][1]-1])
                        s[k[f][0]][k[f][1]-1]=0
                else:
                    k=b
                    g[(p+1)%2]+=len(b)
                    p+=1
            else:
                n+=g[0]*g[1]
else:
    print(n)

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]
def ndir(noh, now):
    result = []
    if now != 0:
        result.append((noh, now-1))
    if now != W-1:
        result.append((noh, now+1))
    if noh != 0:
        result.append((noh-1, now))
    if noh != H-1:
        result.append((noh+1, now))
    return result

H, W = inpl()
S = [input() for _ in range(H)]
direc = [(1, 0), (-1, 0), (0, 1), (0, -1)]
Col = [[0]*W for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if Col[i][j] or S[i][j] == '#':
            continue
        gw, gb, kw, kb = 0, 0, 0, 0
        stack = [(i, j)]
        while stack:
            nh, nw = stack.pop()
            Col[nh][nw] = True
            if (nh+nw)%2:
                if S[nh][nw] == '#':
                    kb += 1
                else:
                    kw += 1
            else:
                if S[nh][nw] == '#':
                    gb += 1
                else:
                    gw += 1
            for ah, aw in ndir(nh, nw):
                if (S[nh][nw] == '.')^(S[ah][aw] == '.') and not Col[ah][aw]:
                    stack.append((ah, aw))
                    Col[ah][aw] = True
        ans += kb*gw + kw*gb
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
H,W=map(int,input().split())
series = [[] for h in range(H)]
for h in range(H):
	series[h] = list(input())

def Go(h,w):
	#print(h,w)
	global c
	check[h][w]=1
	count = 0
	front = ""
	if series[h][w] == "#":
		front = "."
	else:
		front = "#"
	if h >= 1:
		if series[h-1][w] == front and check[h-1][w] == 0:
			if series[h-1][w] == ".":
				count += Go(h-1,w)+1
			else:
				count += Go(h-1,w)
				c += 1
				used[h-1][w] = 1
	if h < H-1:
		if series[h+1][w] == front and check[h+1][w] == 0:
			if series[h+1][w] == ".":
				count += Go(h+1,w)+1
			else:
				count += Go(h+1,w)
				c += 1
				used[h+1][w] = 1
	if w >= 1:
		if series[h][w-1] == front and check[h][w-1] == 0:
			if series[h][w-1] == ".":
				count += Go(h,w-1)+1
			else:
				count += Go(h,w-1)
				c += 1
				used[h][w-1] = 1
	if w < W-1:
		if series[h][w+1] == front and check[h][w+1] == 0:
			if series[h][w+1] == ".":
				count += Go(h,w+1)+1
			else:
				count += Go(h,w+1)
				c += 1
				used[h][w+1] = 1
	return count

ans=0
used =  [[0 for w in range(W)] for h in range(H)]
check = [[0 for w in range(W)] for h in range(H)]
for h in range(H):
	for w in range(W):
		if series[h][w] == "#" and used[h][w] == 0:
			c=1
			ans += Go(h,w) * c
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
board = []
black = "#"
white = "."
for _ in range(H):
    board.append(input())

flags = [[False for _ in range(W)] for _ in range(H)]
has_alternative_around = [[False for _ in range(W)] for _ in range(H)]

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

for i in range(H):
    for j in range(W):
        for dx, dy in deltas:
            ni = i + dx
            nj = j + dy
            if \
            ni >= 0 \
            and ni < H \
            and nj >= 0 \
            and nj < W \
            and board[i][j] != board[ni][nj]:
                has_alternative_around[i][j] = True
                has_alternative_around[ni][nj] = True

ans = 0

for i in range(H):
    for j in range(W):
        if flags[i][j] is True \
        or has_alternative_around[i][j] is False:
            continue
        else:
            flags[i][j] = True
            reachable = 1
            n_black = 0
            n_white = 0
            if board[i][j] == black:
                n_black = 1
            else:
                n_white = 1
            visit = []
            for dx, dy in deltas:
                ni = i + dx
                nj = j + dy
                if \
                ni >= 0 \
                and ni < H \
                and nj >= 0 \
                and nj < W \
                and has_alternative_around[ni][nj] is True \
                and board[i][j] != board[ni][nj] \
                and flags[ni][nj] is False:
                    visit.append( (ni, nj) )
                    flags[ni][nj] = True
                    reachable += 1
                    if board[ni][nj] == black:
                        n_black += 1
                    else:
                        n_white += 1
            while len(visit) != 0:
                visit_info = visit.pop()
                prev_i = visit_info[0]
                prev_j = visit_info[1]
                for dx, dy in deltas:
                    ni = prev_i + dx
                    nj = prev_j + dy
                    if \
                    ni >= 0 \
                    and ni < H \
                    and nj >= 0 \
                    and nj < W \
                    and has_alternative_around[ni][nj] is True \
                    and board[prev_i][prev_j] != board[ni][nj] \
                    and flags[ni][nj] is False:
                        visit.append( (ni, nj) )
                        flags[ni][nj] = True
                        reachable += 1
                        if board[ni][nj] == black:
                            n_black += 1
                        else:
                            n_white += 1
            if reachable >= 2:
                ans += n_black * n_white

print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
import sys
sys.setrecursionlimit(500000)
S = []
for i in range(H):
    S.append(input())

#white = ".", black = "#"
def search(x, y, color):
    global black
    global white
    if color == ".":
        for m in [1, -1]:
            if 0 <= x+m <= H-1:
                if S[x+m][y] == "#" and not dp[x+m][y]:
                    black += 1
                    dp[x+m][y] = True
                    color = "#"
                    search(x+m, y, color)
        for n in [1, -1]:
            if 0 <= y+n <= W-1:
                if S[x][y+n] == "#" and not dp[x][y+n]:
                    black += 1
                    dp[x][y+n] = True
                    color = "#"
                    search(x, y+n, color)

    else:
        for m in [1, -1]:
            if 0 <= x+m <= H-1:
                if S[x+m][y] == "." and not dp[x+m][y]:
                    white += 1
                    dp[x+m][y] = True
                    color = "."
                    search(x+m, y, color)

        for n in [1, -1]:
            if 0 <= y+n <= W-1:
                if S[x][y+n] == "." and not dp[x][y+n]:
                    white += 1
                    dp[x][y+n] = True
                    color = "."
                    search(x, y+n, color)


ans = 0
dp = [[False] * W for a in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j] == "#" and not dp[i][j]:
            black = 1
            white = 0
            dp[i][j] = True
            search(i, j, "#")
            ans += black * white

print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())

def getMN():
    a = input().split()
    b = [int(i) for i in a]
    return b[0],b[1]

def getlist():
    a = input().split()
    b = [int(i) for i in a]
    return b


h,w = getMN()
pos = ["."]*(w*h+5000)
cur = 1

class unionfind():
    def __init__(self,n):
        self.par = [i for i in range(n+1)]
        self.rank = [0]*(n+1)
        self.childnum = [1] * (n + 1)
        self.childb = [0 if pos[i] == "." else 1 for i in range(n+1)]

    def find(self,x):
        if self.par[x] == x:
            return x
        else:
            #print(x, ":", self.par[x])
            self.par[x] = self.find(self.par[x])
            return self.find(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
            self.childnum[y] += self.childnum[x]
            self.childb[y] += self.childb[x]

        else:
            self.par[y] = x
            self.childnum[x] += self.childnum[y]
            self.childb[x] += self.childb[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same_check(self,x,y):
        return self.find(x) == self.find(y)


for i in range(h):
    posin = input()
    for j in range(w):
        if posin[j] == "#":
            pos[j+(i)*w] = "#"

uf = unionfind(h*w+1)

unionlog = []

for i in range(h):
    for j in range(w):
        nn = j+(i)*w
        now = pos[nn]

        if j != w-1:
            nr = j + (i) * w + 1
            right = pos[nr]
            if right != now:
                if not uf.same_check(nn,nr):
                    uf.union(nn,nr)
                    unionlog.append("union:{},{}".format(nn,nr))
        if i != h-1:
            nd = j + (i + 1) * w
            down = pos[nd]
            if down != now:
                if not uf.same_check(nn,nd):
                    uf.union(nn,nd)
                    unionlog.append("union:{},{}".format(nn,nd))


a = 0
#print("\n".join(unionlog))

#print("s",uf.childnum)
#print(uf.childb)
#print([uf.find(i) for i in range(9)])
ans = 0

for parnum in list(set([uf.find(i) for i in range(h*w)])):
    #print(parnum)
    b = uf.childb[parnum]
    w = uf.childnum[parnum] - b
    #print(b,w)
    ans +=  b*w

print(ans)

Submission status: Accepted

Solution code:
def search_from(i,j):
    #print(i,j)
    if i>0:
        if visited[i-1][j] == 0:
            if map[i][j] != map [i-1][j]:
                to_visit.append((i-1,j))
                #print("append", i-1,j, "from",i,j)

    if i<h-1:
        if visited[i+1][j] == 0:
            if map[i][j] != map [i+1][j]:
                to_visit.append((i+1,j))
                #print("append", i+1,j,"from",i,j)
                
    if j>0:
        if visited[i][j-1] == 0:
            if map[i][j] != map [i][j-1]:
                to_visit.append((i,j-1))
                #print("append", i,j-1,"from",i,j)

    if j<w-1:
        if visited[i][j+1] == 0:
            if map[i][j] != map [i][j+1]:
                to_visit.append((i,j+1))
                #print("append", i,j+1,"from",i,j)

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

#print(map)

visited = [[0 for i in range(w)] for j in range(h)]

#print(visited)

to_visit = []

ans = 0
for i in range(h):
    for j in range(w):
        if visited[i][j] == 1:
            continue
        #not visited
        black = 0
        white = 0
        
        to_visit.append((i,j))
        while len(to_visit)>0:
            next = to_visit.pop()
            if visited[next[0]][next[1]] ==0:
                visited[next[0]][next[1]] = 1
                search_from(next[0],next[1])
                if map[next[0]][next[1]] =='#':
                    black += 1
                if map[next[0]][next[1]] =='.':
                    white += 1
        ans += black * white
        #print("b",black, "w",white)
        
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from collections import deque
h, w = map(int, input().split())
s = [input() for _ in range(h)]

segment = [[0]*w for _ in range(h)]
idx = 1
dxy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
for y in range(h):
    for x in range(w):
        if segment[y][x] == 0:
            segment[y][x] = idx
            state = s[y][x]
            que = deque([[y, x, state]])
            while len(que) > 0:
                y_cur, x_cur, state = que.popleft()
                for dx, dy in dxy:
                    y_next = y_cur + dy
                    x_next = x_cur + dx
                    state_next = '.' if state == '#' else '#'
                    if x_next < 0 or y_next < 0 or x_next >= w or y_next >= h:
                        continue
                    elif s[y_next][x_next] != state_next:
                        continue
                    elif segment[y_next][x_next] == 0:
                        segment[y_next][x_next] = idx
                        que.append((y_next, x_next, state_next))
            idx += 1

# print(segment)
idx_max = idx
nbw = [[0, 0] for _ in range(idx_max+1)]
for y in range(h):
    for x in range(w):
        idx = segment[y][x]
        if s[y][x] == '#':
            nbw[idx][0] += 1
        else:
            nbw[idx][1] += 1
ans = 0
for nb, nw in nbw:
    ans += nb*nw
print(ans)

Submission status: Accepted

Solution code:
def solve(H, W, Ss):
    d = [[-1 for __ in range(W)] for _ in range(H)]

    index = 0
    for (sh, sw) in [(h, w) for h in range(0, H) for w in range(0, W)]:
        if d[sh][sw] == -1:
            que = [(sh, sw)]
            index += 1
            d[sh][sw] = index

            while len(que):
                h, w = que.pop()
                for (hi, wi) in [(h + 1, w), (h - 1, w), (h, w - 1), (h, w + 1)]:
                    if 0 <= hi < H and 0 <= wi < W:
                        if Ss[hi][wi] != Ss[h][w] and d[hi][wi] == -1:
                            que.append((hi, wi))
                            d[hi][wi] = index
    c = [[0, 0] for _ in range(index + 1)]
    for h in range(0, H):
        for w in range(0, W):
            if Ss[h][w] == ".":
                c[d[h][w]][0] += 1
            elif Ss[h][w] == "#":
                c[d[h][w]][1] += 1
    ans = sum([b * w for (w, b) in c])
    return ans

if __name__ == "__main__":
    H, W = tuple(map(int, input().split(" ")))
    Ss = list([input() for l in range(H)])
    print(solve(H, W, Ss))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(400*400*1000)
from collections import Counter
def rec(union_id, i, j):
    symbol = S[i][j]
    if union_white[i][j] != 0:
        return
    if symbol == '.':
        union_white[i][j] = union_id
        next_symbol = '#'
    else:
        union_white[i][j] = -1
        next_symbol = '.'
        union_black[union_id] += 1

    if i >= 1 and S[i-1][j] == next_symbol:
        rec(union_id, i-1, j)
    if i < H-1 and S[i+1][j] == next_symbol:
        rec(union_id, i+1, j)
    if j >= 1 and S[i][j-1] == next_symbol:
        rec(union_id, i, j-1)
    if j < W-1 and S[i][j+1] == next_symbol:
        rec(union_id, i, j+1)

    return
H, W = map(int, input().split())
S = [input() for h in range(H)]
ans = 0
union_white = [[0 for w in range(W)]for h in range(H)]
union_black = Counter()
count_black = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '.' or union_white[i][j] != 0:
            continue
        count_black += 1
        rec(count_black, i, j)

counter = Counter([x for Si in union_white for x in Si])
ans = 0
# print(counter)
# print(union_black)
# print(union_white)
for i in union_black.keys():
    ans += counter[i] * union_black[i]

print(ans)

Submission status: Accepted

Solution code:
import itertools
import sys
sys.setrecursionlimit(1000000)
h, w = map(int, input().split())
s_list = []
for i in range(h):
  s_list.append(list(input()))
res = 0
check_list = set()

def rec_create_area(point, tmp_area, current_str):
  new_point_list = []
  new_point_list.append((point[0] + 1, point[1]))
  new_point_list.append((point[0], point[1] + 1))
  new_point_list.append((point[0] - 1, point[1]))
  new_point_list.append((point[0], point[1] - 1))
  for new_point in new_point_list:
    if new_point[0] >= h or new_point[1] >= w or new_point[0] < 0 or new_point[1]  < 0:
      continue
    if new_point in check_list:
      continue
    new_str = s_list[new_point[0]][new_point[1]]
    if new_str == current_str:
      continue
    if new_str == "#":
      tmp_area[0] += 1
    else:
      tmp_area[1] += 1
    check_list.add(new_point)
    rec_create_area(new_point, tmp_area, new_str)
  
for a, b in itertools.product(range(h), range(w)):
  check_point = (a, b)
  if check_point in check_list:
    continue
  check_list.add(check_point)
  current_str = s_list[check_point[0]][check_point[1]]
  if current_str == "#":
    tmp_area = [1, 0]
  else:
    tmp_area = [0, 1]
  rec_create_area(check_point, tmp_area, current_str)
  res += tmp_area[0] * tmp_area[1]
  
print(res)

Submission status: Accepted

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

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

mask = ["".join(["#" if (i + j) % 2 else "." for j in range(W)]) for i in range(H)]

masked_S = [[1 if S[i][j] == mask[i][j] else 0 for j in range(W)] for i in range(H)]

S_colored = [[-1 for j in range(W)] for i in range(H)]

color_count = dict()


def fill(i, j, color):
    S_colored[i][j] = color

    if S[i][j] == "#":
        color_count[color][0] += 1
    else:
        color_count[color][1] += 1

    for yx in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
        dy, dx = yx
        i2, j2 = i + dy, j + dx

        if i2 < 0 or i2 >= H or j2 < 0 or j2 >= W:
            continue

        if S_colored[i2][j2] != -1:
            continue

        if masked_S[i2][j2] != masked_S[i][j]:
            continue

        fill(i2, j2, color)


def main():
    color = -1
    for i in range(H):
        for j in range(W):
            if S_colored[i][j] != -1:
                continue
            color += 1
            color_count[color] = [0, 0]
            fill(i, j, color)

    result = 0
    for k in color_count.keys():
        result += color_count[k][0] * color_count[k][1]

    print(result)

if __name__ == '__main__':
    main()