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
def input():
    return sys.stdin.readline()[:-1]
inf=float("inf")
h,w=map(int,input().split())
s=[input() for i in range(h)]
class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.weight = [0] * (n+1)


    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

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

    def diff(self, x, y):
        return self.weight[x] - self.weight[y]
uf = WeightedUnionFind(h*w)
for i in range(h):
    for j in range(w):
        if (i+1)+1<=h and s[i][j]!=s[i+1][j]:
            uf.union(i*w+j+1,(i+1)*w+j+1,0)
        if (j+1)+1<=w and s[i][j]!=s[i][j+1]:
            uf.union(i*w+j+1,i*w+j+2,0)
        if (i+1)-1>=1 and s[i][j]!=s[i-1][j]:
            uf.union(i*w+j+1,(i-1)*w+j+1,0)
        if (j+1)-1>=1 and s[i][j]!=s[i][j-1]:
            uf.union(i*w+j+1,i*w+j,0)
li=[[0,0] for i in range(h*w+1)]
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            li[uf.find(i*w+j+1)][0]+=1
        else:
            li[uf.find(i*w+j+1)][1]+=1
# print(li)
ans=0
for i in range(h):
    for j in range(w):
        ans+=li[i*w+j+1][0]*li[i*w+j+1][1]
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(1000000)
d=defaultdict(int)
dw=defaultdict(int)
n,m=map(int,input().split())
l=[]
for i in range(n):
  l.append(list(input()))
lb=[[0 for i in range(m)]for j in range(n)]
move=[[1,0],[-1,0],[0,1],[0,-1]]
def dfs(n1,n2,w,n3):
  if lb[n1][n2]!=0:
    return None
  else:
    lb[n1][n2]=n3
    if w==".":
      w1="#"
    else:
      w1="."
    for j in move:
      dx=j[0]
      dy=j[1]
      x=dx+n1
      y=dy+n2
      if 0>x or x>n-1 or y<0 or y>m-1:
        pass
      else:
        if w1!=l[x][y]:
          pass
        else:
          dfs(x,y,w1,n3)
    return None
dfs(0,0,l[0][0],1)
num=1
for i in range(n):
  for j in range(m):
    dfs(i,j,l[i][j],num)
    num+=1
for i in range(n):
  for j in range(m):
    d[lb[i][j]]+=1
    if l[i][j]=="#":
      dw[lb[i][j]]+=1
ans=0
for i in d:
  ans+=dw[i]*(d[i]-dw[i])
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

S = []

for i in range(H):

    s = input()

    S.append(s)

lis = [ [True] * W for i in range(H) ]

ans = 0

for h in range(H):

    for w in range(W):

        if not lis[h][w]:
            continue
        
        q = deque([[h,w]])
        lis[h][w] = False

        if S[h][w] == "#":
            bnum = 1
            wnum = 0
        else:
            bnum = 0
            wnum = 1

        while len(q) > 0:

            now = q.popleft()
            nh = now[0]
            nw = now[1]

            if S[nh][nw] == "#":

                if nh > 0 and S[nh-1][nw] == "." and lis[nh-1][nw]:

                    wnum += 1
                    lis[nh-1][nw] = False
                    q.append([nh-1,nw])

                if nh < H-1 and S[nh+1][nw] == "." and lis[nh+1][nw]:

                    wnum += 1
                    lis[nh+1][nw] = False
                    q.append([nh+1,nw])

                if nw > 0 and S[nh][nw-1] == "." and lis[nh][nw-1]:

                    wnum += 1
                    lis[nh][nw-1] = False
                    q.append([nh,nw-1])

                if nw < W-1 and S[nh][nw+1] == "." and lis[nh][nw+1]:

                    wnum += 1
                    lis[nh][nw+1] = False
                    q.append([nh,nw+1])

            if S[nh][nw] == ".":

                if nh > 0 and S[nh-1][nw] == "#" and lis[nh-1][nw]:

                    bnum += 1
                    lis[nh-1][nw] = False
                    q.append([nh-1,nw])

                if nh < H-1 and S[nh+1][nw] == "#" and lis[nh+1][nw]:

                    bnum += 1
                    lis[nh+1][nw] = False
                    q.append([nh+1,nw])

                if nw > 0 and S[nh][nw-1] == "#" and lis[nh][nw-1]:

                    bnum += 1
                    lis[nh][nw-1] = False
                    q.append([nh,nw-1])

                if nw < W-1 and S[nh][nw+1] == "#" and lis[nh][nw+1]:

                    bnum += 1
                    lis[nh][nw+1] = False
                    q.append([nh,nw+1])
                    
        ans += wnum * bnum


print (ans)

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int,input().split())
S = [input() for i in range(H)]
ans = 0
flag = [[0]*W for i in range(H)]
for i in range(H*W):
    x,y = i%W,i//W
    if flag[y][x] == 1:
        continue
    flag[y][x] = 1
    bw = [0,0]
    bw[[".","#"].index(S[y][x])]+=1
    queue = deque([[x,y]])
    while queue:
        x,y = queue.popleft()
        for a,b in [[-1,0],[1,0],[0,1],[0,-1]]:
            if 0<=x+a<W and 0<=y+b<H and flag[y+b][x+a] == 0 and S[y][x] != S[y+b][x+a]:
                queue.append([x+a,y+b])
                flag[y+b][x+a] = 1
                bw[[".","#"].index(S[y+b][x+a])]+=1
    ans += bw[0]*bw[1]
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools

import queue
from collections import deque

def check(x, y, now_add, color, high, width):
    global data
    move_dic = [(1, 0), (0, 1)]
    for move_x, move_y in move_dic:
        next_x = x + move_x
        next_y = y + move_y
        if 0 <= next_x < high and 0 <= next_y < width:
            if data[next_x][next_y] == 0:
                continue
            if data[next_x][next_y] != data[x][y]:
                now_add.add((i, j))
                color[data[next_x][next_y]] += 1
                check(next_x, next_y, now_add, color, high, width)


def main():
    high, width = map(int, input().split())
    data = [list(input()) for i in range(high)]

    ans = 0
    move_dic = [[1, 0], [0, 1], [-1, 0], [0, -1]]

    for i in range(high):
        for j in range(width):
            if data[i][j] == 0:
                continue

            all_ele = set()
            now_ele = set()
            next_ele = set()
            count = defaultdict(int)

            now_ele.add((i, j))
            all_ele.add((i, j))
            count[data[i][j]] += 1

            while len(now_ele) > 0:
                for x, y in now_ele:
                    for move_x, move_y in move_dic:
                        next_x = x + move_x
                        next_y = y + move_y
                        if 0 <= next_x < high and 0 <= next_y < width:
                            if data[next_x][next_y] == 0 or (next_x, next_y) in all_ele:
                                continue
                            if data[next_x][next_y] != data[x][y]:
                                next_ele.add((next_x, next_y))
                                all_ele.add((next_x, next_y))
                                count[data[next_x][next_y]] += 1
                now_ele = next_ele
                next_ele = set()

            ans += count['.'] * count['#']
            for x, y in all_ele:
                data[x][y] = 0

    print(ans)




if __name__ == '__main__':
    main()
    # test()

Submission status: Accepted

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

visited = [[0]*w for i in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        black = 0
        white = 0
        stack = [[i,j]]
        while stack:
            a,b = stack.pop()
            if visited[a][b]!=1:
                visited[a][b]+=1
                if s[a][b]=='#':
                    black+=1
                else:
                    white+=1
                for x,y in [[1,0],[-1,0],[0,1],[0,-1]]:
                    c = a+y
                    d = b+x
                    if 0<=c<h and 0<=d<w:
                        if s[a][b]!=s[c][d]:
                            stack.append([c,d])
        ans += black*white
print(ans)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
S=[[int(c=='#') for c in input()] for i in range(H)]
v=[[0]*W for i in range(H)]
r=0
def bfs(p,x,y,c,b):
    while 1:
        c^=1
        q=set()
        for h,w in p:
            v[h][w]=1
            if h>0 and not v[h-1][w] and S[h-1][w]==c:
                q.add((h-1,w))
            if w>0 and not v[h][w-1] and S[h][w-1]==c:
                q.add((h,w-1))
            if h<H-1 and not v[h+1][w] and S[h+1][w]==c:
                q.add((h+1,w))
            if w<W-1 and not v[h][w+1] and S[h][w+1]==c:
                q.add((h,w+1))
        if not q:
            return x*y
        if b:
            x+=len(q)
        else:
            y+=len(q)
        b^=1
        p=q
for h in range(H):
    for w in range(W):
        if v[h][w]==0:
            r+=bfs([(h,w)],1,0,S[h][w],0)
print(r)

Submission status: Accepted

Solution code:
from collections import Counter

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


 
class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

uf = UnionFind(H*W)

for i in range(H):
    for j in range(W):
        
        # 横
        if j != W-1 and S[i][j] != S[i][j+1]:
            uf.unite(i*W+j, i*W+j+1)
        
        # 縦
        if i != H-1 and S[i][j] != S[i+1][j]:
            uf.unite(i*W+j, (i+1)*W+j)

for i in range(H*W):
    uf.root(i)

black = Counter()
white = Counter()

#あるユニオンに所属（#.#.の移動できる塊）の#と.の数を数える
for i in range(H):
    for j in range(W):
        k = i*W+j
        if S[i][j] == "#":
            black[uf.root(k)] += 1
        else:
            white[uf.root(k)] += 1

#ユニオンごとに足し合わせ
ans = 0
for k in black.keys():
    ans += black[k] * white[k]

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

es = defaultdict(list)
for i in range(H):
    for j in range(W):
        # 横
        if j != W-1 and S[i][j] != S[i][j+1]:
            es[(i,j)].append((i,j+1))
            es[(i,j+1)].append((i,j))

        # 縦
        if i != H-1 and S[i][j] != S[i+1][j]:
            es[(i,j)].append((i+1,j))
            es[(i+1,j)].append((i,j))


ans = 0
checked = [[False for _ in range(W)] for _ in range(H)]

stack  = es.keys()
for i,j in stack:
    # 開始位置
    if checked[i][j]:
        continue
    
    if S[i][j] == "#":
        cnt_b = 1
        cnt_w = 0
    else:
        cnt_b = 0
        cnt_w = 1


    checked[i][j] = True
    ns = es[(i,j)]
    #tmp = []
    while ns:
        tmp = []
        for a,b in ns:
            if checked[a][b] == True: continue

            checked[a][b] = True
            if S[a][b] == "#":
                cnt_b += 1
            else:
                cnt_w += 1

            for c,d in es[(a,b)]:
                if not checked[c][d]:
                    tmp.append((c,d))
        if len(tmp) > 0:
            ns = tmp
        else:
            ns = []            
    ans += cnt_b * cnt_w


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)]

q=deque()
ans=0

def bfs(i,j):
    global ans
    white=0
    black=0
    q.append((i,j))
    while q:
        y,x=q.popleft()
        if s[y][x]=='#':
            black+=1
        if s[y][x]=='.':
            white+=1
        for dy,dx in ((1,0),(0,1),(-1,0),(0,-1)):
            ny = y+dy
            nx = x+dx
            if 0<=ny<h and 0<=nx<w and s[y][x]!=s[ny][nx] and field[ny][nx]==False:
                field[ny][nx]=True
                q.append((ny,nx))
    ans+=(black*white)

field=[[False]*w for j in range(h)]                         
for i in range(h):
    for j in range(w):
        if s[i][j]=='.' and field[i][j]==False:
            field[i][j]=True
            bfs(i,j)

print(ans)

Submission status: Accepted

Solution code:

def main():
    H, W = map(int, input().split())
    state = [list(input()) for _ in range(H)]
    checked = [[False]*W for _ in range(H)]

    ans = 0
    for h in range(H):
        for w in range(W):
            if checked[h][w]:   continue
            q = [(h, w)]
            score = [0, 0]
            checked[h][w] = True
            c = 0
            while q:
                score[c%2] += len(q)
                qq = []
                for ph, pw in q:
                    nexts = []
                    if ph != 0: nexts.append((ph-1, pw))
                    if ph != H-1: nexts.append((ph+1, pw))
                    if pw != 0: nexts.append((ph, pw-1))
                    if pw != W-1: nexts.append((ph, pw+1))
                    for nh, nw in nexts:
                        if state[nh][nw] != state[ph][pw] and not checked[nh][nw]:
                            checked[nh][nw] = True
                            qq.append((nh, nw))
                c += 1
                q = qq
            ans += score[0]*score[1]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

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

S = [input() for _ in range(H)]




es = defaultdict(list)
# あるマスについて左右見なくても右に向かってみていけば逆もとれる
for i in range(H):
    for j in range(W):
        if j < W-1 and S[i][j] != S[i][j+1]:
            es[(i,j)].append((i,j+1))
            es[(i,j+1)].append((i,j))
        if i < H-1 and S[i][j] != S[i+1][j]:
            es[(i,j)].append((i+1, j))
            es[(i+1,j)].append((i, j))

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


ans = 0
for i in range(H):
    for j in range(W):
        if checked[i][j] == True:
            continue
        
        cnt_b = 0
        cnt_w = 0

        if S[i][j] == "#":
            cnt_b += 1
        else:
            cnt_w += 1
        checked[i][j] = True
        stack = es[(i,j)]

        while stack:
            new_stack = []
            for p,q in stack:
                if checked[p][q] == False:
                    checked[p][q] = True
                    if S[p][q] == "#":
                        cnt_b += 1
                    else:
                        cnt_w += 1

                    new_stack.extend(es[(p,q)])
            if len(new_stack) == 0:
                break
            else:
                stack = new_stack
        
        ans += cnt_b * cnt_w

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

S = [input() for _ in range(H)]




es = defaultdict(list)
for i in range(H):
    for j in range(W):

        # 縦の経路
        if i == 0 and H != 1:
            if S[i][j] != S[i+1][j]:
                es[(i,j)].append((i+1,j))
                es[(i+1,j)].append((i,j))
        elif 0 < i < H-1:
                if S[i][j] != S[i+1][j]:
                    es[(i,j)].append((i+1,j))
                    es[(i+1,j)].append((i,j))
                if S[i][j] != S[i-1][j]:
                    es[(i,j)].append((i-1,j))
                    es[(i-1,j)].append((i,j))
        elif i == H-1 and H != 1:
                if S[i][j] != S[i-1][j]:
                    es[(i,j)].append((i-1,j))
                    es[(i-1,j)].append((i,j))

        # 横の経路
        if j == 0 and W != 1:
            if S[i][j] != S[i][j+1]:
                es[(i,j)].append((i,j+1))
                es[(i,j+1)].append((i,j))
        elif 0 < j < W-1:
            if S[i][j] != S[i][j+1]:
                es[(i,j)].append((i,j+1))
                es[(i,j+1)].append((i,j))
                if S[i][j] != S[i][j-1]:
                    es[(i,j)].append((i,j-1))
                    es[(i,j-1)].append((i,j))
        elif j == W-1 and W != 1:
                if S[i][j] != S[i][j-1]:
                    es[(i,j)].append((i,j-1))
                    es[(i,j-1)].append((i,j))

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


ans = 0
for i in range(H):
    for j in range(W):
        if checked[i][j] == True:
            continue
        
        cnt_b = 0
        cnt_w = 0

        if S[i][j] == "#":
            cnt_b += 1
        else:
            cnt_w += 1
        checked[i][j] = True
        stack = es[(i,j)]

        while stack:
            new_stack = []
            for p,q in stack:
                if checked[p][q] == False:
                    checked[p][q] = True
                    if S[p][q] == "#":
                        cnt_b += 1
                    else:
                        cnt_w += 1

                    new_stack.extend(es[(p,q)])
            if len(new_stack) == 0:
                break
            else:
                stack = new_stack
        
        ans += cnt_b * cnt_w

print(ans)

Submission status: Accepted

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions

import sys
def input():
	return sys.stdin.readline().strip()

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

tansaku = [[0]*W for _ in range(H)]
total = 0
for i in range(H):
	for j in range(W):
		if tansaku[i][j] == 0 and G[i][j] == '#':
			tansaku[i][j] = 1
			black = 1
			white = 0
			que = deque([])
			que.append((i, j))
			delta = ((0, 1), (0, -1), (1, 0), (-1, 0))
			while len(que) > 0:
				loc = que.popleft()

				for d in range(4):
					x = loc[0] + delta[d][0]
					y = loc[1] + delta[d][1]
					if x >= H or y >= W or x < 0 or y < 0:
						continue

					if tansaku[x][y] == 0:
						if G[loc[0]][loc[1]] == '#' and G[x][y] == '.':
							white += 1
							tansaku[x][y] = 1
							que.append((x, y))
							#print((x, y), loc)
						elif G[loc[0]][loc[1]] == '.' and G[x][y] == '#':
							black += 1
							tansaku[x][y] = 1
							que.append((x, y))
							#print((x, y), loc, 1)
			total += black*white
			#print(i, j, black, white)
print(total)

Submission status: Accepted

Solution code:
# aising2019C - Alternating Path
def dfs(sx: int, sy: int) -> None:
    color, stack = [0] * 2, [(sx, sy, S[sx][sy])]
    S[sx][sy] = 2  # make the grid visited
    while stack:
        x, y, col = stack.pop()
        color[col] += 1
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == col ^ 1:
                stack.append((nx, ny, S[nx][ny]))
                S[nx][ny] = 2  # make the grid visited
    return color[0] * color[1]


def main():
    # separate S to connected components
    global H, W, S, dxy
    H, W, *S = open(0).read().split()
    H, W = int(H), int(W)
    S = [[1 if i == "#" else 0 for i in s] for s in S]
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    ans = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] != 2:
                ans += dfs(i, j)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# aising2019C - Alternating Path
def dfs(sx: int, sy: int) -> None:
    color = [0] * 2
    s_col = S[sx][sy]
    color[s_col] += 1
    S[sx][sy] = 2  # make the grid visited
    stack = [(sx, sy, s_col)]
    while stack:
        x, y, col = stack.pop()
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == col ^ 1:
                stack.append((nx, ny, S[nx][ny]))
                color[S[nx][ny]] += 1
                S[nx][ny] = 2
    return color[0] * color[1]


def main():
    # separate S to connected components
    global H, W, S, dxy, blk, wht
    H, W, *S = open(0).read().split()
    H, W = int(H), int(W)
    S = [[1 if i == "#" else 0 for i in s] for s in S]
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    ans = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] != 2:
                ans += dfs(i, j)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# aising2019C - Alternating Path
def dfs(sx: int, sy: int) -> None:
    color = [0] * 2
    s_col = S[sx][sy]
    color[s_col] += 1
    S[sx][sy] = 2  # make the grid visited
    stack = [(sx, sy, s_col)]
    while stack:
        x, y, col = stack.pop()
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == col ^ 1:
                n_col = S[nx][ny]
                stack.append((nx, ny, n_col))
                color[n_col] += 1
                S[nx][ny] = 2
    return color[0] * color[1]


def main():
    # separate S to connected components
    global H, W, S, dxy, blk, wht
    H, W, *S = open(0).read().split()
    H, W = int(H), int(W)
    S = [[1 if i == "#" else 0 for i in s] for s in S]
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    ans = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] != 2:
                ans += dfs(i, j)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# aising2019C - Alternating Path
import sys

sys.setrecursionlimit(10 ** 9)


def dfs(x: int, y: int) -> None:
    global blk, wht
    cur = S[x][y]
    S[x][y] = 2  # make the grid visited
    if cur:
        blk += 1
    else:
        wht += 1
    for dx, dy in dxy:
        nx, ny = x + dx, y + dy
        if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == cur ^ 1:
            dfs(nx, ny)


def main():
    # separate S to connected components
    global H, W, S, dxy, blk, wht
    H, W, *S = open(0).read().split()
    H, W = int(H), int(W)
    S = [[1 if i == "#" else 0 for i in s] for s in S]
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    ans = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] != 2:
                blk, wht = 0, 0
                dfs(i, j)
                ans += blk * wht
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# aising2019C - Alternating Path
import sys

sys.setrecursionlimit(10 ** 9)


def dfs(x: int, y: int) -> None:
    global blk, wht
    seen[x][y] = 1
    cur = S[x][y]
    if cur:
        blk += 1
    else:
        wht += 1
    for dx, dy in dxy:
        nx, ny = x + dx, y + dy
        if 0 <= nx < H and 0 <= ny < W and S[nx][ny] != cur and not seen[nx][ny]:
            dfs(nx, ny)


def main():
    # separate S to connected components
    global H, W, S, seen, dxy, blk, wht
    H, W, *S = open(0).read().split()
    H, W = int(H), int(W)
    S = [[1 if i == "#" else 0 for i in s] for s in S]
    seen = [[0] * W for _ in range(H)]
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    ans = 0
    for i in range(H):
        for j in range(W):
            if not seen[i][j]:
                blk, wht = 0, 0
                dfs(i, j)
                ans += blk * wht
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# aising2019C - Alternating Path
import sys

sys.setrecursionlimit(10 ** 9)


def dfs(x: int, y: int) -> None:
    global blk, wht
    seen[x][y] = 1
    cur = S[x][y]
    if cur == "#":
        blk += 1
    else:
        wht += 1
    for dx, dy in dxy:
        nx, ny = x + dx, y + dy
        if 0 <= nx < H and 0 <= ny < W and S[nx][ny] != cur and not seen[nx][ny]:
            dfs(nx, ny)


def main():
    # separate S to connected components
    global H, W, S, seen, dxy, blk, wht
    H, W, *S = open(0).read().split()
    H, W = int(H), int(W)
    seen = [[0] * W for _ in range(H)]
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    ans = 0
    for i in range(H):
        for j in range(W):
            if not seen[i][j]:
                blk, wht = 0, 0
                dfs(i, j)
                ans += blk * wht
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def solve(H, W, grid):
    from collections import deque
    groups = [[0] * W for h in range(H)]
    v = 0 
    def search(M, h0, w0):
        nonlocal v
        count = [0, 0]
        Q = [(h0, w0)]
        groups[h0][w0] = M
        v+=1
        while Q:
            (h, w) = Q.pop()
            c = 1 - grid[h][w]
            count[1-c] += 1
            if h < H-1:
                if groups[h+1][w] == 0:
                    if grid[h+1][w] == c:
                        groups[h+1][w] = M
                        v += 1
                        Q.append((h+1, w))
                    else:
                        q.append((h+1, w))
            if h > 0:
                if groups[h-1][w] == 0:
                    if grid[h-1][w] == c:
                        groups[h-1][w] = M
                        v += 1
                        Q.append((h-1, w))
                    else:
                        q.append((h-1, w))
            if w > 0:
                if groups[h][w-1] == 0:
                    if grid[h][w-1] == c:
                        groups[h][w-1] = M
                        v += 1
                        Q.append((h, w-1))
                    else:
                        q.append((h, w-1))
            if w < W-1:
                if groups[h][w+1] == 0:
                    if grid[h][w+1] == c:
                        groups[h][w+1] = M
                        v += 1
                        Q.append((h, w+1))
                    else:
                        q.append((h, w+1))
        #print("search(%d,%d): %s"%(h0, w0, count))
        return count

    answer = 0
    m = 0
    q = deque()
    q.append((0,0))
    while q:
        h, w = q.pop()
        if groups[h][w] == 0:
            m+=1
            b, w = search(m, h, w)
            answer += b * w
    #for h in range(H): print(*groups[h])
    return answer

def main():
    import sys
    input = sys.stdin.readline
    H, W = map(int, input().split())

    grid = [[0]]*H
    for i in range(H):
        grid[i] = [1 if c == '#' else 0 for c in input().rstrip()]
    print(solve(H, W, grid))

main()

Submission status: Accepted

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

h,w = map(int, input().split())
board = [[int(j=="#") for j in input()] for i in range(h)]
dxdy = [(0,1), (0,-1), (1,0), (-1,0)]

def dfs(i, j, k, prev):
    if used[i][j] or board[i][j] == prev:
        return
    used[i][j] = 1
    k[board[i][j]] += 1
    for dx, dy in dxdy:
        nx, ny = i+dx, j+dy
        if 0 <= nx < h and 0 <= ny < w and not used[nx][ny] and board[nx][ny] != board[i][j]:
            dfs(nx,ny,k,board[i][j])

used = [[0]*w for i in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if used[i][j]:
            continue
        k = [0]*2
        dfs(i,j,k, -1)
        ans += k[0]*k[1]
print(ans)

Submission status: Accepted

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

h,w = map(int, input().split())
board = [[int(j=="#") for j in input()] for i in range(h)]
dxdy = ((0,1), (0,-1), (1,0), (-1,0))

def dfs(i, j, k, prev):
    if used[i][j] or board[i][j] == prev:
        return
    used[i][j] = 1
    k[board[i][j]] += 1
    for dx, dy in dxdy:
        nx, ny = i+dx, j+dy
        if 0 <= nx < h and 0 <= ny < w and not used[nx][ny] and board[nx][ny] != board[i][j]:
            dfs(nx,ny,k,board[i][j])

used = [[0]*w for i in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if used[i][j]:
            continue
        k = [0]*2
        dfs(i,j,k, -1)
        ans += k[0]*k[1]
print(ans)

Submission status: Accepted

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

h,w = map(int, input().split())
board = [[int(j=="#") for j in input()] for i in range(h)]
dxdy = [[0,1], [0,-1], [1,0], [-1,0]]

def dfs(i, j, k, prev):
    if used[i][j] or board[i][j] == prev:
        return
    used[i][j] = 1
    k[board[i][j]] += 1
    for dx, dy in dxdy:
        nx, ny = i+dx, j+dy
        if 0 <= nx < h and 0 <= ny < w and not used[nx][ny] and board[nx][ny] != board[i][j]:
            dfs(nx,ny,k,board[i][j])

used = [[0]*w for i in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if used[i][j]:
            continue
        k = [0]*2
        dfs(i,j,k, -1)
        ans += k[0]*k[1]
print(ans)