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:
import collections

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


ans = 0

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            continue
        dp = [[0] * W for j in range(H)]
        dp[i][j] = 1

        q = collections.deque()
        q.append((i, j, '#'))

        while q:
            ci, cj, cm = q.popleft()
            for di, dj in ([0, 1], [1, 0], [0, -1], [-1, 0]):
                if 0 <= ci + di <= H - 1 and 0 <= cj + dj <= W - 1:
                    if S[ci + di][cj + dj] != cm:
                        if dp[ci + di][cj + dj] == 0:
                            q.append((ci + di, cj + dj, S[ci + di][cj + dj]))
                        dp[ci + di][cj + dj] += dp[ci][cj]

        for a in range(H):
            for b in range(W):
                if S[a][b] == ".":
                    ans += dp[a][b]

print(ans // 2)

Submission status: Wrong Answer

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

cntblack, cntwhite = 0, 0
visited = [[False] * W for _ in range(H)]

def count(h, w):
    global cntblack, cntwhite
    if visited[h][w]: return
    visited[h][w] = True
    if S[h][w] == ".": cntwhite += 1
    else: cntblack += 1
    for ny, nx in ((1,0),(0,1),(-1,0),(-1,0)):
        ny += h
        nx += w
        if not (0 <= ny < H and 0 <= nx < W): continue
        if S[ny][nx] == S[h][w]: continue
        count(ny, nx)


ans = 0
for h in range(H):
    for w in range(W):
        cntblack, cntwhite = 0, 0
        count(h, w)
        ans += cntblack * cntwhite

print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import deque

h,w=nii()
s=[list(input()) for i in range(h)]

def BFS(sy,sx,ans):
  que=deque()
  que.append((sy,sx))

  b_cnt=1
  w_cnt=0

  while que:
    y,x=que.popleft()
    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 s[y][x]=='#' and s[ny][nx]=='.':
          w_cnt+=1
          que.append((ny,nx))
        if s[y][x]=='.' and s[ny][nx]=='#':
          b_cnt+=1
          que.append((ny,nx))
    if s[y][x]=='#':
      s[y][x]='D'

  ans+=b_cnt*w_cnt
  return ans

ans=0
for i in range(h):
  for j in range(w):
    if s[i][j]=='#':
      ans=BFS(i,j,ans)

print(ans//2)

Submission status: Wrong Answer

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

def dfs(x,y):
    visited = [[0]*W]*H
    ans = 0
    stack = [(x,y)]
    dx = [0,1]
    dy = [1,0]
    while stack:
        x,y = stack.pop()
        for i in range(2):
            if grid[x][y] == "#":
                flg_a = 0
                flg_b = 1
            else:
                flg_a = 1
                flg_b = 0
            nx = x+dx[i]
            ny = y+dy[i]
            if nx <= H-1 and ny <= W-1:
                if flg_a == 0 and visited[nx][ny]==0:
                    if grid[nx][ny] == ".":
                        stack.append((nx,ny))
                        visited[nx][ny] =1
                        if flg_a != flg_b:
                            ans +=1
                        flg_a =1
                if flg_a == 1 and visited[nx][ny] == 0:
                    if grid[nx][ny] == "#":
                        stack.append((nx,ny))
                        visited[nx][ny] =1
                        if flg_a != flg_b:
                            ans += 1
                        flg_a =0
    return ans

answer = 0
for i in range(H):
    for j in range(W):
        answer += dfs(i,j)
print(answer)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
        
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

#初期化
# uf = UnionFind(n)
h,w = inpl()
s = [input() for _ in range(h)]
d = [(1,0),(-1,0),(0,1),(0,-1)]
neg = [set() for _ in range(h*w)]
uf = UnionFind(h*w)
def ind(i,j): return i*w+j
for y in range(h):
    for x in range(w):
        for dy,dx in d:
            ny = y+dy
            nx = x+dx
            if 0 <= ny < h and 0 <= nx < w and s[ny][nx] != s[y][x]:
                uf.union(ind(y,x), ind(ny,nx))
res = 0
cnt = [[0,0] for _ in range(h*w)]
for i,xx in enumerate(uf.parents):
    y,x = divmod(i,w)
    se = 0 if s[y][x] == '.' else 1
    ind = i if xx < 0 else xx
    cnt[ind][se] += 1
for x,y in cnt:
    res += x*y
print(res)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
        
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

#初期化
# uf = UnionFind(n)
h,w = inpl()
s = [input() for _ in range(h)]
d = [(1,0),(-1,0),(0,1),(0,-1)]
dd = [(1,-1),(-1,1),(1,1),(-1,-1)]
neg = [set() for _ in range(h*w)]
uf = UnionFind(h*w)
def ind(i,j): return i*w+j
for y in range(h):
    for x in range(w):
        if s[y][x] == '.': continue
        for dy,dx in d:
            ny = y+dy
            nx = x+dx
            if 0 <= ny < h and 0 <= nx < w and s[ny][nx] == '.':
                neg[ind(y,x)].add(ind(ny,nx))
        for dy,dx in dd:
            ny = y+dy
            nx = x+dx
            if 0 <= ny < h and 0 <= nx < w and s[ny][nx] == '#':
                if s[y+dy][x] == s[y][x+dx] == '.':
                    uf.union(ind(y,x), ind(ny,nx))
res = 0
for li in uf.all_group_members().values():
    se = set()
    for va in li:
        y,x = divmod(va,w)
        if s[y][x] == '.': break
        for vv in list(neg[va]):
            se.add(vv)
    res += len(list(se)) * uf.size(li[0])
print(res)

Submission status: Wrong Answer

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def size(self, x):
        return self.parents[ self.find(x) ] * -1

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

    def union(self,x,y):
        x_root = self.find(x)
        y_root = self.find(y)
        if(x_root == y_root):
            return

        if( self.parents[x_root] <= self.parents[y_root] ):
            self.parents[x_root] += self.parents[y_root]
            self.parents[y_root] = x_root
        else:
            self.parents[y_root] += self.parents[x_root]
            self.parents[x_root] = y_root

    def members(self,x):
        root = self.find(x)
        ret = [ i for i in range(self.n) if self.find(i) == root ]
        return ret

    def roots(self):
        ret = [ i for i in range(self.n) if self.parents[i] < 0]
        return ret

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

h,w = map(int,readline().split())
s = read().split()
color = [[0] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if(s[i][j] =='#'):
            color[i][j] = 1

uf = UnionFind(h*w)
for i in range(h):
    for j in range(w):
        if(j != w-1):
            if(color[i][j] != color[i][j+1]):
                uf.union(i*w+j,i*w+j+1)
        if(i != h-1):
            if(color[i][j] != color[i+1][j]):
                uf.union(i*w+j,(i+1)*w+j)

ans = 0
for gr in uf.all_group_members().values():
    even = 0
    odd = 0
    for i in gr:
        if(i%2==0):
            even += 1
        else:
            odd += 1
    ans += even*odd

print(ans)

Submission status: Wrong Answer

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def size(self, x):
        return self.parents[ self.find(x) ] * -1

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

    def union(self,x,y):
        x_root = self.find(x)
        y_root = self.find(y)
        if(x_root == y_root):
            return

        if( self.parents[x_root] <= self.parents[y_root] ):
            self.parents[x_root] += self.parents[y_root]
            self.parents[y_root] = x_root
        else:
            self.parents[y_root] += self.parents[x_root]
            self.parents[x_root] = y_root

    def members(self,x):
        root = self.find(x)
        ret = [ i for i in range(self.n) if self.find(i) == root ]
        return ret

    def roots(self):
        ret = [ i for i in range(self.n) if self.parents[i] < 0]
        return ret

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

h,w = map(int,readline().split())
s = read().split()

uf = UnionFind(h*w)
for i in range(h):
    for j in range(w):
        if(j != w-1):
            if(s[i][j] != s[i][j+1]):
                uf.union(i*w+j,i*w+j+1)
        if(i != h-1):
            if(s[i][j] != s[i+1][j]):
                uf.union(i*w+j,(i+1)*w+j)

ans = 0
for gr in uf.all_group_members().values():
    even = 0
    odd = 0
    for i in gr:
        if(i%2==0):
            even += 1
        else:
            odd += 1
    ans += even*odd

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
####
for i in range(h+2):
    for j in range(w+2):
        root((i,j))
pb = {}
pw = {}
##pb,pwの引数はroot とる
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[root(k)]+=1
            else:
                pb[root(k)]=1
        elif s[i+1][j+1]==".":
            if k in pw:
                pw[root(k)]+=1
            else:
                pw[root(k)]=1
ans = 0
c2 =  set([p[i][j] for j in range(w+2) for i in range(h+2)])

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:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

#https://note.nkmk.me/python-union-find/

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

h,w=MI()
uf=UnionFind(h*w)
lis=[[0]*w for i in range(h)]
for i in range(h):
    s=SI()
    for j in range(w):
        if s[j]=="#":
            lis[i][j]=1
step=[[0,1],[0,-1],[-1,0],[1,0]]
for i in range(h):
    for j in range(w):
        for x,y in step:
            if not (0<=i+x<h and 0<=j+y<w):
                continue
            if lis[i][j]!=lis[i+x][j+y]:
                uf.union(w*i+j,w*(i+x)+(j+y))
ans=0
print(ans)
'''for z in uf.roots():
    s=0
    b=0
    for node in uf.members(z):
        if lis[node//w][node%w]==1:
            b+=1
        else:
            s+=1
    ans+=b*s
print(ans)'''

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


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

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

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

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return
        if self.parent[root_x] > self.parent[root_y]:
            root_x, root_y = root_y, root_x
        self.parent[root_x] += self.parent[root_y]
        self.parent[root_y] = root_x

    def get_size(self, x):
        return -self.parent[self.find(x)]

    def get_root(self):
        return [i for i, root in enumerate(self.parent) if root < 0]

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.node) if self.find(i) == root]

    def all_group_members(self):
        return {r: self.members(r) for r in self.get_root()}


def main():
    h, w = map(int, input().split())
    grid = [["*" for _ in range(w + 2)]]
    for _ in range(h):
        grid.append(["*"] + list(input()) + ["*"])
    grid.append(grid[0])
    uf = UnionFind(h * w)
    all_black = []

    def grid_num(i, j):
        return w * (i - 1) + j - 1

    for i in range(1, h + 1):
        for j in range(1, w + 1):
            for di, dj in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
                ni = i + di
                nj = j + dj
                if grid[ni][nj] == "*":
                    continue
                elif grid[i][j] != grid[ni][nj]:
                    uf.union(grid_num(i, j), grid_num(ni, nj))
            if grid[i][j] == "#":
                all_black.append([i, j])
    ans = 0

    black = defaultdict(int)
    for i, j in all_black:
        now = grid_num(i, j)
        root = uf.parent[now]
        if root < 0:
            root = now
        black[root] += 1
    for i, r in enumerate(uf.parent):
        if r < 0:
            ans += black[i] * (-r - black[i])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


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

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

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

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return
        if self.parent[root_x] > self.parent[root_y]:
            root_x, root_y = root_y, root_x
        self.parent[root_x] += self.parent[root_y]
        self.parent[root_y] = root_x

    def get_size(self, x):
        return -self.parent[self.find(x)]

    def get_root(self):
        return [i for i, root in enumerate(self.parent) if root < 0]

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.node) if self.find(i) == root]

    def all_group_members(self):
        return {r: self.members(r) for r in self.get_root()}


def main():
    h, w = map(int, input().split())
    grid = [["*" for _ in range(w + 2)]]
    for _ in range(h):
        grid.append(["*"] + list(input()) + ["*"])
    grid.append(grid[0])
    uf = UnionFind(h * w)
    all_black = []

    def grid_num(i, j):
        return w * (i - 1) + j - 1

    for i in range(1, h + 1):
        for j in range(1, w + 1):
            for di, dj in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
                ni = i + di
                nj = j + dj
                if grid[ni][nj] == "*":
                    continue
                elif grid[i][j] != grid[ni][nj]:
                    uf.union(grid_num(i, j), grid_num(ni, nj))
            if grid[i][j] == "#":
                all_black.append([i, j])
    ans = 0

    black = defaultdict(int)
    for i, j in all_black:
        now = grid_num(i, j)
        black[uf.parent[now]] += 1
    for i, r in enumerate(uf.parent):
        if r < 0:
            ans += black[i] * (-r - black[i])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


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

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

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

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return
        if self.parent[root_x] > self.parent[root_y]:
            root_x, root_y = root_y, root_x
        self.parent[root_x] += self.parent[root_y]
        self.parent[root_y] = root_x

    def get_size(self, x):
        return -self.parent[self.find(x)]

    def get_root(self):
        return [i for i, root in enumerate(self.parent) if root < 0]

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.node) if self.find(i) == root]

    def all_group_members(self):
        return {r: self.members(r) for r in self.get_root()}


def main():
    h, w = map(int, input().split())
    grid = [["*" for _ in range(w + 2)]]
    for _ in range(h):
        grid.append(["*"] + list(input()) + ["*"])
    grid.append(grid[0])
    uf = UnionFind(h * w)
    all_black = []

    def grid_num(i, j):
        return w * (i - 1) + j - 1

    for i in range(1, h + 1):
        for j in range(1, w + 1):
            for di, dj in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
                ni = i + di
                nj = j + dj
                if grid[ni][nj] == "*":
                    continue
                elif grid[i][j] != grid[ni][nj]:
                    uf.union(grid_num(i, j), grid_num(ni, nj))
            if grid[i][j] == "#":
                all_black.append([i, j])
    ans = 0
    member = uf.all_group_members()
    black = defaultdict(int)
    for i, j in all_black:
        now = grid_num(i, j)
        black[uf.parent[now]] += 1
    for r in member.keys():
        ans += black[r] * (len(member[r]) - black[r])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

maze=[list(input()) for _ in range(h)]

group=[[0]*w for _ in range(h)]

group_no=0
color_cnt=[]

for y in range(h):
    for x in range(w):
        if group[y][x]==0:
            stack=[(y,x)]
            group_no+=1

            color_cnt_tmp=[0,0]

            while len(stack)>0:
                tmp=stack.pop()
                group[tmp[0]][tmp[1]]=group_no
                print(tmp)
                if maze[tmp[0]][tmp[1]]=="#":
                    color_cnt_tmp[0]+=1
                else:
                    color_cnt_tmp[1]+=1

                for (ny,nx) in [(0,1),(1,0),(-1,0),(0,-1)]:
                    my=ny+tmp[0]
                    mx=nx+tmp[1]
                    if 0<=my<h and 0<=mx<w:
                        if group[my][mx]==0:
                            if maze[tmp[0]][tmp[1]]!=maze[my][mx]:
                                stack.append((my,mx))
                                group[my][mx]=group_no
            color_cnt.append(color_cnt_tmp)

ans=0
for (b,w) in color_cnt:
    ans+=b*w

print(ans)

Submission status: Wrong Answer

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

#g = [[] for _ in range(h*w)]

n = h*w

def Find(x, par):
    if par[x] < 0:
        return x
    else:
        par[x] = Find(par[x], par)
        return par[x]

def Unite(x, y, par, rank):
    x = Find(x, par)
    y = Find(y, par)

    if x != y:
        if rank[x] < rank[y]:
            par[y] += par[x]
            par[x] = y
        else:
            par[x] += par[y]
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

def Same(x, y, par):
    return Find(x, par) == Find(y, par)

def Size(x, par):
    return -par[Find(x, par)]

par = [-1]* n
rank = [0]*n

for y in range(h):
    for x in range(w):
        idx1 = y*w+x
        for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
            ny, nx = y+dy, x+dx
            if 0 <= ny < h and 0 <= nx < w:
                idx2 = ny*w+nx
                if S[y][x] != S[ny][nx]:
                    Unite(idx1, idx2, par, rank)

ans = 0
#print(par)
X = [[0, 0] for _ in range(n)]
K = []

for y in range(h):
    for x in range(w):
        i = y*w+x
        if par[i] < 0:
            K.append(i)
            if S[y][x] == '#':
                X[i][0] += 1
            else:
                X[i][1] += 1
        else:
            if S[y][x] == '#':
                X[par[i]][0] += 1
            else:
                X[par[i]][1] += 1

ans = 0
for k in K:
    ans += X[k][0]*X[k][1]
print(ans)

Submission status: Wrong Answer

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

#g = [[] for _ in range(h*w)]

n = h*w

def Find(x, par):
    if par[x] < 0:
        return x
    else:
        par[x] = Find(par[x], par)
        return par[x]

def Unite(x, y, par, rank):
    x = Find(x, par)
    y = Find(y, par)

    if x != y:
        if rank[x] < rank[y]:
            par[y] += par[x]
            par[x] = y
        else:
            par[x] += par[y]
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

def Same(x, y, par):
    return Find(x, par) == Find(y, par)

def Size(x, par):
    return -par[Find(x, par)]

par = [-1]* n
rank = [0]*n

for y in range(h):
    for x in range(w):
        idx1 = y*w+x
        for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
            ny, nx = y+dy, x+dx
            if 0 <= ny < h and 0 <= nx < w:
                idx2 = ny*w+nx
                if S[y][x] != S[ny][nx]:
                    Unite(idx1, idx2, par, rank)

ans = 0
#print(par)
X = [[0, 0] for _ in range(n)]
K = []

for i in range(n):
    y, x = divmod(i, w)
    if par[i] < 0:
        K.append(i)
        if S[y][x] == '#':
            X[i][0] += 1
        else:
            X[i][1] += 1
    else:
        if S[y][x] == '#':
            X[par[i]][0] += 1
        else:
            X[par[i]][1] += 1

ans = 0
for k in K:
    ans += X[k][0]*X[k][1]
print(ans)

Submission status: Wrong Answer

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

#g = [[] for _ in range(h*w)]

n = h*w

def Find(x, par):
    if par[x] < 0:
        return x
    else:
        par[x] = Find(par[x], par)
        return par[x]

def Unite(x, y, par, rank):
    x = Find(x, par)
    y = Find(y, par)

    if x != y:
        if rank[x] < rank[y]:
            par[y] += par[x]
            par[x] = y
        else:
            par[x] += par[y]
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

def Same(x, y, par):
    return Find(x, par) == Find(y, par)

def Size(x, par):
    return -par[Find(x, par)]

par = [-1]* n
rank = [0]*n

for y in range(h):
    for x in range(w):
        idx1 = y*w+x
        for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
            ny, nx = y+dy, x+dx
            if 0 <= ny < h and 0 <= nx < w:
                idx2 = ny*w+nx
                if S[y][x] != S[ny][nx]:
                    Unite(idx1, idx2, par, rank)

ans = 0
#print(par)
X = [[0]*2 for _ in range(n)]
K = []

for i in range(n):
    y, x = divmod(i, w)
    if par[i] < 0:
        K.append(i)
        if S[y][x] == '#':
            X[i][0] += 1
        else:
            X[i][1] += 1
    else:
        if S[y][x] == '#':
            X[par[i]][0] += 1
        else:
            X[par[i]][1] += 1

ans = 0
for k in K:
    ans += X[k][0]*X[k][1]
print(ans)

Submission status: Wrong Answer

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

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0
  for i in range(h):
    for j in range(w):
      if field[i][j]=='#':
        q=collections.deque()
        visited=[[False]*w for _ in range(h)]
        q.append([i,j])
        while q:
          y,x=q.popleft()
          if visited[y][x]:
            continue
          visited[y][x]=True
          for dy,dx in dd:
            ny=y+dy
            nx=x+dx
            if ny<0 or h<=ny or nx<0 or w<=nx:
              continue
            if field[y][x]==field[ny][nx]:
              continue
            if visited[ny][nx]:
              continue
            if field[ny][nx]=='.':
              # ans+=1
              pass
            q.append([ny,nx])
    # print(ans)
  return ans

# main()
print(main())