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: Wrong Answer

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]
dy = [0, 1]

def counter(sx, sy):
    pos = deque([[sx, sy]])
    cnt = 0
    memo = [[-1] * W for i in range(H)]

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

        for i in range(2):
            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] != maze[sy][sx]:
                    cnt += 1
    return cnt

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

Submission status: Wrong Answer

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:
                row, col = d.popleft()
                visited[row][col] = True
                for new_row, new_col in [[row+1, col], [row-1, col], [row, col+1], [row, col-1]]:
                    if 0 <= new_row <= H-1 and 0 <= new_col <= W-1 and s[row][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: Wrong Answer

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:
                row, col = d.popleft()
                for new_row, new_col in [[row+1, col], [row-1, col], [row, col+1], [row, col-1]]:
                    if 0 <= new_row <= H-1 and 0 <= new_col <= W-1 and s[row][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: Wrong Answer

Solution code:
H,W=map(int,input().split())
table=[list(input()) for _ in range(H)]
dp=[[-1 for _ in range(W)] for _ in range(H)]
col=0
wlist=[0]*(H*W)
blist=[0]*(H*W)
for i in range(H):
    for j in range(W):
        if dp[i][j]==-1:
            dp[i][j]=i*W+j
        col=dp[i][j]
        if i!=0:
            if table[i][j]!=table[i-1][j]:
                dp[i-1][j]=col
        if i!=H-1:
            if table[i][j]!=table[i+1][j]:
                dp[i+1][j]=col
        if j!=0:
            if table[i][j]!=table[i][j-1]:
                dp[i][j-1]=col
        if j!=W-1:
            if table[i][j]!=table[i][j+1]:
                dp[i][j+1]=col
        #print(dp)
        #input()
for i in range(H):
    for j in range(W):
        if table[i][j]=="#":
            blist[dp[i][j]]+=1
        else:
            wlist[dp[i][j]] += 1
#print(wlist,blist)
cnt=0
for i in range(H*W):
    cnt=cnt+blist[i]*wlist[i]
print(cnt)

Submission status: Wrong Answer

Solution code:
dy = (-1,0,1,0)
dx = (0,1,0,-1)

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

ans = 0
dist = [[-1] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if dist[i][j] < 0:
            odd = 0
            even = 1
            dist[i][j] = 0
            stack = [(i,j)]
            while stack:
                i,j = stack.pop()
                if grid[i][j] == '#':
                    for k in range(4):
                        y = i + dy[k]
                        x = j + dx[k]
                        if y < 0 or y >= h:
                            continue
                        if x < 0 or x >= w:
                            continue
                        if grid[y][x] == '.' and dist[y][x] < 0:
                            if dist[i][j] == 0:
                                dist[y][x] = 1
                                odd += 1
                            else:
                                dist[y][x] = 0
                                even += 1
                            stack.append((y,x))
                else:
                    for k in range(4):
                        y = i + dy[k]
                        x = j + dx[k]
                        if y < 0 or y >= h:
                            continue
                        if x < 0 or x >= w:
                            continue
                        if grid[y][x] == '#' and dist[y][x] < 0:
                            if dist[i][j] == 0:
                                dist[y][x] = 1
                                odd += 1
                            else:
                                dist[y][x] = 0
                                even += 1
                            stack.append((y,x))
            ans += even * odd
print(ans)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
dp = [[0]*w for _ in range(h)]
s = [input() for _ in range(h)]
for i in range(h):
    for j in range(w):
        if 1<=j and s[i][j]!=s[i][j-1]:
            dp[i][j] += dp[i][j-1] + 1
        if 1<=i and s[i][j]!=s[i-1][j]:
            dp[i][j] += dp[i-1][j] + 1
print(sum(dp[-1]))

Submission status: Wrong Answer

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

# seen = [False] * (H*W+1)
seen = [[False] * W for i in range(H)]
mv = [(0,1),(0,-1),(1,0),(-1,0)]
from collections import deque
from collections import defaultdict
ans  = 0
for i in range(H):
    for j in range(W):
        if seen[i][j]: continue
        # print("i,j",i,j)
        d = defaultdict(int)
        q = deque()
        q.append((i,j))
        d[fields[i][j]] += 1
        while len(q) > 0:
            h,w = q.popleft()
            s = fields[h][w] #そこの文字列
            for dh, dw in mv:
                if 0 <= h + dh < H and 0 <= w + dw < W:
                    if seen[h+dh][w+dw]:continue
                    t = fields[h+dh][w+dw] #隣接セルの文字列
                    if t == s:continue #同じ場合は加算せず
                    # print(s,t,h,w,h+dh,w+dw,"debug")
                    q.append((h+dh,w+dw))
                    seen[h+dh][w+dw] = True
                    d[t] += 1
        ans += d["#"]*d["."]
# print(seen)
print(ans)

Submission status: Wrong Answer

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

# seen = [False] * (H*W+1)
seen = [[False] * W for i in range(H)]
mv = [(0,1),(0,-1),(1,0),(-1,0)]
from collections import deque
from collections import defaultdict
ans  = 0
for i in range(H):
    for j in range(W):
        if seen[i][j]: continue
        # print("i,j",i,j)
        d = defaultdict(int)
        q = deque()
        q.append((i,j))
        while len(q) > 0:
            h,w = q.popleft()
            s = fields[h][w] #そこの文字列
            if not seen[h][w]:
                d[s] += 1
            for dh, dw in mv:
                if 0 <= h + dh < H and 0 <= w + dw < W:
                    if seen[h+dh][w+dw]:continue
                    t = fields[h+dh][w+dw] #隣接セルの文字列
                    if t == s:continue #同じ場合は加算せず
                    # print(s,t,h,w,h+dh,w+dw,"debug")
                    q.append((h+dh,w+dw))
                    seen[h+dh][w+dw] = True
                    d[t] += 1
        ans += d["#"]*d["."]
# print(seen)
print(ans)

Submission status: Wrong Answer

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

# seen = [False] * (H*W+1)
seen = [[False] * W for i in range(H)]
mv = [(0,1),(0,-1),(1,0),(-1,0)]
from collections import deque
from collections import defaultdict
ans  = 0
for i in range(H):
    for j in range(W):
        if seen[i][j]: continue
        # print("i,j",i,j)
        d = defaultdict(int)
        q = deque()
        q.append((i,j))
        while len(q) > 0:
            h,w = q.popleft()
            s = fields[h][w] #そこの文字列
            if not seen[h][w]:
                d[s] += 1
            for dh, dw in mv:
                if 0 <= h + dh < H and 0 <= w + dw < W:
                    if seen[h+dh][w+dw]:continue
                    t = fields[h+dh][w+dw] #隣接セルの文字列
                    if t == s:continue #同じ場合は加算せず
                    # print(s,t,h,w,h+dh,w+dw,"debug")
                    q.append((h+dh,w+dw))
                    seen[h+dh][w+dw] = True
                    d[t] += 1
        d[s] -= 1
        ans += d["#"]*d["."]
# print(seen)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
black = 0
white = 0
#x,y渡すと、（ｈ、ｗ）に入ってるかどうか判定
def check(s,t):
    if (0 <=  s <= h - 1) and (0 <= t <= w - 1):
        return True
    else:
        return False
def bfs(que):
    finished = set()
    while que:
        x , y, color = que.popleft()
        if x+y*w not in finished:
            finished.add(x+y*w)
            for i, j in ((1, 0), (0, 1)):
                if abs(i) + abs(j) < 2 and check(y+j,x+i):
                    if (x+i)+(y+j)*w not in finished:
                        que.append([x+i,y+j,grid[y+j][x+i]])
                    if color != grid[y+j][x+i]:
                        adjacent_list[x+w*y].append((x + i)+w*(y + j))
def dfs(node):
    global white
    global black
    finished.add(node)
    y,x = divmod(node,w)
    if grid[y][x] == '#':
        black += 1
    else:
        white += 1
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i)
from collections import deque
h,w = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
ans = 0
adjacent_list = [[] for i in range(h*w)]
que = deque()
que.append([0,0,grid[0][0]])
bfs(que)
#再び初期化
finished = set()
for i in range(h*w):
    #頂点iからdfsをする。黒と白をカウントしておいて最後にかける
    black = 0
    white = 0
    if i not in finished:
        dfs(i)
        ans += black * white
print(ans)

Submission status: Wrong Answer

Solution code:
def root(x):
    i,j = x[0],x[1]
    if (i,j) == p[i][j]:
        return (i,j)
    y = root(p[i][j])
    p[i][j]=y
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    pxi,pxj= px[0],px[1];pyi,pyj= py[0],py[1];
    rx = rank[pxi][pxj]; ry = rank[pyi][pyj]
    if ry < rx:
        p[pyi][pyj] = px
    elif rx < ry:
        p[pxi][pxj] = py
    else:
        p[pyi][pyj] = px
        rank[pxi][pxj] += 1
    return 1

h,w = map(int, input().split( ))
s = ["x"*(w+2)]+["x"+input()+"x" for _ in range(h)]+["x"*(w+2)]
p = [[(i,j) for j in range(w+2)] for i in range(h+2)]
rank = [[1]*(w+2) for _ in range(h+2)]

tonari = [(-1,0),(1,0),(0,1),(0,-1)]
for i in range(1,h+1):
    for j in range(1,w+1):
        for di,dj in tonari:
            i2 = i+di;j2 = j+dj
            if (s[i][j],s[i2][j2])==("#",".") or (s[i][j],s[i2][j2])==("#",".") :
                unite((i,j),(i2,j2))
c = [[p[i][j] for j in range(1,w+1)] for i in range(1,h+1)]
ans = 0

pb = {}
pw = {}
for i in range(h):
    for j in range(w):
        k = c[i][j]
        if s[i+1][j+1] =="#":
            if k in pb:
                pb[k]+=1
            else:
                pb[k]=1
        elif s[i+1][j+1]==".":
            if k in pw:
                pw[k]+=1
            else:
                pw[k]=1
ans = 0
c2 =  set([p[i][j] for j in range(1,w+1) for i in range(1,h+1)])

for k in c2:
    if k in pb and k in pw:
        ans += pb[k]*pw[k]
print(ans)

Submission status: Wrong Answer

Solution code:
def root(x):
    i,j = x[0],x[1]
    if (i,j) == p[i][j]:
        return (i,j)
    y = root(p[i][j])
    p[i][j]=y
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    pxi,pxj= px[0],px[1];pyi,pyj= py[0],py[1];
    rx = rank[pxi][pxj]; ry = rank[pyi][pyj]
    if ry < rx:
        p[pyi][pyj] = px
    elif rx < ry:
        p[pxi][pxj] = py
    else:
        p[pyi][pyj] = px
        rank[pxi][pxj] += 1
    return 1

h,w = map(int, input().split( ))
s = ["x"*(w+2)]+["x"+input()+"x" for _ in range(h)]+["x"*(w+2)]
p = [[(i,j) for j in range(w+2)] for i in range(h+2)]
rank = [[1]*(w+2) for _ in range(h+2)]

tonari = [(-1,0),(1,0),(0,1),(0,-1)]
for i in range(1,h+1):
    for j in range(1,w+1):
        for di,dj in tonari:
            i2 = i+di;j2 = j+dj
            if (s[i][j],s[i2][j2])==("#",".") or (s[i][j],s[i2][j2])==("#",".") :
                unite((i,j),(i2,j2))
c = [[p[i][j] for j in range(1,w+1)] for i in range(1,h+1)]
from collections import Counter
ans = 0

pb = {}
pw = {}
for i in range(h):
    for j in range(w):
        k = c[i][j]
        ki,kj = k[0],k[1]
        if s[i+1][j+1] =="#":
            if k in pb:
                pb[k]+=1
            else:
                pb[k]=1
        elif s[i+1][j+1]==".":
            if k in pw:
                pw[k]+=1
            else:
                pw[k]=1
ans = 0
c2 =  set([p[i][j] for j in range(1,w+1) for i in range(1,h+1)])

for k in c2:
    try:
        ans += pb[k]*pw[k]
    except:
        pass
print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n)]
    self.size = [1]*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 unit(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    elif self.rank[x]<self.rank[y]:
      self.par[x] = y
      self.size[y] += self.size[x]
      return
    elif self.rank[y]<self.rank[x]:
      self.par[y] = x
      self.size[x] += self.size[y]
    else:
      self.par[y] = x
      self.size[x] += self.size[y]
      self.rank[x] += 1
      
  def same(self, x, y):
    return self.find(x)==self.find(y)
  
  def count(self, x):
    return self.size[x]
H, W, *L = open(0).read().split()
H = int(H)
W = int(W)
ans = 0
u = UnionFind(H*W)
inf = [[0]*2 for i in range(W*H)]
log = [[0]*W for i in range(H)]
for i in range(H):
  for j in range(W):
    if i==H-1:
      if j==W-1:
        continue
      else:
        if L[i][j]!=L[i][j+1]:
          if log[i][j] and log[i][j+1]:
            continue
          u.unit(i*W+j,i*W+j+1)
          p = u.find(i*W+j)
          if log[i][j]==0:
            if L[i][j]=='.':
              inf[p][0] += 1
            else:
              inf[p][1] += 1
            log[i][j] = 1
          if log[i][j+1]==0:
            if L[i][j+1]=='.':
              inf[p][0] += 1
            else:
              inf[p][1] += 1
            log[i][j+1] = 1
    else:
      if j==W-1:
        if L[i][j]!=L[i+1][j]:
          if log[i][j] and log[i+1][j]:
            continue
          u.unit(i*W+j,(i+1)*W+j)
          p = u.find((i+1)*W+j)
          if log[i][j]==0:
            if L[i][j]=='.':
              inf[p][0] += 1
            else:
              inf[p][1] += 1
            log[i][j] = 1
          if log[i+1][j]==0:
            if L[i+1][j]=='.':
              inf[p][0] += 1
            else:
              inf[p][1] += 1
            log[i+1][j] = 1
      else:
        if L[i][j]!=L[i+1][j]:
          if log[i][j] and log[i+1][j]:
            continue
          u.unit(i*W+j,(i+1)*W+j)
          p = u.find((i+1)*W+j)
          if log[i][j]==0:
            if L[i][j]=='.':
              inf[p][0] += 1
            else:
              inf[p][1] += 1
            log[i][j] = 1
          if log[i+1][j]==0:
            if L[i+1][j]=='.':
              inf[p][0] += 1
            else:
              inf[p][1] += 1
            log[i+1][j] = 1
        if L[i][j]!=L[i][j+1]:
          if log[i][j] and log[i][j+1]:
            continue
          u.unit(i*W+j,i*W+j+1)
          p = u.find(i*W+j)
          if log[i][j]==0:
            if L[i][j]=='.':
              inf[p][0] += 1
            else:
              inf[p][1] += 1
            log[i][j] = 1
          if log[i][j+1]==0:
            if L[i][j+1]=='.':
              inf[p][0] += 1
            else:
              inf[p][1] += 1
            log[i][j+1] = 1
for i in range(H*W):
  a,b = inf[i]
  ans += a*b
print(ans)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
grid =[list(input()) for i in range(h)]
cntW =[[0]*w for i in range(h)]
visited=[[False]*w for i in range(h)]
for i in range(h):
  for j in range(w):
    if grid[i][j]=='#':
      if j<w-1 and grid[i][j+1]=='.':cntW[i][j]+=1
      if j>0 and grid[i][j-1]=='.':cntW[i][j]+=1
      if i<h-1 and grid[i+1][j]=='.':cntW[i][j]+=1
      if i>0 and grid[i-1][j]=='.':cntW[i][j]+=1
ans=0
for i in range(h):
  for j in range(w):
    if visited[i][j]:
      continue
    q=[(i,j)]
    ans+=cntW[i][j]
    visited[i][j]=True
    while q:
      cy,cx=q.pop(0)
      for nx,ny in ((cy+1,cx+1),(cy-1,cx-1),(cy-1,cx+1),(cy+1,cx-1)):
        if 0<=nx<w and 0<=ny<h and grid[ny][nx]=='#' and not(visited[ny][nx]):
          ans+=cntW[ny][nx]
          visited[ny][nx]=True
          q.append((ny,nx))
print(ans)

Submission status: Wrong Answer

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

count=0
count2=0
for h1 in range(H):
    for w1 in range(W):
        if S[h1][w1]=="#" and checked[h1][w1]==0:
            checked[h1][w1]=1
            stack=deque([[h1,w1,"#"]])
            kuro=1
            siro=0
            count2+=1
            visited=set([h1*400+w1])
            print(stack)
            while stack:
                h,w,iro=stack.popleft()
                for y,x in [[-1,0],[1,0],[0,1],[0,-1]]:
                    Y,X=y+h,x+w
                    visitednum=Y*400+X
                    if 0<=Y<H and 0<=X<W and not visitednum in visited:
                        if iro=="#" and S[Y][X]==".":
                            siro+=1
                            visited.add(visitednum)
                            stack.append([Y,X,"."])
                        elif iro=="." and S[Y][X]=="#" and not visitednum in visited:
                            kuro+=1
                            checked[Y][X]=1
                            visited.add(visitednum)
                            stack.append([Y,X,"#"])
            count+=kuro*siro
print(count)
print(count2)

Submission status: Wrong Answer

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

h,w = map(int,input().split())

sl = []

for _ in range(h):
    s = list(input())
    sl.append(s)

used = [-1 for i in range(h*w)]
def dfs(i, j):
    used[i] = j
    if i % w + 1 < w:
        if sl[i//w][i%w] != sl[i//w][i%w+1]:
            if used[i+1] == -1:
                dfs(i + 1, j)
    if i // w + 1 < h:
        if sl[i // w][i % w] != sl[i // w+1][i % w]:
            if used[i+w] == -1:
                dfs(i + w, j)

while True:
    if min(used) >= 0:
        break
    for i, j in enumerate(used):
        if j == -1:
            dfs(i, i)

from collections import defaultdict
dic = defaultdict(list)

for i, j in enumerate(used):
    dic[j].append(i)

ans = 0
for group in dic.values():
    a = 0
    b = 0
    for p in group:
        i = p // w
        j = p % w
        if sl[i][j] == "#":
            a += 1
        else:
            b += 1
    ans += a*b
print(ans)

Submission status: Wrong Answer

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

h,w = map(int,input().split())

sl = []

for _ in range(h):
    s = list(input())
    sl.append(s)

used = [-1 for i in range(h*w)]
def dfs(i, j):
    used[i] = j
    if i % w + 1 < w:
        if sl[i//w][i%w] != sl[i//w][i%w+1]:
            dfs(i + 1, j)
    if i // w + 1 < h:
        if sl[i // w][i % w] != sl[i // w+1][i % w]:
            dfs(i + w, j)

while True:
    if min(used) >= 0:
        break
    for i, j in enumerate(used):
        if j == -1:
            dfs(i, i)

from collections import defaultdict
dic = defaultdict(list)

for i, j in enumerate(used):
    dic[j].append(i)

ans = 0
for group in dic.values():
    a = 0
    b = 0
    for p in group:
        i = p // w
        j = p % w
        if sl[i][j] == "#":
            a += 1
        else:
            b += 1
    ans += a*b
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter


class UnionFind:
    def __init__(self, n):
        self.v = [-1 for _ in range(n)]

    def find(self, x):
        if self.v[x] < 0:
            return x
        else:
            self.v[x] = self.find(self.v[x])
            return self.v[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if -self.v[x] < -self.v[y]:
            x, y = y, x
        self.v[x] += self.v[y]
        self.v[y] = x

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

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

    def size(self, x):
        return -self.v[self.find(x)]


def main():
    import sys

    input = sys.stdin.readline

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

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

    uf = UnionFind(h * w * 2)
    for r in range(h):
        for c in range(w):
            id_ = (r * w + c) + (h * w if s[r][c] == '#' else 0)
            for dr, dc in d:
                nr = r + dr
                if nr < 0 or h <= nr:
                    continue
                nc = c + dc
                if nc < 0 or w <= nc:
                    continue
                if s[nr][nc] == s[r][c]:
                    continue
                nid = (nr * w + nc) + (h * w if s[nr][nc] == '#' else 0)
                uf.unite(id_, nid)

    checked = [False] * (h * w * 2)
    ctr_dot = Counter(uf.v[:h * w])
    ctr_sharp = Counter(uf.v[h * w:])

    ret = 0
    for r in range(h):
        for c in range(w):
            id_ = (r * w + c) + (h * w if s[r][c] == '#' else 0)
            root = uf.find(id_)
            if checked[root]:
                continue
            checked[root] = True

            dot = ctr_dot[root]
            sharp = ctr_sharp[root]
            if root < h * w:
                dot += 1
            else:
                sharp += 1
            ret += dot * sharp

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(si,sj):
  if S[sj][si] != '#':return 0
  
  q = deque()
  q.append([si,sj,1])
  ans = 0
  used.add((si,sj))
  ini_col = S[sj][si]
  while len(q)>0:
    prvi, prvj,prvcnt = q.popleft()
    for i,j in [[prvi+1,prvj],[prvi-1,prvj],[prvi,prvj+1],[prvi,prvj-1]]:
      if (i,j) in used:continue
      elif (prvcnt%2==0 and S[j][i] == ini_col) or (prvcnt%2==1 and S[j][i] not in [ini_col,'-']):
          q.append([i,j,prvcnt+1])
          used.add((i,j))
            
          if S[j][i] == '.':
            ans += 1
  return ans    

H,W = map(int,input().split())
S = [['-' for _ in range(W+2)]] + [['-'] + [s for s in input()] + ['-'] for _ in range(H)] + [['-' for _ in range(W+2)]]
ans = 0
used = set([])
for i in range(1,W+1):
  for j in range(1,H+1):
    if (i,j) not in used:
      ans += bfs(i,j)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(si,sj):
  q = deque()
  q.append([si,sj,1])
  ans = 0
  used = set([si,sj,1])
  ini_col = S[sj][si]
  while len(q)>0:
    prvi, prvj,prvcnt = q.popleft()
    for i,j in [[prvi+1,prvj],[prvi,prvj+1]]:
      if (i,j) in used:continue
      elif (prvcnt%2==0 and S[j][i] == ini_col) or (prvcnt%2==1 and S[j][i] not in [ini_col,'-']):
          q.append([i,j,prvcnt+1])
          used.add((i,j))
            
          if (ini_col == '#' and S[j][i] == '.') or  (ini_col == '.' and S[j][i] == '#'):
            ans += 1
  return ans    

H,W = map(int,input().split())
S = [['-' for _ in range(W+2)]] + [['-'] + [s for s in input()] + ['-'] for _ in range(H)] + [['-' for _ in range(W+2)]]
ans = 0
for i in range(1,W+1):
  for j in range(1,H+1):
    ans += bfs(i,j)
print(ans)

Submission status: Wrong Answer

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

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

for i in range(H):
    for j in range(W):
        b,w = 0,0
        if not visited[i][j]:
            stack.append([i,j])
            visited[i][j] = 1
            while stack:
                x,y = stack.pop()
                if S[x][y]=='#':
                    b += 1
                else:
                    w += 1
                if x+1<H and S[x][y]!=S[x+1][y] and not visited[x+1][y]:
                    visited[x+1][y] = 1
                    stack.append([x+1,y])
                if y+1<W and S[x][y]!=S[x][y+1] and not visited[x][y+1]:
                    visited[x][y+1] = 1
                    stack.append([x,y+1])
            ans += b*w
            
print(ans)

Submission status: Wrong Answer

Solution code:
from fractions import gcd
# from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def main():
    
    h, w = map(int, input().split())
    s = [list(input()) for i in range(h)]
    start = []
    d = {}
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#": 
                start.append([i,j])
                d[(i, j)] = -1

    ans = [0]
    vis = [[-1 for i in range(w)] for j in range(h)]
    def f(x, y, pre):
        vis[x][y] = 1
        for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            nx = i + x
            ny = j + y
            if nx >= 0 and ny >= 0 and nx < h and ny < w and vis[nx][ny] == -1:
                if pre == "B" and s[nx][ny] == ".":
                    ans[0] += 1
                    d[(nx,ny)] = 1
                    f(nx,ny,"W")
                elif pre == "W" and s[nx][ny] == "#":
                    f(nx, ny, "B")
                else:
                    return False
    for i, j in start:
        if d[(i, j)] == -1:
            d[(i,j)] = 1
            f(i, j, "B")
        vis = [[-1 for i in range(w)] for j in range(h)]
    print(ans[0])
        

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from fractions import gcd
# from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def main():
    
    h, w = map(int, input().split())
    s = [list(input()) for i in range(h)]
    start = []
    d = {}
    c = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#": 
                start.append([i,j])
                d[(i, j)] = c
                c += 1
    ans = [0]
    vis = [[-1 for i in range(w)] for j in range(h)]
    def f(x, y, pre):
        vis[x][y] = 1
        for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            nx = i + x
            ny = j + y
            if nx >= 0 and ny >= 0 and nx < h and ny < w and vis[nx][ny] == -1:
                if pre == "B" and s[nx][ny] == ".":
                    ans[0] += 1
                    f(nx,ny,"W")
                elif pre == "W" and s[nx][ny] == "#":
                    f(nx, ny, "B")
                else:
                    return False
    for i, j in start:
        f(i, j, "B")
        vis = [[-1 for i in range(w)] for j in range(h)]
    print(ans[0])

if __name__ == '__main__':
    main()