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
input = sys.stdin.readline


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


def main():
    H, W = map(int, input().split())
    S = []
    for h in range(H):
        S.append(input().strip())

    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))
    D = {}
    for i in range(H):
        for j in range(W):
            r = uf.find(i*W+j)
            if r not in D:
                D[r] = [0, 0]
            if S[i][j] == "#":
                D[r][0] += 1
            else:
                D[r][1] += 1
    ans = 0
    for d in D.values():
        ans += d[0]*d[1]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

remaining = set()
for i in range(H):
    for j in range(W):
        remaining.add((i, j))

q = collections.deque()
ans = 0
while(remaining):
    i, j = remaining.pop()
    q.append((i, j))
    black = 0
    white = 0
    while(q):
        y, x = q.popleft()
        if S[y][x] == "#":
            black += 1
        else:
            white += 1

        if (y-1, x) in remaining and S[y][x] != S[y-1][x]:
            remaining.remove((y-1, x))
            q.append((y-1, x))
        if (y, x-1) in remaining and S[y][x] != S[y][x-1]:
            remaining.remove((y, x-1))
            q.append((y, x-1))
        if (y+1, x) in remaining and S[y][x] != S[y+1][x]:
            remaining.remove((y+1, x))
            q.append((y+1, x))
        if (y, x+1) in remaining and S[y][x] != S[y][x+1]:
            remaining.remove((y, x+1))
            q.append((y, x+1))
    ans += black * white
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

S=[]
for i in range(H):
    S.append([c=='#' for c in input()]) # 黒をTrueとする
# print(S)

a=[[[] for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        if 0<i and (S[i][j] ^ S[i-1][j]):
            a[i][j].append((i-1,j))
        if i<H-1 and (S[i][j] ^ S[i+1][j]):
            a[i][j].append((i+1,j))
        if 0<j and (S[i][j] ^ S[i][j-1]):
            a[i][j].append((i,j-1))
        if j<W-1 and (S[i][j] ^ S[i][j+1]):
            a[i][j].append((i,j+1))
'''
for ai in a:
    print(ai)
'''
ans=0
q=deque()
r=[[False for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        if not r[i][j]:
            b,w=0,0
            q.append((i,j));r[i][j]=True
            if S[i][j]:
                b+=1
            else:
                w+=1
            while q:
                ui,uj=q.popleft()
                for v in a[ui][uj]:
                    vi,vj=v
                    if not r[vi][vj]:
                        q.append((vi,vj));r[vi][vj]=True
                        if S[vi][vj]:
                            b+=1
                        else:
                            w+=1
            ans+=b*w
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

check = [[1 for _ in range(W)] for _ in range(H)]

def bw(s):
  if s == "#":
    return "."
  else:
    return "#"

def cnt_plus(s, cnt):
  if s == "#":
    c = [cnt[0] + 1, cnt[1]]
  else:
    c = [cnt[0], cnt[1] + 1]
  return c
  
def bfs(i, j):
  stack = deque()
  stack.append(((i, j), S[i][j]))
  check[i][j] = 0
  cnt = [0, 0]
  
  while stack:
    p, s = stack.popleft()
    cnt = cnt_plus(s, cnt)
    ii, jj = p
    bws = bw(s)

    if ii - 1 >= 0 and check[ii - 1][jj]:
      if S[ii - 1][jj] == bws:
        check[ii - 1][jj] = 0
        stack.append(((ii - 1, jj), bws))

    if ii + 1 < H and check[ii + 1][jj]:
      if S[ii + 1][jj] == bws:
        check[ii + 1][jj] = 0
        stack.append(((ii + 1, jj), bws))

    if jj - 1 >= 0 and check[ii][jj - 1]:
      if S[ii][jj - 1] == bws:
        check[ii][jj - 1] = 0
        stack.append(((ii, jj - 1), bws))

    if jj + 1 < W and check[ii][jj + 1]:
      if S[ii][jj + 1] == bws:
        check[ii][jj + 1] = 0
        stack.append(((ii, jj + 1), bws))
  return cnt[0] * cnt[1]

answer = 0
for i in range(H):
  for j in range(W):
    if check[i][j] and S[i][j] == "#":
      answer += bfs(i, j)
print(answer)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
grid = [[1 if i == "#" else 0 for i in input()] for _ in range(h)]
seen = [[0] * w for _ in range(h)]
DX = (0, 1, 0, -1)
DY = (1, 0, -1, 0)
ans = 0


def dfs(X, Y, cnt):
    todo = [(X, Y)]
    seen[X][Y] = cnt
    black = 0
    white = 1
    while todo:
        x, y = todo.pop()
        now = grid[x][y]
        for dx, dy in zip(DX, DY):
            nx = x + dx
            ny = y + dy
            if nx < 0 or ny < 0 or nx >= h or ny >= w:  # インデックスが範囲外ならだめ
                continue
            if seen[nx][ny] == cnt or now == grid[nx][ny]:  # 既に見ていたり、白-白、黒-黒ならばだめ
                continue
            if 1-now:  # 現在位置が白色の場合
                black += 1
            else:
                white += 1
            seen[nx][ny] = cnt
            todo.append((nx, ny))
    return black*white


cnt = 1
for i in range(h):
    for j in range(w):
        if grid[i][j] or seen[i][j]:
            continue
        ans += dfs(i, j, cnt)
        cnt += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
h, w = [int(i) for i in sys.stdin.readline().split()]
s_ls = []
bl_ls = []
for i in range(h):
    s = [1 if i == "#" else -1 for i in sys.stdin.readline().strip()]
    for j, k in enumerate(s):
        if k == 1:
            bl_ls.append((i, j))
    s_ls.append(s)

memo_ls = dict()
def dfs(y, x, col):
    if (y, x) in memo_ls:
        return memo_ls[(y, x)]
    res = 0
    if col == -1:
        res += 1
    already.add((y, x))
    for move_y, move_x in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        next_y = y + move_y
        next_x = x + move_x
        if 0 <= next_x < w and 0 <= next_y < h and s_ls[next_y][next_x] == (-1) * col and (next_y, next_x) not in already:
            res += dfs(next_y, next_x, (-1) * col)
    return res

ans = 0
for bl in bl_ls:
    already = set()
    stack = [(bl[0], bl[1], 1, 0)]
    cnt = 0
    while len(stack) > 0:
        y, x, col, _sum = stack.pop(-1)
        if (y, x) in memo_ls:
            cnt = memo_ls[(y, x)]
            break
        if col == -1:
            cnt += 1
        already.add((y, x))
        for move_y, move_x in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            next_y = y + move_y
            next_x = x + move_x
            if 0 <= next_x < w and 0 <= next_y < h and s_ls[next_y][next_x] == (-1) * col and (
            next_y, next_x) not in already:
                stack.append((next_y, next_x, (-1) * col, _sum))
                already.add((next_y, next_x))
    res = cnt
    ans += res
    for al in list(already):
        memo_ls[al] = res
print(ans)

Submission status: Accepted

Solution code:
class UnionFindTree:
    """Disjoint-Set Data Structure
       Union-Find Tree
       complexity:
          init: O(n)
          find, unite, same: O(alpha(n))
       used in SRM505 div.2 900, ATC001 A, DSL1A(AOJ)
    """
    def __init__(self, n):
        self.par = list(range(n))  # parent
        self.rank = [0] * n  # depth of tree

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

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

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

H, W = map(int, input().split())
uft = UnionFindTree(H * W)
board = [input() for _ in range(H)]
drc = [(1, 0), (0, 1)]
for r in range(H):
    for c in range(W):
        if r < H - 1 and board[r + 1][c] != board[r][c]:
            uft.unite(r * W + c, (r + 1) * W + c)
        if c < W - 1 and board[r][c + 1] != board[r][c]:
            uft.unite(r * W + c, r * W + c + 1)
par_dict_w, par_dict_b = dict(), dict()
for r in range(H):
    for c in range(W):
        par = uft.find(r * W + c)
        if board[r][c] == "#":
            par_dict_b[par] = par_dict_b.get(par, 0) + 1
        else:
            par_dict_w[par] = par_dict_w.get(par, 0) + 1
print(sum(par_dict_w[k] * par_dict_b.get(k, 0) for k in par_dict_w.keys()))

Submission status: Accepted

Solution code:
h, w = map(int ,input().split())
s = [list(input()) for _ in range(h)]
check = [[0] * w for _ in range(h)]
move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
ans = 0

for i in range(h):
    for j in range(w):
        if check[i][j] == 1:
            continue
        black, white = 0, 0 

        stack = [[i, j]]
        check[i][j] = 1
        if s[i][j] == '#':
            black += 1
        else:
            white += 1

        while len(stack) > 0:
            x, y = stack.pop()
            tmp = s[x][y]
            for dx, dy in move:
                nx, ny = x + dx, y + dy
                if 0 <= nx < h and 0 <= ny < w and tmp != s[nx][ny] and check[nx][ny] == 0:
                    stack.append([nx, ny])
                    check[nx][ny] = 1
                    if s[nx][ny] == '#':
                        black += 1
                    else:
                        white += 1

        ans += black * white

print(ans)

# %%

Submission status: Accepted

Solution code:
import sys
from collections import deque

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

def bfs(x, y, c):
    global data
    
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    que = deque()
    que.append(((x, y), c))
    data[y][x] = 'visited'
    black = 1
    white = 0

    while que:
        p, color = que.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            next_color = '#' if color == '.' else '.'            
            if 0 <= ny and ny <= H-1 and 0 <= nx and nx <= W-1 and \
                    data[ny][nx] == next_color:
                data[ny][nx] = 'visited'
                if next_color == '.':
                    white += 1
                elif next_color == '#':
                    black += 1
                que.append(((nx, ny), next_color))
    return white * black

H, W = rl()
data = [list(rs()) for _ in range(H)]
answer = 0

for y in range(H):
    for x in range(W):
        if data[y][x] == '#':
            answer += bfs(x, y, data[y][x])

print(answer)
# rest

Submission status: Accepted

Solution code:
def main():
	t, *grid = open(0)
	h, w = map(int, t.split())
	vis = [[False] * w for _ in range(h)]
	ans = 0
	for y in range(h):
		for x in range(w):
			if vis[y][x]:
				continue
			q = [(y, x, grid[y][x])]
			d = {"#": 0, ".": 0}
			while q:
				cy, cx, cc = q.pop()
				for ny, nx in ((cy + 1, cx), (cy - 1, cx), (cy, cx + 1), (cy, cx - 1)):
					if not (0 <= ny < h and 0 <= nx < w) or vis[ny][nx] or cc == grid[ny][nx]:
						continue
					nc = grid[ny][nx]
					d[nc] += 1
					vis[ny][nx] = True
					q.append((ny, nx, nc))
			ans += d["#"] * d["."]
	print(ans)

if __name__=="__main__":
	main()

Submission status: Accepted

Solution code:
def main():
	t, *grid = open(0)
	h, w = map(int, t.split())
	vis = [[False] * w for _ in range(h)]
	ans = 0
	for y in range(h):
		for x in range(w):
			if vis[y][x]:
				continue
			q = [(y, x, grid[y][x])]
			d = {"#": 0, ".": 0}
			while q:
				cy, cx, cc = q.pop(0)
				for ny, nx in ((cy + 1, cx), (cy - 1, cx), (cy, cx + 1), (cy, cx - 1)):
					if not (0 <= ny < h and 0 <= nx < w) or vis[ny][nx] or cc == grid[ny][nx]:
						continue
					nc = grid[ny][nx]
					d[nc] += 1
					vis[ny][nx] = True
					q.append((ny, nx, nc))
			ans += d["#"] * d["."]
	print(ans)

if __name__=="__main__":
	main()

Submission status: Accepted

Solution code:
t,*grid=open(0)
h,w=map(int,t.split())
vis=[[False]*w for _ in range(h)]
ans=0
for y in range(h):
	for x in range(w):
		if vis[y][x]:
			continue
		q=[(y,x)]
		d={"#":0,".":0}
		while q:
			cy,cx=q.pop(0)
			for ny,nx in ((cy+1,cx),(cy-1,cx),(cy,cx+1),(cy,cx-1)):
				if not (0<=ny<h and 0<=nx<w) or vis[ny][nx] or grid[cy][cx]==grid[ny][nx]:
					continue
				d[grid[ny][nx]]+=1
				vis[ny][nx]=True
				q.append((ny,nx))
		ans+=d["#"]*d["."]
print(ans)

Submission status: Accepted

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

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

check = [[0] * W for _ in range(H)]

ans = 0

move = [[1, 0], [-1, 0], [0, 1], [0, -1]]

for h in range(H):
    for w in range(W):
        if check[h][w] == 1:
            continue
        black = 0
        white = 0

        stack = [[h, w]]
        check[h][w] = 1
        if S[h][w] == '#':
            black += 1
        elif S[h][w] == '.':
            white += 1

        while len(stack) != 0:
            x, y = stack.pop()
            tmp = S[x][y]
            for dx, dy in move:
                nx = x + dx
                ny = y + dy
                if 0 <= nx < H and 0 <= ny < W and tmp != S[nx][ny] and check[nx][ny] == 0:
                    check[nx][ny] = 1
                    stack.append([nx, ny])
                    if S[nx][ny] == '#':
                        black += 1
                    elif S[nx][ny] == '.':
                        white += 1
        
        ans += black * white

print (ans)

Submission status: Accepted

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

ans = 0
visited = [[0]*W for _ in range(H)]
stack = []
dx = [1,0,-1,0]
dy = [0,1,0,-1]

for i in range(H):
    for j in range(W):
        b,w = 0,0
        if not visited[i][j]:
            stack.append([i,j])
            visited[i][j] = 1
            while stack:
                x,y = stack.pop()
                if S[x][y]=='#':
                    b += 1
                else:
                    w += 1
                for k in range(4):
                    nx,ny = x+dx[k],y+dy[k]
                    if not(0<=nx<H and 0<=ny<W):
                        continue
                    if not visited[nx][ny] and S[x][y]!=S[nx][ny]:
                        visited[nx][ny] = 1
                        stack.append([nx,ny])
            ans += b*w

print(ans)

Submission status: Accepted

Solution code:
def dfs_grid(h,w,sy, sx, maze,visited):
    cur = defaultdict(int)
    def bfs(cur):
        queue = []
        queue.insert(0, (sy, sx))
        visited[sy][sx] = True
        cur[maze[sy][sx]] += 1
        while len(queue):
            y, x = queue.pop()
            now = maze[y][x]
            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                if (0<= nx <w and 0<= ny <h and maze[ny][nx] != now and (not visited[ny][nx])):
                    queue.insert(0, (ny, nx))
                    visited[ny][nx] = True
                    cur[maze[ny][nx]] +=1
        return cur
    return bfs(cur)
def examC():
    H, W = LI()
    S = [SI() for _ in range(H)]
    ans = 0
    visited = [[False]*(W) for _ in range(H)]
    for i in range(H):
        for j in range(W):
            d = dfs_grid(H,W,i,j,S,visited)
            ans += d["."]*d["#"]
    print(ans)

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examC()

Submission status: Accepted

Solution code:
from fractions import gcd
# from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7

#グリッドを適当に移動してみると、いくつかの連結成分ができる
#その連結成分の条件を満たす組は（白の個数）×(黒の個数)で求まる。
#あとはそれを、すべての連結成分毎に足し合わせる
#PyPyは再帰遅い
def main():
    
    h, w = map(int, input().split())
    s = [list(input()) for i in range(h)]
    start = []
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#": 
                start.append([i,j])

    ans = [0,0]
    vis = [[-1 for i in range(w)] for j in range(h)]
    def f(x, y, pre):
        vis[x][y] = 1
        if s[x][y] == "#":
            ans[0] += 1
        else:
            ans[1] +=1
        for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            nx = i + x
            ny = j + y
            if nx >= 0 and ny >= 0 and nx < h and ny < w and vis[nx][ny] == -1:
                if pre == "B" and s[nx][ny] == ".":
                    f(nx,ny,"W")
                elif pre == "W" and s[nx][ny] == "#":
                    f(nx, ny, "B")
                
    
    ret = 0
    for i, j in start:
        if vis[i][j] == -1:
            f(i, j, "B")
        ret += ans[0] * ans[1]
        ans[0] = ans[1] = 0
    print(ret)
        

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
# from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def main():
    
    h, w = map(int, input().split())
    s = [list(input()) for i in range(h)]
    start = []
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#": 
                start.append([i,j])

    ans = [0,0]
    vis = [[-1 for i in range(w)] for j in range(h)]
    def f(x, y, pre):
        vis[x][y] = 1
        if s[x][y] == "#":
            ans[0] += 1
        else:
            ans[1] +=1
        for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            nx = i + x
            ny = j + y
            if nx >= 0 and ny >= 0 and nx < h and ny < w and vis[nx][ny] == -1:
                if pre == "B" and s[nx][ny] == ".":
                    f(nx,ny,"W")
                elif pre == "W" and s[nx][ny] == "#":
                    f(nx, ny, "B")
                
    
    ret = 0
    for i, j in start:
        if vis[i][j] == -1:
            f(i, j, "B")
        ret += ans[0] * ans[1]
        ans[0] = ans[1] = 0
    print(ret)
        

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int,input().split())
S = [input().strip() for _ in range(H)]
D = {0:".",1:"#"}
G = {}
C = {}
hist = [[-1 for _ in range(W)] for _ in range(H)]
col = -1
for i in range(H):
    for j in range(W):
        if S[i][j]=="#" and hist[i][j]==-1:
            col += 1
            G[col] = [(i,j)]
            que = deque([(i,j,1)])
            hist[i][j] = col
            cnt = 0
            while que:
                y,x,a = que.popleft()
                if x+1<W and S[y][x+1]==D[1-a]:
                    if a==1 and hist[y][x+1]!=col:
                        cnt += 1
                        que.append((y,x+1,1-a))
                        hist[y][x+1]=col
                    elif a==0 and hist[y][x+1]==-1:
                        G[col].append((y,x+1))
                        que.append((y,x+1,1-a))
                        hist[y][x+1]=col
                if y-1>-1 and S[y-1][x]==D[1-a]:
                    if a==1 and hist[y-1][x]!=col:
                        cnt += 1
                        que.append((y-1,x,1-a))
                        hist[y-1][x]=col
                    elif a==0 and hist[y-1][x]==-1:
                        G[col].append((y-1,x))
                        que.append((y-1,x,1-a))
                        hist[y-1][x]=col
                if x-1>-1 and S[y][x-1]==D[1-a]:
                    if a==1 and hist[y][x-1]!=col:
                        cnt += 1
                        que.append((y,x-1,1-a))
                        hist[y][x-1]=col
                    elif a==0 and hist[y][x-1]==-1:
                        G[col].append((y,x-1))
                        hist[y][x-1]=col
                        que.append((y,x-1,1-a))
                if y+1<H and S[y+1][x]==D[1-a]:
                    if a==1 and hist[y+1][x]!=col:
                        cnt += 1
                        que.append((y+1,x,1-a))
                        hist[y+1][x]=col
                    elif a==0 and hist[y+1][x]==-1:
                        G[col].append((y+1,x))
                        que.append((y+1,x,1-a))
                        hist[y+1][x]=col
            C[col] = cnt
tot = 0
for col in G:
    tot += len(G[col])*C[col]
print(tot)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.root=[-1]*(n+1)
        self.rnk=[0]*(n+1)

    def Find_Root(self,x):
        if self.root[x]<0:
            return x
        else:
            self.root[x]=self.Find_Root(self.root[x])
            return self.root[x]

    def Unite(self,x,y):
        x=self.Find_Root(x)
        y=self.Find_Root(y)
        if x==y:
            return
        elif self.rnk[x]>self.rnk[y]:
            self.root[x]+=self.root[y]
            self.root[y]=x
        else:
            self.root[y]+=self.root[x]
            self.root[x]=y
            if self.rnk[x]==self.rnk[y]:
                self.rnk[y]+=1

    def isSameGroup(self,x,y):
        return self.Find_Root(x)==self.Find_Root(y)

    def Count(self,x):
        return -self.root[self.Find_Root(x)]

h,w=map(int,input().split())
g=[list(input()) for _ in range(h)]
uf=UnionFind(h*w)
dyx=[(1,0),(-1,0),(0,1),(0,-1)]
for i in range(h):
    for j in range(w):
        if g[i][j]==".":
            continue
        p=i*w+j
        for dy,dx in dyx:
            y=i+dy
            x=j+dx
            if 0<=y<h and 0<=x<w:
                if g[y][x]==".":
                    np=y*w+x
                    uf.Unite(p,np)

rt=[0]*(h*w)
for i in range(h*w):
    rt[i]=uf.Find_Root(i)

m=min(rt)
rt=list(map(lambda x:x-m, rt))
m=max(rt)
a=[[0,0] for _ in range(m+1)]
for i in range(h*w):
    y=i//w
    x=i%w
    if g[y][x]=="#":
        a[rt[i]][0]+=1
    else:
        a[rt[i]][1]+=1
ans=0
for i,j in a:
    ans+=i*j

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])


def main():
    h,w=inpm()
    s=[input() for _ in range(h)]
    que=deque()
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    went = [[False for _ in range(w)] for _ in range(h)]
    ans = 0
    for i in range(h):
        for j in range(w):
            if s[i][j]=="#":
                if not went[i][j]:
                    went[i][j] = True
                    que = deque()
                    que.append((i,j))
                    a,b = 1,0
                    while len(que)>0:
                        x,y=que.pop()
                        for k in range(4):
                            nx,ny=x+dx[k],y+dy[k]
                            if nx<0 or h<=nx or ny<0 or w<=ny or went[nx][ny]:
                                continue
                            if s[x][y] != s[nx][ny]:
                                if s[nx][ny] == '#':
                                    a+=1
                                else:
                                    b+=1
                                went[nx][ny]=True
                                que.append((nx,ny))
                    ans += a*b
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

def search(sx, sy) :
    q = [(sx, sy)]
    visited[sy][sx] = True
    
    b, w = 0, 0
    if S[sy][sx] == '#' :
        b += 1
    else :
        w += 1
        
    while q :
        cx, cy = q.pop()
        for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)) :
            nx, ny = cx + dx, cy + dy
            if 0 <= nx < W and 0 <= ny < H and not visited[ny][nx] and S[cy][cx] != S[ny][nx] :
                visited[ny][nx] = True
                q.append((nx, ny))
                if S[ny][nx] == '#' :
                    b += 1
                else :
                    w += 1           
    return b * w

ret = 0
for y in range(H) :
    for x in range(W) :
        if not visited[y][x] :
            ret += search(x, y)
            
print(ret)

Submission status: Accepted

Solution code:
import sys
from collections import deque as dq
input = sys.stdin.readline
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
d = [-1, 0, 1, 0]
vis = [[0] * W for _ in range(H)]
Q = dq([])
res = 0
for i in range(H):
  for j in range(W):
    if vis[i][j] == 1: continue
    Q.append((i, j))
    w = 0
    b = 0
    while len(Q):
      p = Q.popleft()
      if S[p[0]][p[1]] == "#": b += 1
      elif S[p[0]][p[1]] == ".": w += 1
      vis[p[0]][p[1]] = 1
      for way in range(4):
        x = p[1] + d[way]
        y = p[0] + d[-1 - way]
        if 0 <= y < H and (0 <= x < W):
          if S[p[0]][p[1]] == S[y][x]:
            continue
          if vis[y][x] == 1: continue
          Q.append((y, x))
          vis[y][x] = 1
    res += b * w
print(res)

Submission status: Accepted

Solution code:
import itertools

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

diffs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
t = [[0] * w for _ in range(h)]
group = 1
for i, j in itertools.product(range(h), range(w)):
    if t[i][j] != 0:
        continue

    stack = [(i, j)]
    while stack:
        x, y = stack.pop()
        t[x][y] = group
        for dx, dy in diffs:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < h and 0 <= ny < w and t[nx][ny] == 0 and s[x][y] != s[nx][ny]:
                stack.append((nx, ny))
    group += 1

d = [[0] * 2 for _ in range(group)]
for i, j in itertools.product(range(h), range(w)):
    d[t[i][j]][0 if s[i][j] == '.' else 1] += 1

ans = sum(d[i][0] * d[i][1] for i in range(len(d)))
print(ans)

Submission status: Accepted

Solution code:
def main():

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

    ans = 0
    visited = set()
    for i in range(H):
        for j in range(W):
            if (i, j) not in visited:
                visited.add((i, j))
                b, w = 0, 0
                if A[i][j] == "#":
                    b += 1
                    c = "."
                else:
                    w += 1
                    c = "#"
                cur = [[i, j]]
                while cur:
                    temp = []
                    for k1, l1 in cur:
                        for dk, dl in [[1,0],[-1,0],[0,1],[0,-1]]:
                            k, l = k1+dk, l1+dl
                            if 0<=k<H and 0<=l<W and (k,l) not in visited and A[k][l] == c:
                                visited.add((k,l))
                                temp.append([k, l])

                    if c == "#":
                        b += len(temp)
                        c = "."
                    else:
                        w += len(temp)
                        c = "#"
                    cur = temp
                ans += b*w
    return ans

if __name__ == '__main__':
    print(main())