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
sys.setrecursionlimit(10 ** 9)
H, W = map(int, input().split())
G = [list(input()) for i in range(H)]
C = [[0] * W for i in range(H)]


def dfs(nh, nw, color):
    direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    C[nh][nw] = color
    for dh, dw in direction:
        if not ((0 <= nh + dh < H) and (0 <= nw + dw < W)):
            continue
        if C[nh + dh][nw + dw] != 0:
            continue
        if G[nh][nw] == G[nh + dh][nw + dw]:
            continue
        C[nh + dh][nw + dw] = color
        dfs(nh + dh, nw + dw, -color)


Color = 1
for h in range(H):
    for w in range(W):
        if C[h][w] == 0:
            dfs(h, w, Color)
            Color += 1


Count = {}
for h in range(H):
    for w in range(W):
        Count[C[h][w]] = 0
        Count[-C[h][w]] = 0


for h in range(H):
    for w in range(W):
        Count[C[h][w]] += 1


ans = 0
for key in Count.keys():
    ans += Count[key] * Count[-key]

print(ans // 2)

Submission status: Accepted

Solution code:
from collections import deque
h,w = (int(i) for i in input().split())
maze = [input() for _ in range(h)]
visited = [[False]*w for _ in range(h)]
  
def solve2(i,j):
  d = [(1,0),(0,1),(-1,0),(0,-1)]
  queue = deque([(i,j)])
  b,c = 0,0
  while queue:
    (x,y) = queue.popleft()
    if maze[x][y] =='#':b+=1
    else:c += 1
    visited[x][y] = True
    
    for dx,dy in d:
      nx,ny = x+dx,y+dy
      #print(nx,ny)
      if nx <= -1 or nx >= h or ny <= -1 or ny >= w:
        continue
      if visited[nx][ny]:
        continue
      #print(maze[nx][ny],maze[x][y])
      if maze[nx][ny] != maze[x][y]:
       visited[nx][ny] = True
       queue.append([nx,ny])
        
 # print(b,c)
  return b*c

ans = 0
for i in range(h):
  for j in range(w):
    if not visited[i][j]:
     ans += solve2(i,j)
print(ans)

Submission status: Accepted

Solution code:
h,w = (int(i) for i in input().split())
s = [input() for i in range(h)]
x,v,ans = [[] for i in range(h*w)],[1]*(h*w),0
for i in range(h):
    for j in range(w):
        if i!=h-1 and s[i][j]!=s[i+1][j]:
            x[i*w+j].append((i+1)*w+j)
            x[(i+1)*w+j].append(i*w+j)
        if j!=w-1 and s[i][j]!=s[i][j+1]:
            x[i*w+j].append(i*w+j+1)
            x[i*w+j+1].append(i*w+j)
for i in range(h*w):
    if v[i]:
        q,a,b,v[i] = [i],0,0,0
        while q:
            p = q.pop()
            if s[p//w][p%w]=="#": a+=1
            else: b+=1
            for j in x[p]:
                if v[j]:
                    q.append(j)
                    v[j] = 0
        ans+=a*b
print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())

field = [["@"] * (w + 2)] + [list("@"+input()+"@") for _ in range(h)] + [["@"] * (w + 2)]
direction = [(0, -1), (0, 1), (1, 0), (-1, 0)]

flip = {".": "#", "#": "."}

def count_up(i, j):
    que = [(i, j)]
    cnt = {".": 0, "#": 0}
    while que:
        i, j = que.pop()
        now = field[i][j]
        field[i][j] = "@"
        fliped_chip = flip.get(now)
        if fliped_chip is not None:
            cnt[now] += 1
        for d in direction:
            dx, dy = d
            nx, ny = j + dx, i + dy
            next_chip = field[ny][nx]
            if next_chip == fliped_chip:
                que.append((ny, nx))
    return cnt

cnt = [[0] * w for _ in range(h)]
result = 0
for i in range(1, h + 1):
    for j in range(1, w + 1):
        dot_sharp = count_up(i, j)
        result += (dot_sharp["."] * dot_sharp["#"])
print(result)
#
#
# print("\n".join(map("".join, field)))
#
#

Submission status: Accepted

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

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

ans = 0
for i in range(h):
  for j in range(w):
    if visited[i][j]:
      continue
    bc = 0
    wc = 0
    visited[i][j] = True
    node = [(i, j)]
    while node:
      ci, cj = node[0]
      node = node[1:]
      if s[ci][cj] == '#':
        bc += 1
      else:
        wc += 1
      if ci - 1 >= 0 and s[ci][cj] != s[ci-1][cj]:
        if not visited[ci-1][cj]:
          visited[ci-1][cj] = True
          node.append((ci-1, cj))
      if ci + 1 <= h-1 and s[ci][cj] != s[ci+1][cj]:
        if not visited[ci+1][cj]:
          visited[ci+1][cj] = True
          node.append((ci+1, cj))
      if cj - 1 >= 0 and s[ci][cj] != s[ci][cj-1]:
        if not visited[ci][cj-1]:
          visited[ci][cj-1] = True
          node.append((ci, cj-1))
      if cj + 1 <= w-1 and s[ci][cj] != s[ci][cj+1]:
        if not visited[ci][cj+1]:
          visited[ci][cj+1] = True
          node.append((ci, cj+1))
    ans += bc * wc

print(ans)

Submission status: Accepted

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

S = [[1 if s=='#' else -1 for s in input()] for _ in range(H)]

def surround(matrix, fill=0):
  if not isinstance(matrix, list):
    raise
  if not all([isinstance(rows, list) for rows in matrix]):
    raise
  if not all([len(rows)==len(matrix[0]) for rows in matrix]):
    raise
  r = len(matrix)
  c = len(matrix[0])
  new_matrix = [[fill]*(c+2)] + [[fill]+rows+[fill] for rows in matrix] + [[fill]*(c+2)]
  return new_matrix

S = surround(S, 0)
# 黒: 1 白:-1 枠:0

from itertools import product
to_visit = set(list(product(range(1,H+1), range(1, W+1))))


from collections import deque

answer = 0
while to_visit:
  h,w = to_visit.pop()

  dq = deque([(h,w)])
  reachable = set([(h,w)])
  blacks = 0
  whites = 0
  if S[h][w]==1:
    blacks += 1
  else:
    whites += 1

  while dq:
    h,w = dq.pop()
    nexts = [(h-1,w),(h+1,w),(h,w-1),(h,w+1)]
    for nxt in nexts:
      if nxt in reachable:
        continue
      else:
        if S[h][w] + S[nxt[0]][nxt[1]]==0:
          to_visit.remove(nxt)
          dq.append(nxt)
          reachable.add(nxt)
          if S[nxt[0]][nxt[1]]==1:
            blacks +=1
          else:
            whites +=1

  answer += blacks * whites
print(answer)

Submission status: Accepted

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

P=[i for i in range(H*W)]
size=[[0,0]for i in range(H*W)]

for i in range(H):
    for j in range(W):
        if L[i][j]==".":
            size[i*W+j][0]+=1
        else:
            size[i*W+j][1]+=1
#print(size)

def find(z):
    if  z==P[z]:
        return z
    else:
        return find(P[z])
def union(x,y):
    X=find(x)
    Y=find(y)
    if sum(size[X])>=sum(size[Y]):
        P[Y]=P[X]
        size[X][0]+=size[Y][0]
        size[X][0]+=size[Y][1]
    else:
        P[X]=P[Y]
        size[Y][0]+=size[X][0]
        size[Y][0]+=size[X][1]
        
for i in range(H):
    for j in range(W):
        if j+1<=W-1:
            
            if L[i][j]!=L[i][j+1]:
                
                if find(i*W+j)!=find(i*W+j+1):
                    #print(i,j)
                    union(i*W+j,i*W+j+1)
        if i+1<=H-1:
            if L[i][j]!=L[i+1][j]:
                if find((i)*W+j)!=find((i+1)*W+j):
                    union(i*W+j,(i+1)*W+j)
BW=[[0,0]for i in range(H*W)]
for i in range(H):
    for j in range(W):
        if L[i][j]==".":
            BW[find(i*W+j)][0]+=1
        else:
            BW[find(i*W+j)][1]+=1

ans=0
for i in range(H):
    for j in range(W):
        if P[i*W+j]==i*W+j:
            ans+=BW[i*W+j][0]*BW[i*W+j][1]
#print(P)
#print(BW)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from itertools import product
import sys
input = sys.stdin.readline

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0]*n
    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.par[x] = y
            else:
                self.par[y] = x
            
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    

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

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

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

whitecnt = np.zeros(H*W, dtype=int)
blackcnt = np.zeros(H*W, dtype=int)

for i, j in product(range(H), range(W)):
    if S[i][j] == '.':
        whitecnt[uf.find(i*W+j)] += 1
    else:
        blackcnt[uf.find(i*W+j)] += 1

print(np.sum(whitecnt*blackcnt))

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(200000)

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


isVisited = [ [False]*W for _ in range(H) ]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
# (i, j) から行けるペアの数
def dfs( x, y ):
    isVisited[x][y] = True
    numBlack, numWhite = 0, 0
    if S[x][y] == '#': numBlack = 1
    else:              numWhite = 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx and nx < H and 0 <= ny and ny < W and not isVisited[nx][ny]:
            if S[x][y] != S[nx][ny]:
                tmpB, tmpW = dfs( nx, ny )
                numBlack += tmpB
                numWhite += tmpW
    return numBlack, numWhite

ans = 0
for i in range(H):
    for j in range(W):
        if not isVisited[i][j]: 
            numBlack, numWhite = dfs( i, j )
            ans += numBlack * numWhite

print( ans )

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int,input().split())
L = []
for i in range(H):
  L.append(list(input()))
TF = []
for i in range(H):
  K = [False]*W
  TF.append(K)
dy_dx = [[1,0],[0,1],[-1,0],[0,-1]]
que = deque([[0,0]])
TF[0][0] = True
ans = 0
cntblack,cntwhite = 0,0
[cury,curx] = [0,0]
if L[0][0] == '#':
  cntblack += 1
else:
  cntwhite += 1
while [cury,curx] != [H-1,W-1]:
  if len(que) != 0:
    cur = que.popleft()
    TF[cur[0]][cur[1]] = True
    for i in range(4):
      if 0 <= cur[0]+dy_dx[i][0] <= H-1 and 0 <= cur[1]+dy_dx[i][1] <= W-1:
        if L[cur[0]+dy_dx[i][0]][cur[1]+dy_dx[i][1]] != L[cur[0]][cur[1]]:
          if TF[cur[0]+dy_dx[i][0]][cur[1]+dy_dx[i][1]] == False:
            TF[cur[0]+dy_dx[i][0]][cur[1]+dy_dx[i][1]] = True
            if L[cur[0]+dy_dx[i][0]][cur[1]+dy_dx[i][1]] == '#':
              cntblack += 1
            else:
              cntwhite += 1
            que.append([cur[0]+dy_dx[i][0],cur[1]+dy_dx[i][1]])
  else:
    ans += cntblack*cntwhite
    cntblack,cntwhite = 0,0
    if TF[cury][curx] == False:
      que.append([cury,curx])
      if L[cury][curx] == '#':
        cntblack += 1
      else:
        cntwhite += 1
    else:
      if curx != W-1:
        curx +=1
      elif cury != H-1:
        cury += 1
        curx = 0
      else:
        print(ans)
        exit()
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

h, w = (int(i) for i in input().split())
a = [input() for i in range(h)]

class UnionFind():
    def __init__(self, N):
        self.par = [i for i in range(N)]
        self.size = [1] * N
        self.N = N

    # xのrootを返す
    def root(self, x):
        if self.par[x] == x:
            return x
        else: 
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    # x, yが同じrootの場合true
    def same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry

    # x,yのrootが違った場合、併合
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if self.size[rx] < self.size[ry]:
            self.par[rx] = ry
            self.size[ry] += self.size[rx]
        else:
            self.par[ry] = rx
            self.size[rx] += self.size[ry]
            
uf = UnionFind(h*w)

for j in range(h):
    for i in range(w):
        if i != w-1 and a[j][i+1] != a[j][i]:
            uf.unite(w*j+i,w*j+i+1)
        if j != h-1 and a[j+1][i] != a[j][i]:
            uf.unite(w*j+i,w*(j+1)+i)

for v in range(h*w):
    uf.root(v)

wc = [0]*(h*w)
bc = [0]*(h*w)
for j in range(h):
    for i in range(w):
        idx = w*j+i
        if a[j][i] == ".":
            wc[uf.par[idx]] += 1
        else:
            bc[uf.par[idx]] += 1

res = 0
for i in range(h*w):
    res += wc[i] * bc[i]
print(res)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n = II()
    h = II()
    w = II()
    print((n-h+1)*(n-w+1))
    return

#B
def B():
    n = II()
    a, b = LI()
    p = LI()
    p.sort()
    ans = [0 for i in range(3)]
    for p_ in p:
        if p_ <= a:
            ans[0] += 1
        elif a < p_ <= b:
            ans[1] += 1
        else:
            ans[2] += 1
    print(min(ans))
    return

#C
def C():
    h, w = LI()
    s = SR(h)
    def bfs(x, y):
        xy_ = [(0, -1), (1, 0), (0, 1), (-1, 0)]
        count1 = 1
        count2 = 0
        q = deque([])
        q.append((x,y))
        while q:
            x,y = q.popleft()
            for xy in xy_:
                x_, y_ = x + xy[0], y + xy[1]
                if 0 <= x_ < w and 0 <= y_ < h:
                    if s[y_][x_] != s[y][x] and field[y_][x_]:
                        field[y_][x_] = False
                        if s[y_][x_] == "#":
                            count1 += 1
                        else:
                            count2 += 1
                        q.append((x_, y_))
        return count1*count2
                        
    field = [[True for i in range(w)] for k in range(h)]
    ans = 0
    for y in range(h):
        for x in range(w):
            if s[y][x] == "#" and field[y][x]:
                field[y][x] = False
                ans += bfs(x, y)
    
    print(ans)
    
        
    return

#D
def D():
    n, q = LI()
    a = LI()
    xq = IR(n)

    for x in xq:
        print(ans[x])
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    C()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


#A
def A():
    n,h,w = IR(3)
    print((n-h+1)*(n-w+1))
    return

#B
def B():
    n = I()
    a,b = LI()
    p = LI()
    k = [0 for i in range(a+1)]
    k += [1 for i in range(b-a)]
    k += [2 for i in range(max(p)+1-b)]
    d = defaultdict(int)
    for i in p:
        d[k[i]] += 1
    ans = min(d[0],d[1],d[2])
    print(ans)
    return

#C
def C():
    h,w = LI()
    s = SR(h)
    bfs_map = [[-1 for i in range(w)] for j in range(h)]
    d = [[0,1],[0,-1],[1,0],[-1,0]]
    ans = 0
    for y in range(h):
        for x in range(w):
            if s[y][x] == "#":
                if bfs_map[y][x] < 0:
                    bfs_map[y][x] = 0
                    a = 1
                    b = 0
                    q = deque()
                    q.append([y,x])
                    while q:
                        n,m = q.popleft()
                        for dy,dx in d:
                            n2 = n+dy
                            m2 = m+dx
                            if 0 <= n2 < h and 0 <= m2 < w:
                                if s[n][m] != s[n2][m2] and bfs_map[n2][m2] < 0:
                                    if s[n2][m2] == "#":a += 1
                                    else:b += 1
                                    bfs_map[n2][m2] = 0
                                    q.append([n2,m2])
                    ans += a*b
    print(ans)
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Accepted

Solution code:
class Unionfind:

    __slots__ = ['nodes','rank']

    def __init__(self, n):
        self.nodes = list(range(n))
        self.rank = [0]*n

    def root(self, x):
        if self.nodes[x] == x:
            return x
        else:
            root_x = self.root(self.nodes[x])
            self.nodes[x] = root_x
            return root_x

    def unite(self, x, y):
        x = self.root(x); y = self.root(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            x, y = y, x
        self.rank[x] += self.rank[y]
        self.nodes[y] = x

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

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

H,W = map(int,input().split())
grid = [list(input()) for _ in range(H)]
uf = Unionfind(H*W)

for i in range(H):
    for j in range(W):
        for di,dj in around:
            ni = i + di; nj = j + dj
            if not(0 <= ni <= H-1 and 0 <= nj <= W-1):
                continue
            x = W*i+j; y = W*ni+nj
            if grid[i][j] != grid[ni][nj]:
                uf.unite(x,y)

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

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

for i,line in enumerate(grid):
    for j,c in enumerate(line):
        parent = uf.nodes[W*i+j]
        if c == ".":
            group[parent][0] += 1
        if c == "#":
            group[parent][1] += 1

ans = sum([w*b for w,b in group])
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
around = [(0,1),(1,0),(0,-1),(-1,0)]

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

checked = [[0]*W for i in range(H)]

def dfs(si,sj):
    if grid[si][sj] == ".":
        b = 0; w = 1
    if grid[si][sj] == "#":
        b = 1; w = 0
    dq = deque()
    dq.append((si,sj))
    checked[si][sj] = 1
    while dq:
        i,j = dq.pop()
        for di,dj in around:
            ni = i + di; nj = j + dj
            if not(0 <= ni <= H-1 and 0 <= nj <= W-1):
                continue
            if checked[ni][nj]:
                continue
            p = grid[i][j]
            np = grid[ni][nj]
            if (p,np) == (".","#"):
                b += 1
                dq.append((ni,nj))
                checked[ni][nj] = 1
            if (p,np) == ("#","."):
                w += 1
                dq.append((ni,nj))
                checked[ni][nj] = 1
    return b*w

ans = 0
for i in range(H):
    for j in range(W):
        if not checked[i][j] and grid[i][j] == ".":
            ans += dfs(i,j)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
around = [(0,1),(1,0),(0,-1),(-1,0)]

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

checked = [[0]*W for i in range(H)]

def bfs(si,sj):
    if grid[si][sj] == ".":
        b = 0; w = 1
    if grid[si][sj] == "#":
        b = 1; w = 0
    dq = deque()
    dq.append((si,sj))
    checked[si][sj] = 1
    while dq:
        i,j = dq.popleft()
        for di,dj in around:
            ni = i + di; nj = j + dj
            if not(0 <= ni <= H-1 and 0 <= nj <= W-1):
                continue
            if checked[ni][nj]:
                continue
            p = grid[i][j]
            np = grid[ni][nj]
            if (p,np) == (".","#"):
                b += 1
                dq.append((ni,nj))
                checked[ni][nj] = 1
            if (p,np) == ("#","."):
                w += 1
                dq.append((ni,nj))
                checked[ni][nj] = 1
    return b*w

ans = 0
for i in range(H):
    for j in range(W):
        if not checked[i][j] and grid[i][j] == ".":
            ans += bfs(i,j)
print(ans)

Submission status: Accepted

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

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

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

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

def dfs(i,j):
    checked[i][j] = 1
    for di,dj in around:
        ni = i + di; nj = j + dj
        if not(0 <= ni <= H-1 and 0 <= nj <= W-1):
            continue
        if checked[ni][nj]:
            continue
        p = grid[i][j]
        np = grid[ni][nj]
        if (p,np) == (".","#"):
            global b
            b += 1
            dfs(ni,nj)
        if (p,np) == ("#","."):
            global w
            w += 1
            dfs(ni,nj)

ans = 0
for i in range(H):
    for j in range(W):
        b = 0; w = 1
        if not checked[i][j] and grid[i][j] == ".":
            dfs(i,j)
        ans += b*w
print(ans)

Submission status: Accepted

Solution code:
# Mar 11, 12:14-
def inpl(): return list(map(int,input().split()))

H,W = inpl()
S = ''
for i in range(H):
    S += input()

N = H*W
parent = [-1]*N
white = [0]*N
black = [0]*N

def group(n):
    if parent[n] < 0:
        return n
    else:
        g = group(parent[n])
        parent[n] = g
        return g

def merge(m,n):
    gm = group(m)
    gn = group(n)
    if gm != gn:
        parent[gn] = gm
        white[gm] += white[gn]
        black[gm] += black[gn]
    return gm

def groupsize(n):
    g = group(n)
    return white[g]*black[g]

def place(n):
    return divmod(n,W)

def index(h,w):
    return h*W + w

for n in range(N):
    if S[n] == '.':
        white[n] = 1
    else:
        black[n] = 1

    h, w = place(n)
    if h > 0 and S[n] != S[n-W]:
        merge(n-W,n)
    if w > 0 and S[n] != S[n-1]:
        merge(n-1,n)    

groupset = set()
for n in range(N):
    groupset.add(group(n))

sizes = [ groupsize(p) for p in groupset ]
ans = sum(sizes)

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Mar  6 16:29:39 2019

@author: Yamazaki Kenichi
"""

H,W = map(int,input().split())
A = [input() for i in range(H)]
T = [[-1,0,0] for j in range(H*W)] 

def g(x,i,j):
    if x == '.':
        return 1 if (i+j)%2 == 0 else 2
    else:
        return 4 if (i+j)%2 == 0 else 3
def p(u):
    return T[u][0]
def findset(u):
    if p(u) == -1:
        return u
    else:
        T[u][0] = findset(p(u))
        return T[u][0]

def unite(u,v):
    if findset(u) == findset(v):
        return
#    if T[findset(u)[0]][findset(u)[1]][1]+T[findset(u)[0]][findset(u)[1]][0
#         ] >= T[findset(v)[0]][findset(v)[1]][0]+T[findset(v)[0]][findset(v)[1]][1]:
    T[findset(u)][1] += T[findset(v)][1]
    T[findset(u)][2] += T[findset(v)][2]
    T[findset(v)][0] = findset(u)
def unite_check(i1,j1,i2,j2):
    if g(A[i1][j1],i1,j1)%2 == 0 and g(A[i2][j2],i2,j2)%2 == 0:
        unite(i1 * W + j1, i2 * W + j2)
    elif g(A[i1][j1],i1,j1)%2 == 1 and g(A[i2][j2],i2,j2)%2 == 1:
        unite(i1 * W + j1, i2 * W + j2)

for i in range(H):
    for j in range(W):
        if g(A[i][j],i,j) <= 2:
            T[i * W + j][1] += 1
        else:
            T[i * W + j][2] += 1
        if i !=0:
            unite_check(i,j,i-1,j)
        if j !=0:
            unite_check(i,j,i,j-1)
ans = 0
for i in range(H):
    for j in range(W):
        if T[i * W + j][0] == -1:
            ans += T[i * W + j][1] * T[i * W + j][2]
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

now = 0
for i in range(H):
    for j in range(W):
        if flag[i][j] == -1:
            stack = deque([]) 
            stack.append([i, j])
            flag[i][j] = now
            while len(stack) > 0:
                y, x = stack.popleft()
                for nx, ny in ([1, 0], [0, 1], [-1, 0], [0, -1]):
                    if 0<= x + nx < W and 0 <= y + ny < H:
                        if S[y][x] != S[y+ny][x+nx] and flag[y+ny][x+nx] == -1:
                            stack.append([y+ny, x+nx])
                            flag[y+ny][x+nx] = now
            now += 1
    
Black = [0 for _ in range(now+1)]
White = [0 for _ in range(now+1)]

for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            Black[flag[i][j]] += 1
        else:
            White[flag[i][j]] += 1
   
res = 0
for i in range(now + 1):
    res += Black[i] * White[i]
    
print(res)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
S=[input() for i in range(H)]
visit=[[False]*W for i in range(H)]
par=[[None]*W for i in range(H)]
dd={}
X=[-1,0,1,0]
Y=[0,-1,0,1]
for j in range(H):
    for i in range(W):
        if visit[j][i]:
            continue
        if S[j][i]=='.':
            continue
        lH=[]
        lH.append((j,i,0))#0が黒
        par[j][i]=(i,j)
        num=0
        while lH:
            y,x,t=lH.pop()
            visit[y][x]=True
            for k in range(4):
                nx=x+X[k]
                ny=y+Y[k]
                if 0<=nx<W and 0<=ny<H:
                    if visit[ny][nx]:
                        continue
                    if t==0 and S[ny][nx]=='.':
                        visit[ny][nx]=True
                        num+=1
                        lH.append((ny,nx,1))
                    elif t==1 and S[ny][nx]=='#':
                        visit[ny][nx] = True
                        par[ny][nx]=(i,j)
                        lH.append((ny,nx,0))
        dd[(i,j)]=num
ans=0
for j in range(H):
    for i in range(W):
        if S[j][i]=='#':
            x,y=par[j][i]
            ans+=dd[(x,y)]
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


# aとbの最大公約数
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


# aとbの最小公倍数
def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def solve(y, x, field, used):

    num_white, num_black = 0, 0
    que = deque()
    que.append((y, x))
    used[y][x] = True

    while len(que) != 0:
        now = que.pop()

        if field[now[0]][now[1]] == '.':
            num_white += 1
        else:
            num_black += 1

        for i in range(4):
            ny = now[0] + dy4[i]
            nx = now[1] + dx4[i]

            if inside(ny, nx, len(field), len(field[0])):
                if field[ny][nx] != field[now[0]][now[1]]:
                    if not used[ny][nx]:
                        que.append((ny, nx))
                        used[ny][nx] = True

    return num_white * num_black


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

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

    ans = 0
    for y in range(H):
        for x in range(W):
            if not used[y][x]:
                ans += solve(y, x, field, used)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict as dd

n, mm = [int(i) for i in input().split()]
c = 0
A = []

m = dd(tuple)

for i in range(n):
    B = input()
    for j in range(mm):
        m[(i, j)]=c
        c+=1
    A.append([i=='#' for i in B])

par = [i for i in range(c)]

def find(a):
    if par[a] == a:
        return a
    par[a] = find(par[a])
    return par[a]

def unite(a, b):
    if a < b:
        a, b = b, a
    par[find(a)] = find(b)

def issafe(x,y):
    return x>=0 and x<n and y>=0 and y<mm

for i in range(n):
    for j in range(mm):
        dx = [[-1, 0], [0, 1], [0, -1], [1, 0]]
        for k in range(len(dx)):
            if issafe(i+dx[k][0], j+dx[k][1]) and A[i][j] != A[i+dx[k][0]][j+dx[k][1]]:
                unite(m[(i, j)], m[(i+dx[k][0], j+dx[k][1])])
                
bl = [0]*c
wh = [0]*c

for i in range(n):
    for j in range(mm):
        if A[i][j] == 1:
            bl[find(m[i, j])]+=1
        else:
            wh[find(m[i, j])]+=1

ans = 0
for i in range(c):
    ans += bl[i]*wh[i]

print(ans)