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
from collections import *

class Unionfind:
    def __init__(self, n):
        self.par = [-1]*n
        self.rank = [1]*n
    
    def root(self, x):
        r = x
        
        while not self.par[r]<0:
            r = self.par[r]
        
        t = x
        
        while t!=r:
            tmp = t
            t = self.par[t]
            self.par[tmp] = r
        
        return r
    
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        
        if rx==ry:
            return
        
        if self.rank[rx]<=self.rank[ry]:
            self.par[ry] += self.par[rx]
            self.par[rx] = ry
            
            if self.rank[rx]==self.rank[ry]:
                self.rank[ry] += 1
        else:
            self.par[rx] += self.par[ry]
            self.par[ry] = rx
    
    def is_same(self, x, y):
        return self.root(x)==self.root(y)
    
    def count(self, x):
        return -self.par[self.root(x)]

H, W = map(int, input().split())
S = [input()[:-1] for _ in range(H)]
uf = Unionfind(H*W)

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

wcnt = defaultdict(int)
bcnt = defaultdict(int)

for i in range(H):
    for j in range(W):
        r = uf.root(W*i+j)
        
        if S[i][j]=='#':
            wcnt[r] += 1
        else:
            bcnt[r] += 1

ans = 0

for k in wcnt:
    ans += wcnt[k]*bcnt[k]

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue
from decimal import *


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)

visited = None
S = None
H, W = None, None


def bfs(x, y):
    global visited
    if visited[y][x]:
        return 0
    q = []
    q.append((x, y))
    black = 0
    white = 0
    while q != []:
        x, y = q.pop()
        DIR = [(-1, 0), (1, 0), (0, 1), (0, -1)]
        for d in DIR:
            nx, ny = x + d[0], y + d[1]
            if 0 <= nx < W and 0 <= ny < H and S[y][x] != S[ny][nx] and not visited[ny][nx]:
                visited[ny][nx] = True
                if S[ny][nx] == '.':
                    white += 1
                else:
                    black += 1
                q.append((nx, ny))
    return black * white


def solve():
    global H, W
    global S
    global visited
    H, W = Scanner.map_int()
    S = Scanner.string_list(H)
    visited = [[False for _ in range(W)] for _ in range(H)]
    ans = 0
    for x in range(W):
        for y in range(H):
            ans += bfs(x, y)
    print(ans)


def main():
    # sys.stdin = open("sample.txt")
    # print('YNEOS'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

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


def bfs(i, j):
    b, w = 0, 0
    visited[i][j] = True
    que = deque([(i, j)])

    while que:
        ci, cj = que.popleft()
        if S[ci][cj] == '#':
            b += 1
        else:
            w += 1

        for di, dj in move:
            ni, nj = ci + di, cj + dj
            if not (0 <= ni < H and 0 <= nj < W) or visited[ni][nj]:
                continue
            if S[ci][cj] != S[ni][nj]:
                visited[ni][nj] = True
                que.append((ni, nj))

    return b * w


result = 0
for i in range(H):
    for j in range(W):
        if visited[i][j]:
            continue
        result += bfs(i, j)
print(result)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
s_list = []
for _ in range(H):
    s = input()
    s_list.append(s)
ans = 0
visited = set({})
for h in range(H):
    for w in range(W):
        if s_list[h][w] == '.':
            if str(h) + '_' + str(w) not in visited:
                d = deque()
                d.append([h, w])
                plus = 1
                minus = 0
                while d:
                    i, j = d.pop()
                    visited.add(str(i) + '_' + str(j))
                    for ii, jj in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                        if (0 <= (i + ii) < H) & (0 <= (j + jj) < W):
                            if str(i + ii) + '_' + str(j + jj) not in visited:
                                if s_list[i][j] != s_list[i + ii][j + jj]:
                                    d.append([i + ii, j + jj])
                                    visited.add(str(i + ii) + '_' + str(j + jj))
                                    if s_list[i + ii][j + jj] == '.':
                                        plus += 1
                                    else:
                                        minus += 1                                
                ans += plus * minus
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:
from collections import deque
h,w=map(int,input().split())
field=[["*" for i in range(w+2)]]+[["*"]+list(input())+["*"] for i in range(h)]+[["*"]*(w+2)]
dx=[-1,0,1,0]
dy=[0,-1,0,1]
visited=[[False for i in range(w+2)] for j in range(h+2)]
s={"#":0,".":1}
ans=0
def bfs(a,b):
    if visited[a][b] or field[a][b]=="*":return 0
    D=deque([(a,b)])
    visited[a][b]=True
    cnt=[0,0]
    while D:
        pos=D.popleft()
        cnt[s[field[pos[0]][pos[1]]]]+=1
        for i,j in zip(dx,dy):
            if field[pos[0]+i][pos[1]+j] == "*" or visited[pos[0]+i][pos[1]+j] or field[pos[0]+i][pos[1]+j]==field[pos[0]][pos[1]]:
                continue
            visited[pos[0]+i][pos[1]+j]=True
            D.append((pos[0]+i,pos[1]+j))
    return cnt[0]*cnt[1]
for i in range(h+2):
    for j in range(w+2):
        ans += bfs(i,j)
print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
s = [input() for _i in range(h)]
visit = [[-1 for _i in range(w)] for _j in range(h)]
r = 0
from collections import deque
for i in range(h):
    for j in range(w):
        if (s[i][j]=="#") and (visit[i][j]<0):
            q = deque([[i, j]])
            black = 1
            white = 0
            visit[i][j] = 1
            while q:
                x, y = q.popleft()
                for n, m in [[1,0], [0, 1], [-1,0], [0,-1]]:
                    if (0<=x+n) and (0<=y+m) and (x+n<h) and (y+m<w):
                        if (visit[x+n][y+m]<0) and (s[x][y]!=s[x+n][y+m]):
                            visit[x+n][y+m]=1
                            if s[x][y] == "#":
                                white += 1
                            else:
                                black += 1
                            q.append([x+n, y+m])
            r += black*white

print(r)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.color = [[0] * 2 for _ in range(n)]
        for i in range(n):
            y, x = divmod(i, w)
            if s[y][x] == '#':
                self.color[i][1] = 1
            else:
                self.color[i][0] = 1

    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
        self.color[x][0] += self.color[y][0]
        self.color[x][1] += self.color[y][1]

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


h, w = map(int, readline().split())
s = [readline().rstrip().decode() for _ in range(h)]
uf = UnionFind(h * w)
move = [(1, 0), (0, 1), (-1, 0), (0, -1)]
for y, ss in enumerate(s):
    for x, sss in enumerate(ss):
        for dy, dx in move:
            xx = x + dx
            yy = y + dy
            if 0 <= xx < w and 0 <= yy < h and sss != s[yy][xx]:
                uf.union(yy * w + xx, y * w + x)
print(sum(uf.color[root][0] * uf.color[root][1] for root in uf.roots()))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
class UnionFind():
    def __init__(self, n):
        self.n=n
        self.parents=[-1]*n # 親(uf.find()で経路圧縮して根)の番号。根の場合は-(そのグループの要素数)
        self.member_color=[[0,0]for _ in range(n)] #.の数，#の数
        for i in range(n):
            if S[i//w][i%w]=="#": 
                self.member_color[i][1]=1
            else:
                self.member_color[i][0]=1
    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 unite(self,x,y):
        #要素x,yのグループを併合
        x,y=self.find(x),self.find(y)
        if x==y:return
        if self.parents[x]>self.parents[y]:#要素数の大きい方をxに
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x #要素数が大きい方に併合
        self.member_color[x][0]+=self.member_color[y][0]
        self.member_color[x][1]+=self.member_color[y][1] 
    def size(self,x):
        #xが属するグループの要素数
        return -self.parents[self.find(x)]
    def same(self,x,y):
        #xとyが同じグループ？
        return self.find(x)==self.find(y)
    def members(self,x):
        #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 all_group_members_list(self):
        #各ルート要素のグループに含まれる要素のリストのリスト
        #[[0, 2], [1, 3, 4, 5]]
        return list(self.all_group_members().values())
    def __str__(self):
        #各ルート要素のグループに含まれる要素のリストをprint()
        return '\n'.join('{}: {}'.format(r,self.members(r)) for r in self.roots())
def main():
    global w,S
    h,w=map(int,input().split())
    S=[input() for _ in range(h)]
    uf=UnionFind(h*w)
    for i in range(h):
        for j in range(w):
            ss=S[i][j]
            for row,col in ((1,0),(-1,0),(0,1),(0,-1)):
                if i+row>=0 and i+row<h and j+col>=0 and j+col<w and ss!=S[i+row][j+col]:
                    uf.unite((i+row)*w+j+col,i*w+j) 
    ans=0
    for r in uf.roots():
        ans+=uf.member_color[r][0]*uf.member_color[r][1]
    print(ans)
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    H,W = LI()
    M = [sys.stdin.readline().rstrip() for _ in range(H)]

    c = [[0] * W for _ in range(H)]
    q = collections.deque()
    ans = 0
    for i in range(H):
        for j in range(W):
            if c[i][j]: continue

            black = 0; white = 0
            q.append((i,j,M[i][j]))
            c[i][j] = 1
            while q:
                y,x,s = q.popleft()
                if s == '#': black += 1
                else: white += 1
                for dy,dx in ((0,1),(1,0),(0,-1),(-1,0)):
                    if 0 <= y+dy < H and 0 <= x+dx < W:
                        if c[y+dy][x+dx] or M[y+dy][x+dx] == s: continue
                        c[y+dy][x+dx] = 1
                        q.append((y+dy,x+dx,M[y+dy][x+dx]))
            ans += black * white
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
maze=[input() for i in range(h)]
class UnionFind:
    #def   -> foo=UnionFind(n,1)  <- 1-based index, default is 0
    #method -> foo.hoge(huga)
    __slots__ = ["_size", "_first_idx", "_parents"]
    def __init__(self, size: int, first_index: int = 0) -> None:
        self._size = size
        self._first_idx = first_index
        self._parents = [[0,0,1] for i in range(size + first_index)]
        for i in range(size):
            self._parents[i][int(maze[i//w][i%w]==".")]=1
    def find(self, x: int) -> int:
        if type(self._parents[x]) is list:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]
    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)
    def unite(self, x: int, y: int) -> bool:
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        if self._parents[x][2] < self._parents[y][2]:
            x, y = y, x
        self._parents[x] = [self._parents[x][i]+self._parents[y][i] for i in range(3)]
        self._parents[y] = x
        return True
ans=0
m=[(0,1),(0,-1),(1,0),(-1,0)]
uf=UnionFind(h*w)
for i in range(h):
    for j in range(w):
        for dx,dy in m:
            if 0<=dx+i<h and 0<=dy+j<w and maze[i][j]!=maze[i+dx][j+dy]:
                uf.unite(i*w+j,(i+dx)*w+j+dy)
for i in uf._parents:
    if type(i)is list:ans+=i[0]*i[1]
print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
maze=[input() for i in range(h)]
class UnionFind:
    #def   -> foo=UnionFind(n,1)  <- 1-based index, default is 0
    #method -> foo.hoge(huga)
    __slots__ = ["_size", "_first_idx", "_parents"]
    def __init__(self, size: int, first_index: int = 0) -> None:
        self._size = size
        self._first_idx = first_index
        self._parents = [[0,0,1] for i in range(size + first_index)]
        for i in range(size):
            self._parents[i][int(maze[i//w][i%w]==".")]=1
    def find(self, x: int) -> int:
        try:
            if type(self._parents[x]) is list:
                return x
        except IndexError:print(x);exit()
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]
    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)
    def unite(self, x: int, y: int) -> bool:
        x, y = self.find(x), self.find(y)

        if x == y:
            return False
        if self._parents[x][2] < self._parents[y][2]:
            x, y = y, x
        self._parents[x] = [self._parents[x][i]+self._parents[y][i] for i in range(3)]
        self._parents[y] = x
        return True
ans=0
m=[(0,1),(0,-1),(1,0),(-1,0)]
uf=UnionFind(h*w)
for i in range(h):
    for j in range(w):
        for dx,dy in m:
            if 0<=dx+i<h and 0<=dy+j<w and maze[i][j]!=maze[i+dx][j+dy]:
                uf.unite(i*w+j,(i+dx)*w+j+dy)
for i in uf._parents:
    if type(i)is list:ans+=i[0]*i[1]
print(ans)

Submission status: Accepted

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

mat=[[x=="#" for x in input()] for _ in range(H)]
#print(mat)

answer=0
visited_set=set()
for i in range(H):
  for j in range(W):
    if not mat[i][j] or (i,j) in visited_set:
      continue      

    queue=[(i,j)]
    d=0
    num_black=num_white=0
    while queue:
      new_queue=set()
      for q in queue:
        ii,jj=q
        visited_set.add((ii,jj))
        if d%2==0:
          num_black+=1
        else:
          num_white+=1
        
        if ii>0 and mat[ii][jj]!=mat[ii-1][jj] and not (ii-1,jj) in visited_set:
          new_queue.add((ii-1,jj))
        if ii<H-1 and mat[ii][jj]!=mat[ii+1][jj] and not (ii+1,jj) in visited_set:
          new_queue.add((ii+1,jj))
        if jj>0 and mat[ii][jj]!=mat[ii][jj-1] and not (ii,jj-1) in visited_set:
          new_queue.add((ii,jj-1))
        if jj<W-1 and mat[ii][jj]!=mat[ii][jj+1] and not (ii,jj+1) in visited_set:
          new_queue.add((ii,jj+1))
          
      queue=list(new_queue)
      d+=1
      
    #print(i,j,num_black,num_white)
    answer+=num_black*num_white

print(answer)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    H, W = map(int, rl().split())
    S = [rl().rstrip() for _ in range(H)]
    
    roots = []
    searched = [[False] * W for _ in range(H)]
    counter = defaultdict(int)
    for i in range(H):
        for j in range(W):
            if searched[i][j]:
                continue
            roots.append((i, j))
            searched[i][j] = True
            sij = S[i][j]
            counter[(i, j, sij == '.')] += 1
            que = deque([(i, j, sij)])
            while que:
                cy, cx, cc = que.popleft()
                for dy, dx in ((-1, 0), (0, 1), (1, 0), (0, -1)):
                    ny, nx = cy + dy, cx + dx
                    if 0 <= ny < H and 0 <= nx < W:
                        if searched[ny][nx]:
                            continue
                        nc = S[ny][nx]
                        if cc == nc:
                            continue
                        searched[ny][nx] = True
                        counter[(i, j, nc == '.')] += 1
                        que.append((ny, nx, nc))
    
    ans = 0
    for i, j in roots:
        ans += counter[(i, j, 0)] * counter[(i, j, 1)]
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(200000)
H,W=map(int,input().split())
S=[input() for i in range(H)]
l=[[0]*(W+2) for i in range(H+2)]
for i in range(1,H+1):
    for j in range(1,W+1):
        l[i][j]=1
a,c=0,1
def nu(h,w):
    global c,b
    if S[h-1][w-1]=="#":
        b+=1
    if l[h-1][w] and S[h-1][w-1]!=S[h-2][w-1]:
        l[h-1][w]=0
        c+=1
        nu(h-1,w)
    if l[h+1][w] and S[h-1][w-1]!=S[h][w-1]:
        l[h+1][w]=0
        c+=1
        nu(h+1,w)
    if l[h][w-1] and S[h-1][w-1]!=S[h-1][w-2]:
        l[h][w-1]=0
        c+=1
        nu(h,w-1)
    if l[h][w+1] and S[h-1][w-1]!=S[h-1][w]:
        l[h][w+1]=0
        c+=1
        nu(h,w+1)
for i in range(1,H+1):
    for j in range(1,W+2):
        if not l[i][j]:
            continue
        b,c=0,1
        l[i][j]=0
        nu(i,j)
        a+=b*(c-b)
print(a)

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
s=[input() for _ in range(h)]
visited=[[True]*w for _ in range(h)]
def bfs(sx,sy):
    q=deque([(sx,sy)])
    visited[sx][sy]=False
    black=1
    white=0
    while q:
        x,y=q.popleft()
        for dx,dy in [[0,1],[1,0],[0,-1],[-1,0]]:
            nx,ny=x+dx,y+dy
            if 0<=nx<h and 0<=ny<w:
                if visited[nx][ny]:
                    if s[x][y]=="#" and s[nx][ny]==".":
                        visited[nx][ny]=False
                        q.append((nx,ny))
                        white+=1
                    elif s[x][y]=="." and s[nx][ny]=="#":
                        visited[nx][ny]=False
                        q.append((nx,ny))
                        black+=1
    return black,white
ans=0
for sx in range(h):
    for sy in range(w):
        if s[sx][sy]=="#" and visited[sx][sy]:
            black,white=bfs(sx,sy)
            ans+=black*white
print(ans)

Submission status: Accepted

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

check = [[False for _ in range(w)]for __ in range(h)]

import queue
q=queue.Queue()
nh = [1,0,-1,0]
nw = [0,1,0,-1]

ans = 0
for i in range(h):
    for j in range(w):
        if check[i][j]:continue
        check[i][j] =True
        cnt = [0]*2
        cnt[s[i][j] == '#']+=1
        q.put([i,j])
        while not q.empty():
            nowi,nowj = q.get()
            for ne in range(4):
                ni = nowi + nh[ne]
                nj = nowj + nw[ne]
                if ni<0 or h <=ni or nj<0 or w<=nj:continue
                if s[nowi][nowj] == s[ni][nj]:continue
                if check[ni][nj]:continue
                check[ni][nj]=True
                cnt[s[ni][nj]=='#']+=1
                q.put([ni,nj])
        ans += cnt[0]*cnt[1]
print(ans)

Submission status: Accepted

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

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

other_color = {".": "#", "#":'.'}

def dfs(i,j, color):
    num = 0
    black_num = 0
    #import IPython;IPython.embed()
    if i != 0:
        if S[i-1][j] == other_color[color] and not visit_flag[i-1][j]:
            visit_flag[i-1][j] = True
            _num, _black_num = dfs(i-1, j, other_color[color])
            num += _num
            black_num += _black_num
            if other_color[color] == "#":
                black_num += 1
                black_visited_flag[i-1][j] = True
            else:
                num += 1
    if i != H-1:
        if S[i+1][j] == other_color[color] and not visit_flag[i+1][j]:
            visit_flag[i+1][j] = True
            _num, _black_num = dfs(i+1, j, other_color[color])
            num += _num
            black_num += _black_num
            if other_color[color] == "#":
                black_num += 1
                black_visited_flag[i+1][j] = True
            else:
                num += 1
    if j != 0:
        if S[i][j-1] == other_color[color] and not visit_flag[i][j-1]:
            visit_flag[i][j-1] = True
            _num, _black_num = dfs(i, j -1, other_color[color])
            num += _num
            black_num += _black_num
            if other_color[color] == "#":
                black_num += 1
                black_visited_flag[i][j-1] = True
            else:
                num += 1
    if j != W-1:
        if S[i][j+1] == other_color[color] and not visit_flag[i][j+1]:
            visit_flag[i][j+1] = True
            _num, _black_num = dfs(i, j+1, other_color[color])
            num += _num
            black_num += _black_num
            if other_color[color] == "#":
                black_num += 1
                black_visited_flag[i][j+1] = True
            else:
                num += 1
    return num, black_num



ans = 0
visit_flag = [[False] * W for _ in range(H)] 
for i, row in enumerate(S):
    for j, val in enumerate(row):
        if black_visited_flag[i][j] or S[i][j] == ".":
            continue
        num, black_num = dfs(i,j, "#")
        ans += (num * black_num)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H,W=map(int,input().split())
table=[list(input()) for _ in range(H)]
dp=[[-1 for _ in range(W)] for _ in range(H)]
seen=[[0 for _ in range(W)] for _ in range(H)]
d=deque()
col=0
wlist=[0]*(H*W)
blist=[0]*(H*W)
for i in range(H):
    for j in range(W):
        if dp[i][j]==-1:
            col = i*W+j
            d.append([i,j])
            seen[i][j]=1
        while len(d)>0:
            v=d.popleft()
            x=v[0]
            y=v[1]
            dp[x][y]=col
            if x!=0:
                if (table[x][y]!=table[x-1][y])and(seen[x-1][y]==0):
                    seen[x-1][y]=1
                    d.append([x-1,y])
            if x!=H-1:
                if (table[x][y]!=table[x+1][y])and(seen[x+1][y]==0):
                    seen[x+1][y]=1
                    d.append([x + 1, y])
            if y!=0:
                if (table[x][y]!=table[x][y-1])and(seen[x][y-1]==0):
                    seen[x][y-1]=1
                    d.append([x, y-1])
            if y!=W-1:
                if (table[x][y]!=table[x][y+1])and(seen[x][y+1]==0):
                    seen[x][y+1]=1
                    d.append([x, y+1])
            #print(dp)
            #print(d)
            #input()
for i in range(H):
    for j in range(W):
        if table[i][j]=="#":
            blist[dp[i][j]]+=1
        else:
            wlist[dp[i][j]] += 1
#print(wlist,blist)
cnt=0
for i in range(H*W):
    cnt=cnt+blist[i]*wlist[i]
print(cnt)

Submission status: Accepted

Solution code:
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]


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

# calc connected componets
con_comp = UnionFind(H * W)
for i in range(H):
    for j in range(W):
        for (dh, dw) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            if i + dh < 0 or j + dw < 0 or i + dh >= H or j + dw >= W:
                continue
            if S[i][j] != S[i + dh][j + dw]:
                con_comp.union(i * W + j, (i + dh) * W + j + dw)

# enum white
white = {}
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            if con_comp.find(i * W + j) in white:
                white[con_comp.find(i * W + j)] += 1
            else:
                white[con_comp.find(i * W + j)] = 1

# count black
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#' and con_comp.size(i * W + j) > 1:
            ans += white[con_comp.find(i * W + j)]

print(ans)