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**7)
h,w = map(int,input().split())
s = [list(input()) for i in range(h)]

dp = [[-1]*w for i in range(h)]

co = [0]
dx = [0,0,1,-1]
dy = [1,-1,0,0]
def dfs(x,y,c):
    count = 0
    dp[x][y] = 1
    if s[x][y] == "#":
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] == "." and dp[nx][ny] == -1:
                count += 1
                count += dfs(nx,ny,c+1)
    elif s[x][y] == ".":
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] == "#" and dp[nx][ny] == -1:
                l.append((nx,ny))
                count += dfs(nx,ny,c+1)
    return count
            
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            l = []
            count = dfs(i,j,0)
            ans += count*(len(l)+1)
            s[i][j] = "x"
            for x,y in l:
                s[x][y] = "x"
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
S = [['.']*(W+2)] + [['.'] + list(input()) + ['.'] for _ in range(H)] + [['.']*(W+2)]
for i in range(1, H+1):
  S[i][0] = S[i][1]
  S[i][-1] = S[i][-2]
for i in range(1, W+1):
  S[0][i] = S[1][i]
  S[-1][i] = S[-2][i]
S[0][0] = S[0][1]
S[-1][0] = S[-2][0]
S[0][-1] = S[0][-2]
S[-1][-1] = S[-2][-1]
V = [[0 for _ in range(W+2)] for i in range(H+2)]
num = 0
for i in range(1, H+1):
  for j in range(1, W+1):
    if S[i][j] == '#' and V[i][j] == 0:
      V[i][j] = 1
      p = [[i, j]]
      cnt = 1
      pnt = 0
      D = {'.': 0, '#': 0}
      D[S[i][j]] = 1
      while pnt < cnt:
        n = cnt
        for k in range(pnt, cnt):
          x = p[k][:]
          y = S[x[0]][x[1]][:]
          if S[x[0]-1][x[1]] != y and V[x[0]-1][x[1]] == 0:
            V[x[0]-1][x[1]] = 1
            p.append([x[0]-1, x[1]])
            D[S[x[0]-1][x[1]]] += 1
            cnt += 1
          if S[x[0]+1][x[1]] != y and V[x[0]+1][x[1]] == 0:
            V[x[0]+1][x[1]] = 1
            p.append([x[0]+1, x[1]])
            D[S[x[0]+1][x[1]]] += 1
            cnt += 1
          if S[x[0]][x[1]-1] != y and V[x[0]][x[1]-1] == 0:
            V[x[0]][x[1]-1] = 1
            p.append([x[0], x[1]-1])
            D[S[x[0]][x[1]-1]] += 1
            cnt += 1
          if S[x[0]][x[1]+1] != y and V[x[0]][x[1]+1] == 0:
            V[x[0]][x[1]+1] = 1
            p.append([x[0], x[1]+1])
            D[S[x[0]][x[1]+1]] += 1
            cnt += 1
        pnt = n
      num += D['.'] * D['#']
print(num)

Submission status: Accepted

Solution code:
from collections import deque
def bfs(S,H,W,sh,sw):
    black,white=0,0
    d=deque()
    d.append([sh,sw])
    if S[sh][sw]=='#':
        black+=1
    elif S[sh][sw]=='.':
        white+=1
    seen[sh][sw]=1
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    while(len(d)!=0):
        h=d[0][0]
        w=d[0][1]
        d.popleft()
        for dir in range(4):
            nh=h+dx[dir]
            nw=w+dy[dir]
            if(nh>H-1 or nh<0 or nw>W-1 or nw<0):
                continue
            if(seen[nh][nw] or S[nh][nw]==S[h][w]):
                continue
            if S[nh][nw]=='#':
                black+=1
            else:
                white+=1
            seen[nh][nw]=1
            d.append([nh,nw])
    return white,black

H,W=map(int,input().split())
G=[list(input()) for i in range(H)]
seen=[[0]*W for i in range(H)]
ans=0

for i in range(H):
    for j in range(W):
        if not seen[i][j]:
            w,b=bfs(G,H,W,i,j)
            ans+=w*b
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
h , w = map(int,input().split())
ma = [list(input()) for i in range(h)]
visit = [[False for i in range(w)] for j in range(h)]
ans = 0
muki = [(0,1),(0,-1),(1,0),(-1,0)]
for i in range(h):
    for j in range(w):
        if ma[i][j] == "#" and not visit[i][j]:
            visit[i][j] = True
            d = deque()
            d.append((i,j,1))
            kuro = 1
            siro = 0
            while d:
                nowx , nowy , p = d.popleft()
                for a,b in muki:
                    nex = nowx + a
                    ney = nowy + b
                    if 0 <= nex <= h-1 and 0 <= ney <= w-1:
                        if not visit[nex][ney]:
                            if p == 1 and ma[nex][ney] == ".":
                                d.append((nex,ney,0))
                                siro += 1
                                visit[nex][ney] = True
                            if p == 0 and ma[nex][ney] == "#":
                                d.append((nex,ney,1))
                                kuro += 1
                                visit[nex][ney] = True
            ans += kuro*siro
print(ans)

Submission status: Accepted

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

dct = {"#": 0, ".": 1, "-": 2}


def f(c):
    return dct[c]


h, w = map(int, input().split())
s = [[2] * (w + 2)]
for _ in range(h):
    s.append([2] + list(map(f, input())) + [2])
s.append([2] * (w + 2))

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


def dfs(col, hh, ww):
    if s[hh][ww] != col:
        return

    cnt[col] += 1
    s[hh][ww] = 2

    for dh, dw in d:
        nh = hh + dh
        nw = ww + dw
        dfs(1-col, nh, nw)


ans = 0
for hi in range(1, h + 1):
    for wi in range(1, w + 1):
        cnt = [0, 0]
        if s[hi][wi] != 2:
            dfs(s[hi][wi], hi, wi)
        ans += cnt[0] * cnt[1]

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/aising2019/tasks/aising2019_c

import sys
sys.setrecursionlimit(10 ** 7)

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


def dfs(h, w, ph, pw):
    if M[h][w] == '.':
        bc, wc = 0, 1
    else:
        bc, wc = 1, 0
    for (dh, dw) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        nh, nw = h + dh, w + dw
        if nh < 0 or H <= nh or nw < 0 or W <= nw:
            continue
        if nh == ph and nw == pw:
            continue
        if seen[nh][nw]:
            continue
        if M[nh][nw] == M[h][w]:
            continue
        seen[nh][nw] = True
        b_add, w_add = dfs(nh, nw, h, w)
        bc += b_add
        wc += w_add
    return bc, wc

ans = 0
for h in range(H):
    for w in range(W):
        if seen[h][w] == False:
            seen[h][w] = True
            b, w = dfs(h, w, -1, -1)
            ans += b * w
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
h, w = map(int, input().split())
s = [input() for _ in range(h)]
seen = [[False for _ in range(w)] for _ in range(h)]

def dfs(bx, by, sx, sy):
    if s[sx][sy] == '.':
        b_cnt, w_cnt = 0, 1
    else:
        b_cnt, w_cnt = 1, 0
    for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        px, py = sx + dx, sy + dy
        #print('=', px, py)
        if bx == px and by == py:
            #print(px, py, 'flg1')
            continue
        if px < 0 or h <= px or py < 0 or w <= py:
            #print(px, py, 'flg2')
            continue
        if seen[px][py]:
            #print(px, py, 'flg3')
            continue
        if s[sx][sy] == s[px][py]:
            #print(px, py, 'flg4')
            continue
        seen[px][py] = True
        b_add, w_add = dfs(sx, sy, px, py)
        b_cnt += b_add
        w_cnt += w_add

    return b_cnt, w_cnt

ans = 0
#print(dfs(-1, -1, 1, 1))
for i in range(h):
    for j in range(w):
        if seen[i][j] == False:
            seen[i][j] = True
            b_cnt, w_cnt = dfs(-1, -1, i, j)
            ans += b_cnt * w_cnt

print(ans)

Submission status: Accepted

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

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

visited = set()
def dfs(x, y, c, white, black):
  global visited
  for dx, dy in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
    xx = x + dx; yy = y + dy
    if 0<=xx<H and 0<=yy<W and (xx, yy) not in visited and S[xx][yy]!=c:
      cc = S[xx][yy]
      if cc == '.':
        white += 1
      else:
        black += 1
      visited.add((xx, yy))
      white, black = dfs(xx, yy, cc, white, black)
  return white, black

ans = 0
for x in range(H):
  for y in range(W):
    if (x, y) not in visited:
      visited.add((x, y))
      c = S[x][y]
      if c == '.':
        white = 1; black = 0
      else:
        white = 0; black = 1
      white, black = dfs(x, y, c, white, black)
      ans += white * black

print(ans)

Submission status: Accepted

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

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

visited = set()
def dfs(x, y, c, white, black):
  global visited
  for dx, dy in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
    xx = x + dx; yy = y + dy
    if 0<=xx<H and 0<=yy<W and (xx, yy) not in visited and S[xx][yy]!=c:
      cc = S[xx][yy]
      if cc == '.':
        white.add((xx, yy))
      else:
        black.add((xx, yy))
      visited.add((xx, yy))
      white, black = dfs(xx, yy, cc, white, black)
  return white, black

ans = 0
for x in range(H):
  for y in range(W):
    if (x, y) not in visited:
      visited.add((x, y))
      c = S[x][y]
      if c == '.':
        white = set(((x, y), )); black = set()
      else:
        white = set(); black = set(((x, y), ))
      white, black = dfs(x, y, c, white, black)
      ans += len(white) * len(black)

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**6)
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
dx = (0, 0, 1, -1)
dy = (1, -1, 0, 0)
seen = [[False] * w for _ in range(h)]

numb = 0
numw = 0


def dfs(x, y):
    global numb, numw
    seen[x][y] = True
    if s[x][y] == '#':
        numb += 1
    else:
        numw += 1
    for di in range(4):
        nx = x + dx[di]
        ny = y + dy[di]
        if (nx < 0 or nx >= h or ny < 0 or ny >= w):
            continue
        if s[x][y] == s[nx][ny]:
            continue
        if seen[nx][ny]:
            continue
        dfs(nx, ny)


ans = 0
for x in range(h):
    for y in range(w):
        if seen[x][y]:
            continue
        if s[x][y] == '.':
            continue
        numb = 0
        numw = 0
        dfs(x, y)
        ans += numb * numw
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
dx = (0, 0, 1, -1)
dy = (1, -1, 0, 0)
seen = [[False] * w for _ in range(h)]

numb = 0
numw = 0


def dfs(x, y):
    global numb, numw
    seen[x][y] = True
    if s[x][y] == '#':
        numb += 1
    else:
        numw += 1
    for di in range(4):
        nx = x + dx[di]
        ny = y + dy[di]
        if (nx < 0 or nx >= h or ny < 0 or ny >= w):
            continue
        if s[x][y] == s[nx][ny]:
            continue
        if seen[nx][ny]:
            continue
        dfs(nx, ny)


ans = 0
for x in range(h):
    for y in range(w):
        if seen[x][y]:
            continue
        if s[x][y] == '.':
            continue
        numb = 0
        numw = 0
        dfs(x, y)
        ans += numb * numw
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

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

for row in range(H):
    for col in range(W):
        if not visited[row][col]:
            visited[row][col] = True
            d = deque([[row, col]])
            if s[row][col] == ".":
                passed_black, passed_white = 0, 1
            else:
                passed_black, passed_white = 1, 0

            while d:
                now_row, now_col = d.popleft()
                visited[now_row][now_col] = True
                for new_row, new_col in [[now_row+1, now_col], [now_row-1, now_col], [now_row, now_col+1], [now_row, now_col-1]]:
                    if 0 <= new_row <= H-1 and 0 <= new_col <= W-1 and s[now_row][now_col] != s[new_row][new_col] and not visited[new_row][new_col]:
                        d.append([new_row, new_col])
                        visited[new_row][new_col] = True
                        if s[new_row][new_col] == ".":
                            passed_white += 1
                        else:
                            passed_black += 1

            ans += passed_black * passed_white

print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

H, W = getNM()
maze = []
for i in range(H):
    m = list(input())
    maze.append(m)

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

memo = [[-1] * W for i in range(H)]

def counter(sx, sy):
    black_cnt = 0
    white_cnt = 0

    memo[sy][sx] = 1
    if maze[sy][sx] == "#":
        black_cnt += 1
    else:
        white_cnt += 1

    pos = deque([[sx, sy]])

    while len(pos) > 0:
        x, y = pos.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < W and 0 <= ny < H and maze[ny][nx] != maze[y][x] and memo[ny][nx] == -1:
                memo[ny][nx] = 1
                pos.append([nx, ny])
                if maze[ny][nx] == "#":
                    black_cnt += 1
                else:
                    white_cnt += 1
    return black_cnt * white_cnt

ans = 0
for i in range(H):
    for j in range(W):
        ans += counter(j, i)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

d_i = [-1, 0, 1, 0]
d_j = [0, -1, 0, 1]

ans = 0
visited = [[False]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if visited[i][j]:
            continue
        b = 0
        wh = 0
        q = deque()
        q.append((i,j))
        visited[i][j] = True
        while len(q) > 0:
            c_h, c_w = q.pop()
            if s[c_h][c_w] == '#':
                b += 1
            else:
                wh += 1
            for dir in range(4):
                n_h = c_h+d_i[dir]
                n_w = c_w+d_j[dir]
                if n_h < 0 or h-1 < n_h or n_w < 0 or w-1 < n_w:
                    continue
                if visited[n_h][n_w]:
                    continue
                if s[c_h][c_w] == s[n_h][n_w]:
                    continue
                q.append((n_h, n_w))
                visited[n_h][n_w] = True
        ans += b*wh
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
s = []
for _ in range(h):
    s.append(input())
dxdy = [(-1,0), (0,-1), (0,1), (1,0)]
seen = [[False]*w for _ in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if seen[i][j]:
            continue
        q = deque([(j, i)])
        cnt = [0, 0]
        cnt[int(s[i][j]=='#')] += 1
        seen[i][j] = True
        while q:
            x, y = q.popleft()
            for dx, dy in dxdy:
                if not (0<=x+dx<w and 0<=y+dy<h):
                    continue
                if seen[y+dy][x+dx] or s[y][x]==s[y+dy][x+dx]:
                    continue
                cnt[int(s[y+dy][x+dx]=='#')] += 1
                seen[y+dy][x+dx] = True
                q.append((x+dx, y+dy))
        ans += cnt[0]*cnt[1]
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(410000)

h,w = map(int,input().split())
F = []
for i in range(h):
  F.append(list(input()))
  
V = [[False]*w for _ in range(h)]

def dfs(y,x,c):      
  V[y][x] = True
  black = 0
  white = 0
  if c =='#':
    black+=1
  else:
    white+=1
  for dy,dx in [(-1,0),(0,1),(1,0),(0,-1)]:
    ny = y + dy
    nx = x + dx
    if 0<=ny<h and 0<=nx<w:      
      if F[ny][nx]!=c and V[ny][nx] == False:
        nc = '#'
        if c =='#':
          nc = '.'
        bn,wn = dfs(ny,nx,nc)
        black += bn
        white += wn  
  return black,white
        
ans = 0
for i in range(h):
  for j in range(w):
    if F[i][j] == '#':      
      black,white = dfs(i,j,'#')
      ans += black*white
      
print(ans)

Submission status: Accepted

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)
MOD = 10 ** 9 + 7
INF = float("inf")


def main():
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    seen = [[False] * W for _ in range(H)]
    black = [0]
    white = [0]

    def dfs(x, y):
        seen[x][y] = True
        if S[x][y] == "#":
            black[-1] += 1
        else:
            white[-1] += 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if not (0 <= nx < H and 0 <= ny < W):
                continue
            if S[x][y] == S[nx][ny]:
                continue
            if seen[nx][ny]:
                continue
            dfs(nx, ny)

    answer = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == ".":
                continue
            if seen[h][w]:
                continue
            black.append(0)
            white.append(0)
            dfs(h, w)

    for i in range(len(black)):
        answer += black[i] * white[i]
    print(answer)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


def dfs(maze, H, W, sh, sw, gh, gw):
    visited = [[False] * W for _ in range(H)]
    visited[sh][sw] = True
    q = deque([(sh, sw)])
    while q:
        h, w = q.pop()
        if h == gh and w == gw:
            return True
        for dh, dw in [(1, 0), (-1, 0), (0, -1), (0, 1)]:
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W:
                if not visited[nh][nw]:
                    if maze[nh][nw] == ".":
                        visited[nh][nw] = True
                        q.append((nh, nw))
    return False


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

    def dfs(x, y, black, white):
        q = deque([(x, y)])
        while q:
            X, Y = q.pop()
            if seen[X][Y]:
                continue
            seen[X][Y] = True
            if S[X][Y] == "#":
                black += 1
            else:
                white += 1
            for i in range(4):
                nx = X + dx[i]
                ny = Y + dy[i]
                if not (0 <= nx < H and 0 <= ny < W):
                    continue
                if S[X][Y] == S[nx][ny]:
                    continue
                if seen[nx][ny]:
                    continue
                q.append((nx, ny))
        return black, white

    answer = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == ".":
                continue
            if seen[h][w]:
                continue
            black = 0
            white = 0
            black, white = dfs(h, w, black, white)
            answer += black * white

    print(answer)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

    def dfs(sh, sw):
        q = deque([(sh, sw)])
        seen[sh][sw] = True
        black = 0
        white = 0
        if S[sh][sw] == "#":
            black += 1
        else:
            white += 1

        while q:
            h, w = q.popleft()

            for dh, dw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                nh = h + dh
                nw = w + dw

                if 0 <= nh < H and 0 <= nw < W:
                    if seen[nh][nw]:
                        continue
                    if S[h][w] == S[nh][nw]:
                        continue

                    seen[nh][nw] = True
                    q.append((nh, nw))
                    if S[nh][nw] == "#":
                        black += 1
                    else:
                        white += 1

        return black * white

    ans = 0
    for h in range(H):
        for w in range(W):
            if seen[h][w]:
                continue
            ans += dfs(h, w)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]
dij=[(1,0),(0,1),(-1,0),(0,-1)]

def main():
    h,w=MI()
    ss=[SI() for _ in range(h)]

    def dfs(i,j):
        stack=[(i,j)]
        bc,wc=0,0
        while stack:
            i,j=stack.pop()
            if ss[i][j]=="#":bc+=1
            else:wc+=1
            for di,dj in dij:
                ni,nj=i+di,j+dj
                if ni<0 or nj<0 or ni>=h or nj>=w:continue
                if fin[ni][nj] or ss[i][j]==ss[ni][nj]:continue
                fin[ni][nj]=True
                stack.append((ni,nj))
        return bc,wc

    ans=0
    fin=[[False]*w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if fin[i][j]:continue
            fin[i][j]=True
            bc,wc=dfs(i,j)
            ans+=bc*wc
    print(ans)

main()

Submission status: Accepted

Solution code:
from collections import deque

def main():
    H, W = map(int, input().split())
    S = list(list(input()) for _ in range(H))
    visited = [[False] * W for _ in range(H)]
    blacks = []
    ans = 0
    dh = [0,1,0,-1]
    dw = [1,0,-1,0]
    for h in range(H):
        for w in range(W):
            if S[h][w] == '#':
                blacks.append((h,w))

    for h, w in blacks:
        if not visited[h][w]:
            Q = deque([(h,w)])
            white = 0
            black = 1
            visited[h][w] = True
            while Q:
                i, j = Q.popleft()
                now = S[i][j]

                for n in range(4):
                    nh = i + dh[n]
                    nw = j + dw[n]

                    if 0 <= nh < H and 0 <= nw < W:
                        if not visited[nh][nw]:
                            if now != S[nh][nw]:
                                visited[nh][nw] = True
                                Q.append((nh,nw))
                                if S[nh][nw] == '.':
                                    white += 1
                                else:
                                    black += 1
            ans += white * black

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

def main():
    H, W = map(int, input().split())
    S = list(list(input()) for _ in range(H))
    visited = [[False] * W for _ in range(H)]
    blacks = []
    ans = 0
    dh = [0,1,0,-1]
    dw = [1,0,-1,0]
    for h in range(H):
        for w in range(W):
            if S[h][w] == '#':
                blacks.append((h,w))

    for h, w in blacks:
        if not visited[h][w]:
            Q = deque([(h,w)])
            white = 0
            black = 1
            visited[h][w] = True
            while Q:
                i, j = Q.pop()
                now = S[i][j]

                for n in range(4):
                    nh = i + dh[n]
                    nw = j + dw[n]

                    if 0 <= nh < H and 0 <= nw < W:
                        if not visited[nh][nw]:
                            if now != S[nh][nw]:
                                visited[nh][nw] = True
                                Q.append((nh,nw))
                                if S[nh][nw] == '.':
                                    white += 1
                                else:
                                    black += 1
            ans += white * black

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

grid = [readline().rstrip() for i in range(H)]

visited = set()
ans = 0
from collections import deque
cases = ((0,1),(0,-1),(1,0),(-1,0))
for i in range(H):
  for j in range(W):
    if (i,j) in visited:
      continue
    if grid[i][j] == ".":
      continue
    q = deque()
    black = 0
    white = 0
    q.append([i,j,1])
    aim = ".#"
    while q:
      y,x,isblack = q.popleft()
      if (y,x) in visited:
        continue
      if aim[isblack] != grid[y][x]:
        continue
      visited.add((y,x))
      if isblack:
        black += 1
      else:
        white += 1
      isblack ^= 1
      for c in cases:
        if 0 <= y + c[0] < H and 0 <= x + c[1] < W:
          q.append([y + c[0],x + c[1],isblack])
    ans += black * white
print(ans)

Submission status: Accepted

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

used = [[0]*W for _ in range(H)]
q = deque()
ans = 0
for i in range(H):
    for j in range(W):
        if used[i][j] == 1:
            continue
        if S[i][j] == ".":
            continue
        dic = {"#":1, ".":0}
        q.append((i, j, "#"))
        used[i][j] = 1
        while q:
            temp = q.popleft()
            k = temp[0]
            l = temp[1]
            f = temp[2]
            if f == "#":
                f = "."
            else:
                f = "#"
            if k > 0 and S[k-1][l] == f and used[k-1][l] == 0:
                used[k-1][l] = 1
                dic[f] += 1
                q.append((k-1, l, f))
            if k < H-1 and S[k+1][l] == f and used[k+1][l] == 0:
                used[k+1][l] = 1
                dic[f] += 1
                q.append((k+1, l, f))
            if l > 0 and S[k][l-1] == f and used[k][l-1] == 0:
                used[k][l-1] = 1
                dic[f] += 1
                q.append((k, l-1, f))
            if l < W-1 and S[k][l+1] == f and used[k][l+1] == 0:
                used[k][l+1] = 1
                dic[f] += 1
                q.append((k, l+1, f))
        ans += dic["#"]*dic["."]

print(ans)

Submission status: Accepted

Solution code:
#エイシング プログラミング コンテスト 2019 -C Alternating Path
"""
s(#に限る),g(.に限る)の座標を任意に定めたとき、
4近傍で#.#.#.と交互に移動できるものの数を求めよ
(但し、s,gが同一でそのような道が複数あっても、1つしかカウントしない)
各#から何回.を通れるかをdfsで求めれば良い。
ちなみに、その時に#を通れば、その#は今dfsを行っている#と同じだけの組み合わせ
を持つので、端折って良い。
"""
import sys
from collections import deque
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
H,W = map(int,readline().split())
maze = []
for _ in range(H):
    maze += [list(readline().rstrip().decode())]
used = [[0]*W for _ in range(H)]
def dfs(y,x):
    white = 0
    black = 1
    deq = deque([(y,x)])
    used[y][x] = 1
    while deq:
        fr = deq.pop()
        for go in [(0,1),(1,0),(0,-1),(-1,0)]:
            if 0 <= fr[0]+go[0] < H and 0 <= fr[1]+go[1] < W:
                if not used[fr[0]+go[0]][fr[1]+go[1]]:
                    if maze[fr[0]][fr[1]] != maze[fr[0]+go[0]][fr[1]+go[1]]:
                        deq.append((fr[0]+go[0],fr[1]+go[1]))
                        used[fr[0]+go[0]][fr[1]+go[1]] = 1
                        if maze[fr[0]+go[0]][fr[1]+go[1]] == ".":
                            white += 1
                        else:
                            black += 1
    
    return white * black
ans = 0
for i in range(H):
    for j in range(W):
        if not used[i][j] and maze[i][j] == "#":
            ans += dfs(i,j)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

from collections import defaultdict
rows, cols = map(int, input().split())
n = rows*cols
ns = defaultdict(set)
ss = [None] * rows
color = [None] * n
for i in range(rows):
    s = input()
    ss[i] = s
    for j,c in enumerate(s):
        u = i*cols+j
        color[u] = c
        if i>0:
            if c!=ss[i-1][j]:
                v = u - cols
                ns[u].add(v)
                ns[v].add(u)
        if j>0:
            if c!=s[j-1]:
                v = u - 1
                ns[u].add(v)
                ns[v].add(u)
seen = [False] * n
ans = 0
for u in range(n):
    if seen[u]:
        continue
    q = [u]
    s = set([u])
    while q:
        u = q.pop()
        for v in ns[u]:
            if seen[v]:
                continue
            seen[v] = True
            s.add(v)
            q.append(v)
    ans += sum(color[item]=="#" for item in s) * sum(color[item]=="." for item in s)
print(ans)