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:
#!/usr/bin/env python3

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math, cmath
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import _heapify_max, _heappop_max, _siftdown_max
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    Num = Union[int, float]
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input():  return sys.stdin.readline().rstrip()
    def ii():     return int(input())
    def isp():    return input().split()
    def mi():     return map(int, input().split())
    def mi_0():   return map(lambda x: int(x)-1, input().split())
    def lmi():    return list(map(int, input().split()))
    def lmi_0():  return list(map(lambda x: int(x)-1, input().split()))
    def li():     return list(input())
    def debug(x): print(x, file=sys.stderr)
    # def _heappush_max(h, item): h.append(item); _siftdown_max(h, 0, len(h)-1)
    
    
    h, w = mi()
    grid = []
    B = 1
    W = -1
    for _ in range(h):
        line = input()
        grid.append(list(map(lambda x: B if x == '#' else W, line)))
    visited = [[False] * w for _ in range(h)]

    # debug(grid)
    # debug(visited)


    def bfs(p):
        d = ((1, 0), (-1, 0), (0, 1), (0, -1))
        black_cnt, white_cnt = 0, 0
        q = deque()
        q.append(p)
        while q:
            i, j = q.popleft()
            if not visited[i][j]:
                visited[i][j] = True
                if grid[i][j] == B:
                    black_cnt += 1
                else:
                    white_cnt += 1
                for dx, dy in d:
                    nx, ny = i + dx, j + dy
                    if 0 <= nx < h and 0 <= ny < w and not visited[nx][ny] and grid[i][j] * grid[nx][ny] == -1:
                        q.append((nx, ny))
        return black_cnt, white_cnt


    ans = 0
    for i in range(h):
        for j in range(w):
            if grid[i][j] == B and not visited[i][j]:
                black_cnt, white_cnt = bfs((i, j))
                ans += black_cnt * white_cnt

    print(ans)




if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

is_used = [[False] * w for _ in range(h)]

di = [+1, 0, -1, 0]
dj = [0, +1, 0, -1]


def dfs(i, j):
    if s[i][j] == '#':
        cnt_w, cnt_b = 0, 1
    else:
        cnt_w, cnt_b = 1, 0

    for k in range(4):
        ni = i + di[k]
        nj = j + dj[k]
        if ni < 0 or ni >= h or nj < 0 or nj >= w:
            continue
        if is_used[ni][nj]:
            continue
        if s[i][j] == s[ni][nj]:
            continue

        is_used[ni][nj] = True
        cw, cb = dfs(ni, nj)
        cnt_w += cw
        cnt_b += cb
    return (cnt_w, cnt_b)


ans = 0
for i in range(h):
    for j in range(w):
        if not is_used[i][j]:
            is_used[i][j] = True
            cnt_w, cnt_b = dfs(i, j)
            ans += cnt_w * cnt_b

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(list(input()))
flg = [[True] * W for i in range(H)]

def bfs(i,j,S,flg):
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    que = deque([(i,j)])
    black = 1
    cnt = 1

    while len(que) != 0:
        p = que.popleft()
        #print(p)
        flg[p[0]][p[1]] = False
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if nx >= 0 and nx < H and ny >= 0 and ny < W and flg[nx][ny] == True:
                if S[p[0]][p[1]] == '#' and S[nx][ny] == '.':
                    que.append((nx,ny))
                    cnt += 1
                    flg[nx][ny] = False
                if S[p[0]][p[1]] == '.' and S[nx][ny] == '#':
                    que.append((nx,ny))
                    cnt += 1
                    black += 1
                    flg[nx][ny] = False
    # print(black,cnt-black)
    # val = 0
    # if black >= 2:
    #     val += (black*(black-1))//2
    return black * (cnt-black) 

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#' and flg[i][j] == True:
            ans += bfs(i,j,S,flg)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque


def main():
    H, W = list(map(int, input().split()))
    S = [input() for _ in range(H)]
    visited = [[0] * W for _ in range(H)]
    ans = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '#' or visited[h][w] == 1:
                continue
            n_white, n_black = 0, 0
            que = deque()
            que.append((h, w))
            while len(que) > 0:
                ch, cw = que.pop()
                if visited[ch][cw] == 1:
                    continue
                visited[ch][cw] = 1
                if S[ch][cw] == '.':
                    n_white += 1
                else:
                    n_black += 1
                for dh, dw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                    next_h, next_w = ch + dh, cw + dw
                    if 0 <= next_h < H and 0 <= next_w < W and \
                        S[ch][cw] != S[next_h][next_w] and \
                        visited[next_h][next_w] == 0:
                        que.append((next_h, next_w))
            ans += n_white * n_black
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

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

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

for y0 in range(H):
	for x0 in range(W):
		if S[y0][x0] ==  "." or check[y0][x0] == 1:
			continue
		cnt_black = 1
		cnt_white = 0
		check[y0][x0] = 1
		q = deque([(y0, x0)])
		while q:
			#print(q)
			y, x = q.popleft()
			for i in range(4):
				ny = y + dy[i]
				nx = x + dx[i]
				if 0 <= ny < H and 0 <= nx < W:
					if S[y][x] == "#" and S[ny][nx] == "." and check[ny][nx] == 0:
						check[ny][nx] = 1
						#print((y0, x0), (ny, nx))
						cnt_white += 1
						q.append((ny, nx))
					if S[y][x] == "." and S[ny][nx] == "#" and check[ny][nx] == 0:
						check[ny][nx] = 1
						cnt_black += 1
						q.append((ny, nx))
		ans += cnt_white*cnt_black
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

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

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

for y0 in range(H):
	for x0 in range(W):
		if S[y0][x0] ==  "." or check[y0][x0] == 1:
			continue
		cnt_black = 1
		cnt_white = 0
		check[y0][x0] = 1
		q = deque([(y0, x0, 1)])
		while q:
			#print(q)
			y, x, color = q.popleft()
			for i in range(4):
				ny = y + dy[i]
				nx = x + dx[i]
				if 0 <= ny < H and 0 <= nx < W:
					if color == 1 and S[ny][nx] == "." and check[ny][nx] == 0:
						check[ny][nx] = 1
						#print((y0, x0), (ny, nx))
						cnt_white += 1
						q.append((ny, nx, 0))
					if color == 0 and S[ny][nx] == "#" and check[ny][nx] == 0:
						check[ny][nx] = 1
						cnt_black += 1
						q.append((ny, nx, 1))
		ans += cnt_white*cnt_black
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

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

INF = -1
Gmap = [list(input()) for _ in range(H)]
Seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
init_q =[]

from collections import deque

def bfs(sth, stw):
    black = 1
    white = 0
    next_q = deque([])
    next_q.append((sth, stw))
    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h, w = next_q.popleft()
        Seen[h][w] = 0
        for d in direc:
            hs, ws = h + d[0], w + d[1]
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[h][w]=='#' and Gmap[hs][ws]=='.' and Seen[hs][ws]==INF:
                Seen[hs][ws]=0
                next_q.append((hs, ws))
                white +=1
            if Gmap[h][w]=='.' and Gmap[hs][ws]=='#' and Seen[hs][ws]==INF:
                Seen[hs][ws]=0
                next_q.append((hs, ws))
                black +=1
#        print(black,white)
    return black * white

#複数
ret = 0
for sth in range(H):
    for stw in range(W):
        if Gmap[sth][stw]=='#' and Seen[sth][stw]==INF:
            x = bfs(sth, stw)
#                print(sth,stw ,x)
            ret += x
print(ret)

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

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

INF = -1
Gmap = [list(input()) for _ in range(H)]
Seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
init_q =[]

from collections import deque

def bfs(sth, stw):
    black = 1
    white = 0
    next_q = deque([])
    next_q.append((sth, stw))
    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h, w = next_q.popleft()
        Seen[h][w] = 0
        for d in direc:
            hs, ws = h + d[0], w + d[1]
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[h][w]=='#' and Gmap[hs][ws]=='.' and Seen[hs][ws]==INF:
                Seen[hs][ws]=0
                next_q.append((hs, ws))
                white +=1
            if Gmap[h][w]=='.' and Gmap[hs][ws]=='#' and Seen[hs][ws]==INF:
                Seen[hs][ws]=0
                next_q.append((hs, ws))
                black +=1
#        print(black,white)
    return black * white

def main():
    #複数
    ret = 0
    for sth in range(H):
        for stw in range(W):
            if Gmap[sth][stw]=='#' and Seen[sth][stw]==INF:
                x = bfs(sth, stw)
#                print(sth,stw ,x)
                ret += x
    print(ret)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque


def bfs(S):  # 幅優先探索  # キュー
    que = deque([S])
    b, w = 0, 0
    while len(que) > 0:
        p, q = que.popleft()
        b += int(s[p][q] == '#')
        w += int(s[p][q] == '.')
        for i, j in near[p][q]:  # 移動先の候補
            if (i, j) in frag:  # 処理済みか否か
                continue
            que.append((i, j)), frag.add((i, j))
    return b * w


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

near = [[set() for j in range(w)] for i in range(h)]
for i, si in enumerate(s):
    for j, sij in enumerate(si):
        for p, q in [(i - 1, j), (i, j - 1), (i + 1, j), (i, j + 1)]:
            if 0 <= p < h and 0 <= q < w and s[p][q] != sij:
                near[i][j].add((p, q))

ans, frag = 0,set()
for i in range(h):
    for j in range(w):
        if (i, j) not in frag:
            frag.add((i, j))
            ans += bfs((i, j))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque


def bfs(S):  # 幅優先探索  # キュー
    que = deque([S])
    b, w = 0, 0
    while len(que) > 0:
        p, q = que.popleft()
        b += int(s[p][q] == '#')
        w += int(s[p][q] == '.')
        for i, j in near[p][q]:  # 移動先の候補
            if (i, j) in frag:  # 処理済みか否か
                continue
            if s[i][j] != s[p][q]:
                que.append((i, j)), frag.add((i, j))
    return b * w


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

near = [[set() for j in range(w)] for i in range(h)]
for i, si in enumerate(s):
    for j, sij in enumerate(si):
        for p, q in [(i - 1, j), (i, j - 1), (i + 1, j), (i, j + 1)]:
            if 0 <= p < h and 0 <= q < w and s[p][q] != sij:
                near[i][j].add((p, q))

ans, frag = 0,set()
for i in range(h):
    for j in range(w):
        if (i, j) not in frag:
            frag.add((i, j))
            ans += bfs((i, j))
print(ans)

Submission status: Accepted

Solution code:

import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]

H, W = read_values()
P = [[False for _ in range(W)] for _ in range(H)]
F = [input().strip() for i in range(H)]

def f(h, w):
    S = deque()
    S.append((h, w))
    P[h][w] = True
    T = [0, 1]
    while S:
        h, w = S.popleft()
        for hh, ww in [(h + 1, w), (h - 1, w), (h, w + 1), (h, w - 1)]:
            if not (0 <= hh < H and 0 <= ww < W):
                continue
            if P[hh][ww]:
                continue
            if F[hh][ww] == F[h][w]:
                continue
            P[hh][ww] = True
            t = 0 if F[hh][ww] == "." else 1
            T[t] += 1
            S.append((hh, ww))
    return T[0] * T[1]


def main():
    res = 0
    for h in range(H):
        for w in range(W):
            if P[h][w] or F[h][w] != "#":
                continue
            res += f(h, w)
    print(res)
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

mp = [[0]*W for _ in range(H)]
dxy = [[-1,0],[1,0],[0,-1],[0,1]]
lst = []

q = deque([])
num = 1
for i in range(H):
  for j in range(W):
    if mp[i][j] == 0:
      q.append((i,j))
      mp[i][j] = num
      dic = {'#':0, '.':0}
      while q:
        t = q.popleft()
        dic[Ss[t[0]][t[1]]] += 1
        for k in range(4):
          if t[0] + dxy[k][0] >= 0 and t[0] + dxy[k][0] < H \
             and t[1] + dxy[k][1] >= 0 and t[1] + dxy[k][1] < W \
             and Ss[t[0]][t[1]] != Ss[t[0]+dxy[k][0]][t[1]+dxy[k][1]]\
             and mp[t[0]+dxy[k][0]][t[1]+dxy[k][1]] == 0:
            
            mp[t[0]+dxy[k][0]][t[1]+dxy[k][1]] = num
            q.append((t[0]+dxy[k][0],t[1]+dxy[k][1]))
      lst.append(dic)
      num += 1

rlt = 0
for d in lst:
  rlt += d['#']*d['.']

print(rlt)

Submission status: Accepted

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

# 横の比較
for i in range(H):
    for j in range(W-1):
        if S[i][j] != S[i][j+1]:
            edge.append((i*W+j,i*W+j+1))
# 縦の比較
for i in range(H-1):
    for j in range(W):
        if S[i][j] != S[i+1][j]:
            edge.append((i*W+j, (i+1)*W+j))

class UnionFind():
    '''
    UnionFindでグラフの状態を管理する
    '''
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def is_root(self, x):
        return self.root[x] < 0

    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 is_same_group(self, x, y):
        '''
        同一のルーツを持つかどうか調査する
        '''
        return self.find_root(x) == self.find_root(y)

    def count(self, x):
        return -self.root[self.find_root(x)]

union = UnionFind(H*W)
for l, r in edge:
    union.unite(l, r)
cnt = [0] * (H*W)
for i in range(H*W):
    c = union.find_root(i)
    if S[i//W][i%W] == "#":
        cnt[c] += 1

ans = 0
for i in range(H*W):
    if union.is_root(i):
        r = union.find_root(i)
        c = union.count(i)
        ans += cnt[r] * (c-cnt[r])
print(ans)

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from collections import deque
    input = sys.stdin.readline

    H, W = map(int, input().split())
    grid = []
    for _ in range(H):
        grid.append(input().rstrip('\n'))

    ans = 0
    seen = [[0] * W for _ in range(H)]
    d = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    for h0 in range(H):
        for w0 in range(W):
            if seen[h0][w0] == 0:
                que = deque([(h0, w0)])
                seen[h0][w0] = 1
                black = white = 0
                while que:
                    h, w = que.popleft()
                    if grid[h][w] == "#":
                        black += 1
                    else:
                        white += 1
                    for dh, dw in d:
                        h_new, w_new = h+dh, w+dw
                        if 0 <= h_new < H and 0 <= w_new < W:
                            if seen[h_new][w_new] == 0:
                                if grid[h][w] != grid[h_new][w_new]:
                                    que.append((h_new, w_new))
                                    seen[h_new][w_new] = 1
                ans += black * white
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
seen = [[0] * W for _ in range(H)]

# Fの点を頂点とするグラフを考える。グラフの連結成分に'#'がbコ, '.'がwコある場合、
# b*wが条件を満たす

def dfs(sy, sx):
    seen[sy][sx] = 1
    b, w = 1, 0
    
    for dy, dx in move:
      ny = sy + dy
      nx = sx + dx
      if 0 <= ny < H and 0 <= nx < W and F[ny][nx] != F[sy][sx] and not seen[ny][nx]:
        p = dfs(ny, nx)
        b += p[1]  # 逆にしている
        w += p[0]  # 天才か？
    return (b, w)
        
count = 0
for i in range(H):
    for j in range(W):
        if not seen[i][j]:
            b, w = dfs(i, j)
            count += b * w

print(count)

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def bfs_grid(H, W, grid):

    d = [[False for _ in range(W)] for _ in range(H)]
    move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    ans = 0

    for sy in range(H):
        for sx in range(W):
            if d[sy][sx]:
                continue

            q = deque()
            q.append((sx, sy))
            d[sy][sx] = True
            black = 0
            white = 0
            while q:
                x, y = q.popleft()
                now_color = grid[y][x]
                if now_color:
                    white += 1
                else:
                    black += 1
                for m in move:
                    nx, ny = x + m[0], y + m[1]
                    if 0 <= nx < W and 0 <= ny < H:
                        if not d[ny][nx] and grid[ny][nx] != now_color:
                            d[ny][nx] = True
                            q.append((nx, ny))

            ans += black * white

    return ans


def main():
    H, W = in_nn()
    grid = in_map2(H)

    print(bfs_grid(H, W, grid))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

h, w = map(int, input().split())
s = [input() for i in range(h)]
mx=[1, -1, 0, 0]
my=[0, 0, 1, -1]
vis=[[0]*w for i in range(h)]
import queue
q=queue.Queue()
ans=0
for i in range(h):
  for j in range(w):
    if vis[i][j]==0:
      white=0
      black=0
      q.put([i, j])
      vis[i][j]=1
      while not q.empty():
        y, x = q.get()
        if s[y][x]==".":
          white+=1
        else:
          black+=1
        #vis[y][x]=1
        for k in range(4):
          nx=x+mx[k]
          ny=y+my[k]
          if 0<=nx<=w-1 and 0<=ny<=h-1 and vis[ny][nx]==0:
            if s[y][x] != s[ny][nx]:
              q.put([ny, nx])
              vis[ny][nx]=1
      if white+black!=1:
        ans+=white*black
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
seen = [[False]*W for _ in range(H)]
dx,dy = [1, 0, -1, 0], [0, 1, 0, -1]
c,S = 0,[]
for _ in range(H):
	S.append(input())

for i in range(H):
	for j in range(W):
		if (S[i][j]=='#') and (not seen[i][j]):
			d = deque()
			d.append((i, j))
			seen[i][j],b,w = True,1,0
			while d:
				px,py = d.popleft()
				for x,y in zip(dx,dy):
					nx, ny = px+x, py+y
					if nx < 0 or ny < 0 or nx >= H or ny >= W or seen[nx][ny]:
						continue
					if (S[px][py]=='#' and S[nx][ny] == '.') or (S[px][py]=='.' and S[nx][ny] == '#'):
						d.append((nx, ny))
						seen[nx][ny] = 1
						if S[px][py] == '#':
							w += 1
						else:
							b += 1
			c += b*w

print(c)

Submission status: Accepted

Solution code:
from collections import deque

dx,dy = [1, 0, -1, 0], [0, 1, 0, -1]

H, W = map(int, input().split())
seen = [[False]*W for _ in range(H)]
c,S = 0,[]
for _ in range(H):
	S.append(input())

for i in range(H):
	for j in range(W):
		if (S[i][j]=='#') and (not seen[i][j]):
			d = deque()
			d.append((i, j))
			seen[i][j],b,w = True,1,0
			while d:
				px,py = d.popleft()
				for x,y in zip(dx,dy):
					nx, ny = px+x, py+y
					if nx < 0 or ny < 0 or nx >= H or ny >= W or seen[nx][ny]:
						continue
					if S[px][py]=='#' and S[nx][ny] == '.':
						d.append((nx, ny))
						seen[nx][ny] = 1
						w += 1
					elif S[px][py]=='.' and S[nx][ny] == '#':
						d.append((nx, ny))
						seen[nx][ny] = 1
						b += 1
			c += b*w

print(c)

Submission status: Accepted

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

#union-find

n = h*w

par = [0] * n
rank = [0] * n

#初期化
for i in range(n):
    par[i] = i
    rank[i] = 0

#判定(一番上野根を求める)
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
    
#結合
def unite(x , y):
    rx = find(x)
    ry = find(y)
    
    if rx == ry:
        return
    
    if rank[rx] < rank[ry]:
        par[rx] = ry
    elif rank[rx] > rank[ry]:
        par[ry] = rx
    else:
        par[ry] = x
        rank[rx] += 1

for i in range(h):
    for j in range(w-1):
        if s[i][j] != s[i][j+1]:
            unite(i*w+j , i*w +j+1)
            
for i in range(h-1):
    for j in range(w):
        if s[i][j] != s[i+1][j]:
            unite(i*w+j , (i+1)*w +j)
            
uni = [[0]*2 for _ in range(n)]

for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            k = 0
        else:
            k = 1
        uni[find(i*w+j)][k] += 1
        
ans = 0
for i in uni:
    ans += i[0] * i[1]
    
print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
lists=[list(input()) for i in range(h)]
visited=[[False for i in range(w)] for j in range(h)]
from collections import deque

ans=0
dif=[(-1,0),(1,0),(0,-1),(0,1)]

def solve(i,j):
    global ans 
    ans=ans
    black=0
    white=0
    if visited[i][j]==False:
        if lists[i][j]=="#":
            black+=1
        else:
            white+=1
        visited[i][j]=True
        
    d=deque()
    e=deque()
    d.append((i,j))
    while d:
        while d:
            p=d.popleft()
            x,y=p
            color=lists[x][y]
            for que in dif:
                dx,dy=que
                if 0<=dx+x<h and 0<=dy+y<w:
                    if visited[dx+x][dy+y]==False and lists[dx+x][dy+y]!=color:
                        visited[dx+x][dy+y]=True
                        e.append((dx+x,dy+y))
                        if color=="#":
                            white+=1
                        else:
                            black+=1
        if e:
            d=e
            e=deque()
    ans+=(white)*(black)
flag=True
while flag:
    sub=False
    for i in range(h):
        for j in range(w):
            if visited[i][j]==False:
                solve(i,j)
                sub=True
    if sub==False:
        flag=False
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15
Dy = (-1,0,1,0)
Dx = (0,1,0,-1)
def main():
    H,W = map(int,input().split())
    grid = [input() for _ in range(H)]
    grid = [[1 if g == '#' else 0 for g in gr] for gr in grid]
    G = [[] for _ in range(H*W)]

    for i in range(H):
        for j in range(W):
            for dy,dx in zip(Dy,Dx):
                y = i + dy
                x = j + dx
                if y < 0 or y >= H or x < 0 or x >= W:
                    continue
                if grid[i][j]^grid[y][x] == 1:
                    G[i*W + j].append(y*W + x)
                    G[y*W + x].append(i*W + j)
    
    visited = [-1] * (H*W)
    ans = 0
    for i in range(W*H):
        if visited[i] >= 0:
            continue
        stack = [i]
        visited[i] = 0
        w = 1
        b = 0
        while stack:
            v = stack.pop()
            for e in G[v]:
                if visited[e] >= 0:
                    continue
                visited[e] = visited[v]^1
                if visited[e] == 1:
                    b += 1
                else:
                    w += 1
                stack.append(e)
        ans += b*w
    print(ans)
if __name__ == '__main__':
    main()