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: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
h,w = map(int, input().split())
sf = [input() for _ in range(h)]

def check(c1,c2):
    st = [(c1[0],c1[1],"#")]
    visited = [[False for _ in range(w)] for _ in range(h)]
    while len(st)>0:
        s = st.pop()
        visited[s[0]][s[1]] = True
        if s[0]==c2[0] and s[1]==c2[1]:
            return True
        for d in [[1,0],[0,1],[-1,0],[0,-1]]:
            dh = s[0]+d[0]
            dw = s[1]+d[1]
            if h>dh>=0 and w>dw>=0:
                if s[2]=="#" and sf[dh][dw]=="." and not visited[dh][dw]:
                    st.append((dh,dw,"."))
                elif s[2]=="." and sf[dh][dw]=="#" and not visited[dh][dw]:
                    st.append((dh,dw,"#"))
    return False

def candidate(hi,wi):
    for d in [[1,0],[0,1],[-1,0],[0,-1]]:
        dh = hi+d[0]
        dw = wi+d[1]
        if h>dh>=0 and w>dw>=0 and sf[hi][wi]!=sf[dh][dw]:
            return True
    return False

p1 = []
p2 = []
for hi in range(h):
    for wi in range(w):
        if not candidate(hi,wi):
            continue
        if sf[hi][wi]=="#":
            p1.append((hi,wi))
        else:
            p2.append((hi,wi))

res = 0
for c1 in p1:
    for c2 in p2:
        if check(c1,c2):
            res += 1

# for hi1 in range(h):
#     for wi1 in range(w):
#         if not candidate(hi1,wi1):
#             continue
#         if sf[hi1][wi1]==".":
#             continue
#         for hi2 in range(h):
#             for wi2 in range(w):
#                 if hi1==hi2 and wi1==wi2:
#                     continue
#                 if not candidate(hi2,wi2):
#                     continue
#                 if sf[hi2][wi2]=="#":
#                     continue
#
#                 # print("check",(hi1,wi1), (hi2,wi2))
#                 if check((hi1,wi1),(hi2,wi2)):
#                     # print((hi1,wi1), (hi2,wi2))
#                     res += 1

print(res)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, S):
    g = defaultdict(dict)
    for i, r in enumerate(S):
        for j, c in enumerate(r):
            if i > 0 and S[i-1][j] != c:
                g[(i, j)][(i-1, j)] = 1
                g[(i-1, j)][(i, j)] = 1
            if i < H-1 and S[i+1][j] != c:
                g[(i, j)][(i+1, j)] = 1
                g[(i+1, j)][(i, j)] = 1
            if j > 0 and S[i][j-1] != c:
                g[(i, j)][(i, j-1)] = 1
                g[(i, j-1)][(i, j)] = 1
            if j < W-1 and S[i][j+1] != c:
                g[(i, j)][(i, j+1)] = 1
                g[(i, j+1)][(i, j)] = 1
    
    ans = 0
    for k in g:
        i, j = k
        if S[i][j] != '#':
            continue
        s = [k]
        done = set([k])
        while s:
            # print(s)
            k = s.pop()
            for n in g[k]:
                if n not in done:
                    s.append(n)
                    done.add(n)
            i, j = k
            if S[i][j] == '.':
                ans += 1
            

    return ans


def main():
    H, W = read_int_n()
    S = []
    for _ in range(H):
        S.append(read_str())
    print(slv(H, W, S))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
h, w = map(int, input().split())
mp = ["X" * (w + 2)] + ["X" + input() + "X" for _ in range(h)] + ["X" * (w + 2)]
checked = [[False] * (w + 2) for _ in range(h + 2)]
vec = ((1, 0), (0, -1), (-1, 0), (0, 1))


def another(c):
    if c == "#": return "."
    if c == ".": return "#"


def search(x, y):
    checked[y][x] = True
    now = mp[y][x]
    if mp[y][x] == "#":
        b_cnt = 1
        w_cnt = 0
    else:
        b_cnt = 0
        w_cnt = 1
    for dx, dy in vec:
        if not checked[y + dy][x + dx] and mp[y + dy][x + dx] == another(now):
            w_add, b_add = search(x + dx, y + dy)
            w_cnt += w_add
            b_cnt += b_add
    return w_cnt, b_cnt

ans = 0
for y in range(1, h + 1):
    for x in range(1, w + 1):
        if not checked[y][x]:
            w_cnt, b_cnt = search(x, y)
            ans += w_cnt * b_cnt

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
s = [["X"] * (W+2)] + [["X"] + list(input()) + ["X"] for _ in range(H)] + [["X"] * (W+2)]

DH = [1, 0, -1, 0]
DW = [0, 1, 0, -1]

ans = 0
def bfs(start):
	global ans
	que = deque([start])
	visited = [[False for _ in [0]*(W+2)] for _ in [0]*(H+2)]
	visited[start[0]][start[1]] = True
	#cur = s[start[0]][start[1]]
	while que:
		label = que.pop()
		h, w = label[0], label[1]
		if s[start[0]][start[1]] != s[h][w] and W*start[0]+start[1] < W*h+w:
			ans += 1
		for dh, dw in zip(DH, DW):
			if s[h][w] == ".":
				if s[h+dh][w+dw] == "#" and visited[h+dh][w+dw] == False:
					que.appendleft([h+dh, w+dw])
					visited[h+dh][w+dw] = True
			elif s[h][w] == "#":
				if s[h+dh][w+dw] == "." and visited[h+dh][w+dw] == False:
					que.appendleft([h+dh, w+dw])
					visited[h+dh][w+dw] = True


	del que, visited
	return

for i in range(1, H+1):
	for j in range(1, W+1):
		bfs([i, j])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
h,w = map(int, input().split())
sf = [input() for _ in range(h)]

def check(c1,c2):
    st = [(c1[0],c1[1],"#")]
    visited = [[False for _ in range(w)] for _ in range(h)]
    while len(st)>0:
        s = st.pop()
        visited[s[0]][s[1]] = True
        if s[0]==c2[0] and s[1]==c2[1]:
            return True
        for d in [[1,0],[0,1],[-1,0],[0,-1]]:
            dh = s[0]+d[0]
            dw = s[1]+d[1]
            if h>dh>=0 and w>dw>=0:
                if s[2]=="#" and sf[dh][dw]=="." and not visited[dh][dw]:
                    st.append((dh,dw,"."))
                elif s[2]=="." and sf[dh][dw]=="#" and not visited[dh][dw]:
                    st.append((dh,dw,"#"))
    return False

def candidate(hi,wi):
    for d in [[1,0],[0,1],[-1,0],[0,-1]]:
        dh = hi+d[0]
        dw = wi+d[1]
        if h>dh>=0 and w>dw>=0 and sf[hi][wi]!=sf[dh][dw]:
            return True
    return False

res = 0
for hi1 in range(h):
    for wi1 in range(w):
        if not candidate(hi1,wi1):
            continue
        if sf[hi1][wi1]==".":
            continue
        for hi2 in range(h):
            for wi2 in range(w):
                if hi1==hi2 and wi1==wi2:
                    continue
                if not candidate(hi2,wi2):
                    continue
                if sf[hi2][wi2]=="#":
                    continue

                # print("check",(hi1,wi1), (hi2,wi2))
                if check((hi1,wi1),(hi2,wi2)):
                    # print((hi1,wi1), (hi2,wi2))
                    res += 1

print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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


def count(start, S, H, W):
    retval = 0
    q = deque()
    q.append((start[0], start[1], "#"))
    tested = [[False] * W for _ in range(H)]
    while(len(q)):
        i, j, color = q.popleft()
        if tested[i][j]:
            continue
        tested[i][j] = True
        if color == ".":
            retval += 1
        if color == "#":
            ncolor = "."
        else:
            ncolor = "#"
        for d in DIRECTIONS:
            ni = i + d[0]
            nj = j + d[1]
            if 0 <= ni and ni < H and 0 <= nj and nj < W and S[ni][nj] == ncolor:
                q.append((ni, nj, ncolor))
    return retval


def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    retval = 0
    for i in range(H):
        for j in range(W):
            if(S[i][j] == "#"):
                retval += count((i, j), S, H, W)
    print(retval)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from networkx.utils import UnionFind
def input(): return sys.stdin.readline().rstrip()
def main():
    h, w = map(int, input().split())
    s = [list(input()) for i in range(h)]
    uf = UnionFind()
    for i in range(h):
        for j in range(w):
            if i != h-1:
                if s[i][j] != s[i+1][j]:
                    uf.union((i*w)+j, (i*w)+j+w)
            if j != w-1:
                if s[i][j] != s[i][j+1]:
                    uf.union((i*w)+j, (i*w)+j+1)
    ans=0
    for item in uf.to_sets():
        A=0
        B=0
        for grid in item:
            i,j=divmod(grid,w)
            if s[i][j]=='.':
                A+=1
            else:
                B+=1
        ans+=A*B
    print(ans)
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7


def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    ans = 0
    checked = [[0]*W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if S[i][j] == '.' or checked[i][j]:
                continue
            queue = deque()
            queue.append((i, j))
            dx = [1, -1, 0, 0]
            dy = [0, 0, 1, -1]
            black = 1  # 黒マスの数
            white = 0
            checked[i][j] = 1

            while queue:
                nowy, nowx = queue.popleft()
                for k in range(4):
                    y = nowy + dy[k]
                    x = nowx + dx[k]
                    if 0 <= y < H and 0 <= x < W:
                        if checked[y][x]:
                            continue
                        if S[y][x] != S[nowy][nowx]:
                            if S[y][x] == '.':
                                white += 1
                            else:
                                black += 1
                            queue.append((y, x))
                            checked[y][x] = 1
            # print(i, j)
            ans += black * white
            # print(checked)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

def main():
    h, w = map(int, input().split())
    tizu = [input().strip() for _ in range(h)]
    directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    used = [[False for _ in range(w)] for _ in range(h)]
    
    ans = 0
    for i in range(h):
        for j in range(w):
            if used[i][j]:
                continue
            used[i][j] = True
            queue = deque()
            queue.append([i, j])
            queue.append(tizu[i][j])
            b_cnt = 0
            w_cnt = 0
            while queue:
                pos = queue.popleft()
                bw = queue.popleft()
                if bw == "#":
                    b_cnt += 1
                else:
                    w_cnt += 1
                for dy, dx in directions:
                    ny = dy + pos[0]
                    nx = dx + pos[1]
                    if ny == -1 or ny == h or nx == -1 or nx == w:
                        continue
                    if used[ny][nx]:
                        continue
                    bw2 = tizu[ny][nx]
                    if bw == bw2:
                        continue
                    used[ny][nx] = True
                    queue.append([ny, nx])
                    queue.append(bw2)
            ans += b_cnt * w_cnt
    print(ans)

main()

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
A=[list(input()) for i  in range(h)]
black=[] ;seen=[[0]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if A[i][j]=="#":
            black.append((i,j))
            
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal as D  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
from fractions import Fraction as F  #F(a,b)で正確なa/b
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
dx=[1,0,-1,0]
dy=[0,1,0,-1]
ans=0

# print(seen)

for i,j in black:
    # print(i,j)
    if seen[i][j]:continue
    seen[i][j]=1
    color=[0,1]
    queue= deque([(i,j,1)])
    while queue:
        x,y,c= queue.pop()
        # print(i,j,x,y,c)
        for xx,yy in zip(dx,dy):
            if 0<=x+xx<h and 0<=y+yy<w and seen[x+xx][y+yy]==0 and A[x+xx][y+yy]==".#"[1-c]:
                color[1-c]+=1
                seen[x+xx][y+yy]=1 
                queue.appendleft((x+xx,y+yy,1-c))
    ans+= color[0] * color[1]
print(ans)

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect
h,w=map(int,input().split())
s=[list(input()) for _ in range(h)]
seen={}
check=[[0]*w for _ in range(h)]

for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            seen[i*w+j]=0
if not seen:
    print(0)
    exit()
d=deque()
p=[[1,0],[-1,0],[0,1],[0,-1]]
ans=0

for j in seen:
    if seen[j]==0:
        d.append(j)
        blue=1
        white=0
        seen[j]=1    
        while d:
            i=d.pop()
            if i==0:
                f=True if s[0][0]=="#" else False
            else:
                f=True if i>0 else False
            ih=abs(i)//w
            iw=abs(i)%w
            check[ih][iw]=1
            for v in p:
                x,y=v
                if f==True and 0<=x+iw<w and 0<=y+ih<h and s[y+ih][x+iw]=="." and check[y+ih][x+iw]==0:
                    d.append(((ih+y)*w+(iw+x))*(-1))
                    white+=1
                    check[y+ih][x+iw]=1
                elif f==False and 0<=x+iw<w and 0<=y+ih<h and s[y+ih][x+iw]=="#" and check[y+ih][x+iw]==0:
                    d.append(((ih+y)*w+(iw+x)))
                    seen[((ih+y)*w+(iw+x))]=1
                    check[y+ih][x+iw]=1
                    blue+=1
        ans+=blue*white
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]

cntblack, cntwhite = 0, 0
visited = [[False] * W for _ in range(H)]

def count(h, w):
    global cntblack, cntwhite
    if visited[h][w]: return
    visited[h][w] = True
    if S[h][w] == ".": cntwhite += 1
    else: cntblack += 1
    for ny, nx in ((1,0),(0,1),(-1,0),(0,-1)):
        ny += h
        nx += w
        if not (0 <= ny < H and 0 <= nx < W): continue
        if S[ny][nx] == S[h][w]: continue
        count(ny, nx)


ans = 0
for h in range(H):
    for w in range(W):
        cntblack, cntwhite = 0, 0
        count(h, w)
        ans += cntblack * cntwhite

print(ans)

Submission status: Accepted

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

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self._size = [1] * 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._size[ra] < self._size[rb]: ra,rb = rb,ra
        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        self.count += 1
    def size(self,a):
        return self._size[self.root(a)]

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.unite(i*W+j, (i+1)*W+j)
        if j < W-1 and S[i][j] != S[i][j+1]:
            uf.unite(i*W+j, i*W+j+1)
for i in range(H*W):
    uf.root(i)

from collections import defaultdict
bl = defaultdict(lambda: 0)
wh = defaultdict(lambda: 0)
for i in range(H):
    for j in range(W):
        v = i*W+j
        r = uf.root(v)
        if S[i][j]=='#':
            bl[r] += 1
        else:
            wh[r] += 1

ans = 0
for k in bl.keys():
    ans += bl[k] * wh[k]
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
grid = [input() for _ in range(h)]
visited = [[0]*w for _ in range(h)]
moves = ((1, 0), (-1, 0), (0, 1), (0, -1))

ans = 0
for i in range(h):
    for j in range(w):
        if not visited[i][j]:
            bcnt, wcnt = 0, 0
            q = deque([(i, j)])
            while q:
                cx, cy = q.popleft()
                if visited[cx][cy]:
                    continue
                if grid[cx][cy] == "#":
                    bcnt += 1
                else:
                    wcnt += 1
                visited[cx][cy] = 1
                for (dx, dy) in moves:
                    if 0 <= cx + dx < h and 0 <= cy + dy < w and not visited[cx + dx][cy + dy] and grid[cx + dx][cy + dy] != grid[cx][cy]:
                        q.append((cx + dx, cy + dy))
            ans += bcnt * wcnt
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import deque

h,w=nii()
s=[list(input()) for i in range(h)]

def BFS(sy,sx,ans):
  s[sy][sx]='B'

  que=deque()
  que.append((sy,sx))

  b_cnt=1
  w_cnt=0

  while que:
    y,x=que.popleft()
    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:
        if s[y][x]=='B' and s[ny][nx]=='.':
          w_cnt+=1
          s[ny][nx]='W'
          que.append((ny,nx))
        if s[y][x]=='W' and s[ny][nx]=='#':
          b_cnt+=1
          s[ny][nx]='B'
          que.append((ny,nx))

  ans+=b_cnt*w_cnt
  return ans

ans=0
for i in range(h):
  for j in range(w):
    if s[i][j]=='#':
      ans=BFS(i,j,ans)

print(ans)

Submission status: Accepted

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

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

def dfs(y, x):
    b, w = 0, 0
    if S[y][x] == '#': b += 1
    else: w += 1
    for dy, dx in ((0,1), (1,0), (0,-1), (-1,0)):
        ny, nx = y + dy, x + dx
        if ny < 0 or ny >= H or nx < 0 or nx >= W: continue
        if S[y][x] == S[ny][nx] or visited[ny][nx]: continue
        visited[ny][nx] = 1
        n, m = dfs(ny, nx)
        b += n
        w += m
    return (b, w)

ans = 0
for i in range(H):
    for j in range(W):
        if not visited[i][j]:
            visited[i][j] = 1
            b, w = dfs(i, j)
            ans += b * w
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H,W=map(int, input().split())

S=[]
for i in range(H):
    s=list(input())
    S.append(s)



dones=[[0]*W for _ in range(H)]
dh=[1,0,-1,0]
dw=[0,1,0,-1]

def judge(h,w):
    if 0<=h<H and 0<=w<W:
        if dones[h][w]==0:
            return True
    return False
ans=0
for h in range(H):
    for w in range(W):
        now=S[h][w]
        if now=="#" and dones[h][w]==0:
            que=deque([])
            que.append((h, w, "#"))
            dones[h][w]=1
            blacks=0
            whites=0
            while que:
                nowh, noww, color = que.popleft()
                if color=="#":
                    blacks+=1
                    #print(nowh, noww)
                else:
                    whites+=1
                for i in range(4):
                    nh=nowh+dh[i]
                    nw=noww+dw[i]
                    if judge(nh, nw):
                        if color=="#" and S[nh][nw]==".":
                            que.append((nh,nw,"."))
                            dones[nh][nw]=1
                        if color=="." and S[nh][nw]=="#":
                            dones[nh][nw]=1
                            que.append((nh,nw,"#"))
            ans+=blacks*whites
            #print(blacks, whites)

print(ans)

Submission status: Accepted

Solution code:
def aising19_c():
    from collections import deque

    h, w = (int(x) for x in input().split())
    color = [[s == '#' for s in str(input())] for _ in range(h)]
    used = [[False]*w for _ in range(h)]

    ans = 0
    for i in range(h):
        for j in range(w):
            if used[i][j]: continue
            bk, wt = 0, 0
            que = deque()
            used[i][j] = True
            que.append((i, j))
            while que:
                ci, cj = que.popleft()
                if color[ci][cj]: bk += 1
                else: wt += 1
                for di, dj in ((-1,0),(0,-1),(0,1),(1,0)):
                    ni, nj = ci+di, cj+dj
                    if ni < 0 or h <= ni or nj < 0 or w <= nj: continue
                    if color[ci][cj] == color[ni][nj]: continue
                    if used[ni][nj]: continue
                    used[ni][nj] = True
                    que.append((ni, nj))
            ans += bk * wt
    print(ans)

if __name__ == '__main__':
    aising19_c()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

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

#初期化
# uf = UnionFind(n)
h,w = inpl()
s = [input() for _ in range(h)]
d = [(1,0),(-1,0),(0,1),(0,-1)]
uf = UnionFind(h*w+5)
def ind(i,j): return i*w+j
for y in range(h):
    for x in range(w):
        for dy,dx in d:
            ny = y+dy
            nx = x+dx
            if 0 <= ny < h and 0 <= nx < w and s[ny][nx] != s[y][x]:
                uf.union(ind(y,x), ind(ny,nx))
# print(uf.parents)f
res = 0
cnt = [[0,0] for _ in range(h*w)]
for i in range(h*w):
    ind = uf.find(i)
    color = 0 if s[i//w][i%w] == '.' else 1
    cnt[ind][color] += 1
for i in range(h*w):
    res += cnt[i][0] * cnt[i][1]
print(res)

Submission status: Accepted

Solution code:
from collections import deque
h, w, *s = open(0).read().split()
h = int(h)
w = int(w)

q = deque()
used = [False] * (h * w)

ans = 0
for i in range(h):
    for j in range(w):
        if not used[i * w + j]:
            bcnt = 0
            cnt = 0

            q.append((i, j))
            used[i * w + j] = True
            cnt += 1
            bcnt += s[i][j] == '#'

            while len(q):
                y, x = q.popleft()
                for dy, dx in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                    ny = y + dy
                    nx = x + dx
                    if 0 <= nx < w and 0 <= ny < h and s[y][x] != s[ny][nx] and not used[ny * w + nx]:
                        q.append((ny, nx))
                        used[ny * w + nx] = True
                        cnt += 1
                        bcnt += s[ny][nx] == '#'
            ans += bcnt * (cnt - bcnt)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import setrecursionlimit


def dfs(i, j, c):
    visited[i][j] = 1
    current.append((i, j))
    for di, dj in (1, 0), (-1, 0), (0, 1), (0, -1):
        ni, nj = i + di, j + dj
        if not (0 <= ni < H and 0 <= nj < W and not visited[ni][nj]):
            continue
        if S[ni][nj] == c:
            continue
        dfs(ni, nj, not c)


setrecursionlimit(2 * 10 ** 5)
H, W = map(int, input().split())
S = [[c == "#" for c in input()] for _ in range(H)]

ans = 0
visited = [[0] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j] and not visited[i][j]:
            current = []
            dfs(i, j, True)
            b, w = 0, 0
            for k, l in current:
                if S[k][l]:
                    b += 1
                else:
                    w += 1
            ans += b * w
print(ans)

Submission status: Accepted

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

H, W = map(int, input().split())
S = [list(map(lambda x: 1 if x == '#' else 0, input()[:-1])) for _ in [0]*H]
for i, ss in enumerate(S):
    for j, s in enumerate(ss):
        if (i ^ j) & 1:
            ss[j] ^= 1

visited = [0]*(H*W)

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


def dfs(i, j, cnt):
    c = S[i][j]
    for di, dj in dirs:
        ni, nj = i+di, j+dj
        if not 0 <= ni < H or not 0 <= nj < W:
            continue
        if visited[ni*W+nj]:
            continue
        if c == S[ni][nj]:
            visited[ni*W+nj] = 1
            cnt[(ni ^ nj) & 1] += 1
            dfs(ni, nj, cnt)


ans = 0
for i in range(H):
    for j in range(W):
        if visited[i*W+j]:
            continue
        visited[i*W+j] = 1
        cnt = [0, 0]
        cnt[(i ^ j) & 1] += 1
        dfs(i, j, cnt)
        ans += cnt[0] * cnt[1]
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
h,w = map(int, input().split())
s = [input() for i in range(h)]
root = [[0,1],[1,0],[0,-1],[-1,0]]
def bfs(x,y):
  v[x][y]=1
  cnt=1
  cnt1=0
  d = deque([[x,y]])
  while len(d):
    e,f = d.popleft()
    c = s[e][f]
    for a,b in root:
      x1 = e+a
      y1 = f+b
      if x1>=0 and x1<h and y1>=0 and y1 <w and v[x1][y1]==0:
        if c == '.' and s[x1][y1]=='#':
          v[x1][y1]=1
          d.append([x1,y1])
          cnt+=1
        if c == '#' and s[x1][y1]=='.':
          v[x1][y1]=1
          d.append([x1,y1])
          cnt1+=1
  return cnt*cnt1
v = [[0 for i in range(w)] for j in range(h)]
ans=0
for i in range(h):
  for j in range(w):
    if v[i][j]:
      continue
    if s[i][j]=='#':
      ans+= bfs(i,j)
print(ans)