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:
H,W = map(int,input().split())
S = [[c==".#"[(i+j)%2] for j,c in enumerate(input())] for i in range(H)]#(0,0)が黒のときFalse
V = [[-1]*W for _ in [0]*H]
ans = 0
for si in range(H):
    for sj in range(W):
        if V[si][sj] != -1:continue
        V[si][sj] = 0
        cnt = [0,0]
        cnt[(S[si][sj]+si+sj)%2]+=1
        q = [[si,sj]]
        while q:
            i,j = q.pop()
            for di,dj in ((1,0),(-1,0),(0,1),(0,-1)):
                if (not (0<=i+di<H)) or (not (0<=j+dj<W)):continue
                if V[i+di][j+dj] != -1:continue
                if S[i][j] != S[i+di][j+dj]:continue
                V[i+di][j+dj] = V[i][j]
                q.append([i+di,j+dj])
                cnt[(S[i][j]+i+di+j+dj)%2] += 1
        ans += cnt[0]*cnt[1]
print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
s=["?"*(w+2)]+["?"+input()+"?" for _ in [0]*h]+["?"*(w+2)]
memo=[[None for _ in range(w)] for _ in range(h)]
cnt=0
for i in range(1,h+1):
    for j in range(1,w+1):
        if memo[i-1][j-1]==None:
            memo[i-1][j-1]=True
            maru=(s[i][j]==".")
            batsu=1-maru
            q=[(i,j)]
            while(q):
                qq=[]
                for k,l in q:
                    if s[k-1][l]!="?":
                        if memo[k-2][l-1]==None:
                            if s[k-1][l]!=s[k][l]:
                                memo[k-2][l-1]=True
                                qq.append((k-1,l))
                                if s[k-1][l]==".":
                                    maru+=1
                                else:
                                    batsu+=1
                    if s[k+1][l]!="?":
                        if memo[k][l-1]==None:
                            if s[k+1][l]!=s[k][l]:
                                memo[k][l-1]=True
                                qq.append((k+1,l))
                                if s[k+1][l]==".":
                                    maru+=1
                                else:
                                    batsu+=1
                    if s[k][l-1]!="?":
                        if memo[k-1][l-2]==None:
                            if s[k][l-1]!=s[k][l]:
                                memo[k-1][l-2]=True
                                qq.append((k,l-1))
                                if s[k][l-1]==".":
                                    maru+=1
                                else:
                                    batsu+=1
                    if s[k][l+1]!="?":
                        if memo[k-1][l]==None:
                            if s[k][l+1]!=s[k][l]:
                                memo[k-1][l]=True
                                qq.append((k,l+1))
                                if s[k][l+1]==".":
                                    maru+=1
                                else:
                                    batsu+=1
                q=qq
            cnt+=maru*batsu
print(cnt)

Submission status: Accepted

Solution code:
import sys
from sys import stdin
sys.setrecursionlimit(10**7)
dx = (1, 0, -1, 0)
dy = (0, 1, 0, -1)
H, W = [int(_) for _ in stdin.readline().rstrip().split()]
field = [list(stdin.readline().rstrip()) for _ in range(H)]
seen = [[False for i in range(400)] for j in range(400)]
num_b, num_w = 0, 0
ans = 0

def dfs(h, w):
    seen[h][w] = True
    if field[h][w] == '#':
        global num_b
        num_b += 1
    else:
        global num_w
        num_w += 1

    for direction in range(4):
        nh = h + dx[direction]
        nw = w + dy[direction]

        if nh < 0 or nh >= H or nw < 0 or nw >= W:
            continue
        if field[nh][nw] == field[h][w]:
            continue
        if seen[nh][nw]:
            continue

        dfs(nh, nw)

for i in range(H):
    for j in range(W):
        if field[i][j] == '.':
            continue
        if seen[i][j]:
            continue
        num_b, num_w = 0, 0
        dfs(i, j)
        ans += num_b * num_w 

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
h, w = [int(item) for item in input().split()]
field = []
for i in range(h):
    field.append(input().rstrip())

black = 0; white = 0
visited = [[0] * w for _ in range(h)]

def dfs(is_black, i, j):
    global black
    global white
    visited[i][j] = 1
    for x, y in [[1,0], [0,1], [0,-1], [-1,0]]:
        if i+x < 0 or i+x >= h or j+y < 0 or j+y >= w:
            continue
        if visited[i + x][j + y] != 0:
            continue
        if is_black:
            if field[i+x][j+y] == ".":
                white += 1
                dfs(False, i+x, j+y)
        if not is_black:
            if field[i+x][j+y] == "#":
                black += 1
                dfs(True, i+x, j+y)

ans = 0
for i in range(h):
    for j in range(w):
        if visited[i][j] != 0:
            continue
        if field[i][j] == "#":
            white = 0; black = 1
            dfs(True, i, j)
        else:
            white = 1; black = 0
            dfs(False, i, j)
        ans += white * black

print(ans)

Submission status: Accepted

Solution code:
from collections import deque


def bfs(y,x):
    global s
    global fl
    global h
    global w
    global ans
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    count = 1
    black = 0
    d = deque()
    # appendするときに計算する
    d.append([y,x])
    fl[y][x] = 1
    if s[y][x]=='#':
        black+=1
    while len(d):
        p = d.pop()
        for k in range(4):
            if 0<=p[1]+dx[k] <w and 0<=p[0]+dy[k] <h and s[p[0]][p[1]]!=s[p[0]+dy[k]][p[1]+dx[k]]:
                if fl[p[0]+dy[k]][p[1]+dx[k]]:
                    continue
                d.append([p[0]+dy[k],p[1]+dx[k]])
                count += 1
                fl[p[0]+dy[k]][p[1]+dx[k]] = 1
                if s[p[0]+dy[k]][p[1]+dx[k]]=='#':
                    black+=1
    ans += black*(count-black)


h, w = map(int, input().split())
s = [input() for i in range(h)]
fl = [[0 for _ in range(w)] for _ in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if not fl[i][j]:
            bfs(i,j)
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

direction = []
for i in range(4):
    dx = 5 % (i + 1) - 1
    dy = 5 % (i + 2) - 1
    direction.append((dx, dy))
H, W = map(int, input().split())
grid = [input() for _ in range(H)]
visited = [[False for _ in range(W)] for _ in range(H)]
ans = 0
for i, j in product(range(H), range(W)):
    if visited[i][j]: continue
    stack = [(i, j)]
    black = 0; white = 0;
    while stack:
        x, y = stack.pop()
        if visited[x][y]: continue
        visited[x][y] = True
        if grid[x][y] == '#': black += 1
        else: white += 1
        for dx, dy in direction:
            temp_x, temp_y = min(max(x + dx, 0), H-1), min(max(y + dy, 0), W-1)
            if visited[temp_x][temp_y]: continue
            if grid[x][y] != grid[temp_x][temp_y]: stack.append((temp_x, temp_y))
    ans += black * white
print(ans)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    H, W = MI()
    S =[":"*(W+2)]  + [":"+ST()+":" for _ in range(H)] + [":"*(W+2)]

    checked = set()
    d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    ans = 0
    for h in range(1, H + 1):
        for w in range(1, W + 1):
            if (h, w) in checked:
                continue
            queue = [(h,w)]
            black = 0
            white = 0
            while queue:
                from_h, from_w = queue.pop()
                if (from_h,from_w) in checked:
                    continue
                checked.add((from_h,from_w))
                if S[from_h][from_w] == "#":
                    black += 1
                else:
                    white += 1
                for dh, dw in d:
                    if S[from_h + dh][from_w + dw] != ":" and (from_h + dh, from_w + dw) not in checked and S[from_h + dh][from_w + dw] != S[from_h][from_w]:
                        queue.append((from_h + dh, from_w + dw))
            ans += black * white
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def inpl(): return list(map(int, input().split()))

class UnionFind():
    def __init__(self, N):
        self.par = [-1]*(N)
        self.size = [1]*(N)

    def find(self, x):
        if self.par[x] == -1:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            if self.size[px] < self.size[py]:
                px, py = py, px
            self.size[px] += self.size[py]
            self.par[py] = px

H, W = inpl()
S = [[-1]*W for _ in range(H)]
for h in range(H):
    s = input()
    for w in range(W):
        S[h][w] = int(s[w] == "#")

UF = UnionFind(H*W)

for h in range(H):
    for w in range(W-1):
        if S[h][w] != S[h][w+1]:
            UF.unite(h*W+w, h*W+w+1)
for h in range(H-1):
    for w in range(W):
        if S[h][w] != S[h+1][w]:
            UF.unite(h*W+w, h*W+w+W)

ans = 0
for i in range(H*W):
    if UF.par[i] == -1:
        s = UF.size[i]
        ans += s*(s-1)//2

BC = [0]*(H*W)
WC = [0]*(H*W)

for h in range(H):
    for w in range(W):
        if S[h][w] == 1:
            BC[UF.find(h*W+w)] += 1
        else:
            WC[UF.find(h*W+w)] += 1
print(sum([BC[i]*WC[i] for i in range(H*W)]))

Submission status: Accepted

Solution code:
import collections

h,w=map(int,input().split())
color=[[0]*w for _ in range(h)]
for i in range(h):
  s=input()
  for j in range(w):
    if s[j]=='#':
      color[i][j]=1
used=[[0]*400 for _ in range(400)]
ans=0
bc=0
wc=0
for i in range(0,h):
  for j in range(0,w):
    if used[i][j]==1:
      continue
    bc=0
    wc=0
    q=collections.deque()
    used[i][j]=1
    q.append([i,j])
    while 1:
      if len(q)==0:
        break
      else:
        ti,tj=q.popleft()
        if color[ti][tj]==1:
          bc+=1
        else:
          wc+=1
        if ti-1>=0:
          if color[ti][tj]!=color[ti-1][tj]:
            if used[ti-1][tj]==0:
              used[ti-1][tj]=1
              q.append([ti-1,tj])
        if ti+1<=h-1:
          if color[ti][tj]!=color[ti+1][tj]:
            if used[ti+1][tj]==0:
              used[ti+1][tj]=1
              q.append([ti+1,tj])
        if tj-1>=0:
          if color[ti][tj]!=color[ti][tj-1]:
            if used[ti][tj-1]==0:
              used[ti][tj-1]=1
              q.append([ti,tj-1])
        if tj+1<=w-1:
          if color[ti][tj]!=color[ti][tj+1]:
            if used[ti][tj+1]==0:
              used[ti][tj+1]=1
              q.append([ti,tj+1])
    ans+=bc*wc
print(ans)

Submission status: Accepted

Solution code:
class UF():
  def __init__(self, N):
    self._parent=[n for n in range(0, N)]
    self._size=[1] * N

  def find_root(self, x):
    if self._parent[x]==x:return x
    self._parent[x]=self.find_root(self._parent[x])
    return self._parent[x]

  def unite(self, x, y):
    gx=self.find_root(x)
    gy=self.find_root(y)
    if gx==gy:return

    if self._size[gx]<self._size[gy]:
      self._parent[gx]=gy
      self._size[gy]+=self._size[gx]
    else:
      self._parent[gy]=gx
      self._size[gx]+=self._size[gy]

  def size(self, x):
    return self._size[self.find_root(x)]

  def samegroup(self, x, y):
    return self.find_root(x)==self.find_root(y)

  def groupnum(self):
    N=len(self._parent)
    ans=0
    for i in range(N):
      if self.find_root(i)==i:
        ans+=1
    return ans

h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
UF=UF(h*w)
for i in range(h):
  for j in range(w):
    if i!=0:
      if s[i][j]!=s[i-1][j]:UF.unite(i*w+j,(i-1)*w+j)
    if i!=h-1:
      if s[i][j]!=s[i+1][j]:UF.unite(i*w+j,(i+1)*w+j)
    if j!=0:
      if s[i][j]!=s[i][j-1]:UF.unite(i*w+j,i*w+(j-1))
    if j!=w-1:
      if s[i][j]!=s[i][j+1]:UF.unite(i*w+j,i*w+(j+1))
listB=[0 for i in range(h*w)]
listW=[0 for i in range(h*w)]
for i in range(h):
  for j in range(w):
    if s[i][j]=='#':
      listB[UF.find_root(i*w+j)]+=1
    else:
      listW[UF.find_root(i*w+j)]+=1
ct=0
for i in range(h*w):
  ct+=listB[i]*listW[i]
print(ct)

Submission status: Accepted

Solution code:
class UF():
  def __init__(self, N):
    self._parent=[n for n in range(0, N)]
    self._size=[1] * N

  def find_root(self, x):
    if self._parent[x]==x:return x
    self._parent[x]=self.find_root(self._parent[x])
    return self._parent[x]

  def unite(self, x, y):
    gx=self.find_root(x)
    gy=self.find_root(y)
    if gx==gy:return

    if self._size[gx]<self._size[gy]:
      self._parent[gx]=gy
      self._size[gy]+=self._size[gx]
    else:
      self._parent[gy]=gx
      self._size[gx]+=self._size[gy]

  def size(self, x):
    return self._size[self.find_root(x)]

  def samegroup(self, x, y):
    return self.find_root(x)==self.find_root(y)

  def groupnum(self):
    N=len(self._parent)
    ans=0
    for i in range(N):
      if self.find_root(i)==i:
        ans+=1
    return ans

from collections import defaultdict
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
UF=UF(h*w)
for i in range(h):
  for j in range(w):
    if i!=0:
      if s[i][j]!=s[i-1][j]:UF.unite(i*w+j,(i-1)*w+j)
    if i!=h-1:
      if s[i][j]!=s[i+1][j]:UF.unite(i*w+j,(i+1)*w+j)
    if j!=0:
      if s[i][j]!=s[i][j-1]:UF.unite(i*w+j,i*w+(j-1))
    if j!=w-1:
      if s[i][j]!=s[i][j+1]:UF.unite(i*w+j,i*w+(j+1))
listB=[0 for i in range(h*w)]
listW=[0 for i in range(h*w)]
for i in range(h):
  for j in range(w):
    if s[i][j]=='#':
      listB[UF.find_root(i*w+j)]+=1
    else:
      listW[UF.find_root(i*w+j)]+=1
ct=0
for i in range(h*w):
  ct+=listB[i]*listW[i]
print(ct)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
P=[]
for i in range(h):
  C=[str(_) for _ in input()]
  P+=C
par=[[-1,0,0] for _ in range(h*w)]
def find(x):
  if par[x][0]<0:
    return x
  else:
    par[x][0]=find(par[x][0])
    return par[x][0]
def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return False
  else:
    if par[x][0]>par[y][0]:
      x,y=y,x
    par[x][0]+=par[y][0]
    par[y][0]=x
    return True
def same(x,y):
  return find(x)==find(y)
def size(x):
  return -par[find(x)][0]
for i in range(h*w):
  if P[i]=="#":
    par[i][1]+=1
    if (i+1)%w!=0 and P[i+1]==".":
      unite(i,i+1)
    if (i+w)<(h*w) and P[i+w]==".":
      unite(i,i+w)
  else:
    par[i][2]+=1
    if (i+1)%w!=0 and P[i+1]=="#":
      unite(i,i+1)
    if (i+w)<(h*w) and P[i+w]=="#":
      unite(i,i+w)
ans=0
for p,x,y in par:
  if p>=0:
    par[find(p)][1]+=x
    par[find(p)][2]+=y
for p,x,y in par:
  if p<-1:
    ans+=x*y
print(ans)

Submission status: Accepted

Solution code:
h,w = map(int, input().split())
m = [input() for _ in range(h)]
seen = [[0]*w for _ in range(h)]
dxy =[(1,0),(0,1),(-1,0),(0,-1)]
cnt = 0
for i in range(h):
  for j in range(w):
    if not seen[i][j]:
      bcnt,wcnt = 0,0
      q = [(i,j)]
      while q:
        y,x = q.pop()
        if seen[y][x]:
          continue
        if m[y][x] == "#":
          bcnt += 1
        else:
          wcnt += 1
        seen[y][x] = 1
        for dx,dy in dxy:
          if 0<=x+dx<w and 0<=y+dy<h and not seen[y+dy][x+dx] and m[y+dy][x+dx] != m[y][x]:
            q.append((y+dy,x+dx))
      cnt += bcnt*wcnt
print(cnt)

Submission status: Accepted

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]



H,W=map(int,input().split())
tree=UnionFind(H*W)
s=[input() for i in range(H)]

for i in range(H):
    for j in range(W):
        x=i*W+j+1
        if i>0 and s[i][j]!=s[i-1][j]: tree.Unite(x,x-W)
        if i<H-1 and s[i][j]!=s[i+1][j]: tree.Unite(x,x+W)
        if j>0 and s[i][j]!=s[i][j-1]: tree.Unite(x,x-1)
        if j<W-1 and s[i][j]!=s[i][j+1]: tree.Unite(x,x+1)

dicw={}


for i in range(H):
    for j in range(W):
        p=tree.Find_Root(i*W+j+1)
        if not p in dicw:
            dicw[p]=0
        if s[i][j]==".":
            dicw[p]+=1

ans=0
for i in dicw:
    n=tree.Count(i)

    ans+=dicw[i]*(n-dicw[i])
print(ans)

Submission status: Accepted

Solution code:
import sys
# import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
# from itertools import permutations, combinations, product, accumulate, groupby
# from bisect import bisect_left, bisect_right, insort_left, insort_right
# from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]


if __name__ == '__main__':
    h, w = wi()
    s = hs(h)
    flagli = [[0] * w for i in range(h)]
    stack = deque()
    black = 0
    white = 0
    for i in range(h):
        for j in range(w):
            if flagli[i][j] == 0:
                flagli[i][j] = 1
                white = 1 if s[i][j] == "." else 0
                black = 1 if s[i][j] == "#" else 0
                stack.append([i, j])
                while stack != deque():
                    p, q = stack.pop()
                    k = 0 if s[p][q] == "." else 1
                    for dx, dy in dd:
                        nx = q + dx;
                        ny = p + dy
                        if 0 <= nx < w and 0 <= ny < h:
                            if flagli[ny][nx] == 0:
                                if k == 0 and s[ny][nx] == "#":
                                    flagli[ny][nx] = 1
                                    stack.append([ny, nx])
                                    black += 1
                                elif k == 1 and s[ny][nx] == ".":
                                    flagli[ny][nx] = 1
                                    stack.append([ny, nx])
                                    white += 1
                ans += black * white
                black = 0
                white = 0
    print(ans)

Submission status: Accepted

Solution code:
import sys
# import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
# from itertools import permutations, combinations, product, accumulate, groupby
# from bisect import bisect_left, bisect_right, insort_left, insort_right
# from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]


#if __name__ == '__main__':
h, w = wi()
s = hs(h)
flagli = [[0] * w for i in range(h)]
stack = deque()
black = 0
white = 0
for i in range(h):
    for j in range(w):
        if flagli[i][j] == 0:
            flagli[i][j] = 1
            white = 1 if s[i][j] == "." else 0
            black = 1 if s[i][j] == "#" else 0
            stack.append([i, j])
            while stack != deque():
                p, q = stack.pop()
                k = 0 if s[p][q] == "." else 1
                for dx, dy in dd:
                    nx = q + dx;
                    ny = p + dy
                    if 0 <= nx < w and 0 <= ny < h:
                        if flagli[ny][nx] == 0:
                            if k == 0 and s[ny][nx] == "#":
                                flagli[ny][nx] = 1
                                stack.append([ny, nx])
                                black += 1
                            elif k == 1 and s[ny][nx] == ".":
                                flagli[ny][nx] = 1
                                stack.append([ny, nx])
                                white += 1
            ans += black * white
            black = 0
            white = 0
print(ans)

Submission status: Accepted

Solution code:
import sys
# import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
# from itertools import permutations, combinations, product, accumulate, groupby
# from bisect import bisect_left, bisect_right, insort_left, insort_right
# from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]


if __name__ == '__main__':
    h, w = wi()
    s = hs(h)
    flagli = [[0] * w for i in range(h)]
    stack = deque()
    black = 0
    white = 0
    for i in range(h):
        for j in range(w):
            if flagli[i][j] == 0:
                flagli[i][j] = 1
                white = 1 if s[i][j] == "." else 0
                black = 1 if s[i][j] == "#" else 0
                stack.append([i, j])
                while stack != deque():
                    p, q = stack.pop()
                    k = 0 if s[p][q] == "." else 1
                    for dx, dy in dd:
                        nx = q + dx;
                        ny = p + dy
                        if 0 <= nx < w and 0 <= ny < h:
                            if flagli[ny][nx] == 0:
                                if k == 0 and s[ny][nx] == "#":
                                    flagli[ny][nx] = 1
                                    stack.append([ny, nx])
                                    black += 1
                                elif k == 1 and s[ny][nx] == ".":
                                    flagli[ny][nx] = 1
                                    stack.append([ny, nx])
                                    white += 1
                ans += black * white
                black = 0
                white = 0
print(ans)

Submission status: Accepted

Solution code:
from itertools import*
import math
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

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

dirc = [(0,1),(1,0),(0,-1),(-1,0)]
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 dirc:
            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

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

Submission status: Accepted

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


def dfs(startx: int, starty: int) -> set:
    dxdy = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    stack = [(startx, starty, s[starty][startx] == '#')]
    reached = set()
    reached.add((startx, starty))
    b, w = 0, 0
    while stack:
        d = stack.pop()
        if d[2]:
            b += 1
        else:
            w += 1
        for a in dxdy:
            x = d[0] + a[0]
            y = d[1] + a[1]
            if (x, y) not in reached and 0 <= x < W and 0 <= y < H and d[2] ^ (s[y][x] == '#'):
                stack.append((x, y, s[y][x] == '#'))
                reached.add((x, y))
    return (reached, b, w)


reach = set()
ans = 0
for i in range(H):
    for j in range(W):
        if (j, i) not in reach:
            res = dfs(j, i)
            reach |= res[0]
            ans += res[1] * res[2]
print(ans)

Submission status: Accepted

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

checked = set([])
lis = [(1,0),(0,1),(-1,0),(0,-1)]

def bfs(i,j):
    fifo = deque([])
    fifo.append((i,j))
    checked.add((i,j))
    cntBlack = 0
    cntWhite = 0
    while fifo:
        i,j = fifo.popleft()
        if inl[i][j] == '.':
            cntWhite += 1
        else:
            cntBlack += 1

        for di,dj in lis:
            if i+di >= 0 and i+di < H and j+dj >= 0 and j+dj < W and \
                not (i+di, j+dj) in checked \
                and inl[i][j] != inl[i+di][j+dj]:

                checked.add((i+di, j+dj))
                fifo.append((i+di, j+dj))
    return cntBlack*cntWhite

res = 0
for i in range(H):
    for j in range(W):
        if not (i,j) in checked:
            res += bfs(i,j)
print(res)

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
p=['-'*(w+2)]
for i in range(h):
    p.append('-'+input()+'-')
p.append('-'*(w+2))

isl=[]
v=[[0 for i in range(w+2)] for j in range(h+2)]
d=[[0,1],[1,0],[-1,0],[0,-1]]

def bfs(x,y):
    if v[x][y]!=0:
        return
    q=deque()
    q.append((x,y))
    v[x][y]=1
    br,wh=0,0
    cnt=0
    while len(q)>0:
        ch,cw=q.popleft()
        #v[ch][cw]=1
        if p[ch][cw]=='#':
            br+=1
            for dh,dw in d:
                if p[ch+dh][cw+dw]=='.' and v[ch+dh][cw+dw]==0:
                    q.append((ch+dh,cw+dw))
                    v[ch+dh][cw+dw]=1
        elif p[ch][cw]=='.':
            wh+=1
            for dh,dw in d:
                if p[ch+dh][cw+dw]=='#' and v[ch+dh][cw+dw]==0:
                    q.append((ch+dh,cw+dw))
                    v[ch+dh][cw+dw]=1
        #print('xy=',x,y,'chw=',ch,cw,'bw=',br,wh,q)
    isl.append((br,wh))

for i in range(1,h+1):
    for j in range(1,w+1):
        bfs(i,j)

ans=0
for br,wh in isl:
    ans+=br*wh

print(ans)