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:
# coding:utf-8

import sys
from collections import Counter, defaultdict

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

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


# UnionFind
class UnionFind:
    # 負: ルートで値は木の深さを表す
    # 正: 子で値は次のノードを表す
    def __init__(self, size: int) -> None:
        self.nodes = [-1] * size  # 初期状態では全てのノードがルート

    def get_root(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            self.nodes[x] = self.get_root(self.nodes[x])
            return self.nodes[x]

    def unite(self, x: int, y: int) -> None:
        root_x, root_y = self.get_root(x), self.get_root(y)
        if root_x != root_y:
            if self.nodes[root_x] != self.nodes[root_y]:  # グラフの高さが異なる場合
                # 木のランクが高い方のルートに併合させる
                # 併合後にランクの変動はない
                if self.nodes[root_x] < self.nodes[root_y]:
                    self.nodes[root_y] = root_x
                else:
                    self.nodes[root_x] = root_y
            else:
                # ランクが等しい木同士を併合させるので
                # 併合後は木のランクが1つ上がる
                self.nodes[root_x] += -1
                self.nodes[root_y] = root_x


H, W = LI()
B = [[1 if s == '#' else 0 for s in S()] for _ in range(H)]

uf = UnionFind(H * W)

for h in range(H):
    for w in range(W):
        if w < W - 1 and B[h][w] != B[h][w + 1]:
            uf.unite(h * W + w, h * W + w + 1)
        if h < H - 1 and B[h][w] != B[h + 1][w]:
            uf.unite(h * W + w, (h + 1) * W + w)

black = defaultdict(int)
white = defaultdict(int)
for i, n in enumerate(uf.nodes):
    if n < 0:
        n = i
    h, w = divmod(i, W)
    if B[h][w] == 1:
        black[n] += 1
    else:
        white[n] += 1

ans = 0
for n in black.keys():
    ans += black[n] * white[n]

print(ans)

Submission status: Wrong Answer

Solution code:
def getminLT(i):
  if LT[i] == i:
    return i
  else:
    return getminLT(LT[i])

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

D = []
for i in range(H):
  D.append(input())

M = [[0] * W for i in range(H)]
LT = [0]
for i in range(H):
  for j in range(W):
    if i == 0 and j == 0:
      continue
    flag = False
    if i != 0:
      if D[i][j] != D[i-1][j]:
        M[i][j] = M[i-1][j]
        flag = True
    if j != 0:
      if D[i][j] != D[i][j-1]:
        M[i][j] = M[i][j-1]
        if flag == True:
          LT[max(M[i-1][j], M[i][j-1])] = LT[min(M[i][j-1], M[i-1][j])]
        flag = True
    if flag == False:
        M[i][j] = len(LT)
        LT.append(len(LT))
for i in range(len(LT)):
  LT[i] = getminLT(LT[i])
  
L = [[] for i in range(len(LT))]
for i in range(H):
  for j in range(W):
  	L[LT[M[i][j]]].append((i, j))
#print(M)
#print(LT)
#print(L)
cnt = 0
for i in L:
  E = 0
  A = 0
  for j in i:
    if (j[0] + j[1]) % 2 == 0:
      E += 1
    else:
      A += 1
  cnt += E * A
print(cnt)

Submission status: Wrong Answer

Solution code:
def getminLT(i):
  if LT[i] == i:
    return i
  else:
    return getminLT(LT[i])

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

D = []
for i in range(H):
  D.append(input())

M = [[0] * W for i in range(H)]
LT = [0]
for i in range(H):
  for j in range(W):
    if i == 0 and j == 0:
      continue
    flag = False
    if i != 0:
      if D[i][j] != D[i-1][j]:
        M[i][j] = M[i-1][j]
        flag = True
    if j != 0:
      if D[i][j] != D[i][j-1]:
        M[i][j] = M[i][j-1]
        if flag == True:
          LT[max(LT[M[i-1][j]], LT[M[i][j-1]])] = LT[min(LT[M[i][j-1]], LT[M[i-1][j]])]
        flag = True
    if flag == False:
        M[i][j] = len(LT)
        LT.append(len(LT))
for i in range(len(LT)):
  LT[i] = getminLT(LT[i])
  
L = [[] for i in range(len(LT))]
for i in range(H):
  for j in range(W):
  	L[LT[M[i][j]]].append((i, j))
#print(M)
#print(LT)
#print(L)
cnt = 0
for i in L:
  E = 0
  A = 0
  for j in i:
    if (j[0] + j[1]) % 2 == 0:
      E += 1
    else:
      A += 1
  cnt += E * A
print(cnt)

Submission status: Wrong Answer

Solution code:
def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

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

D = []
for i in range(H):
  D.append(input())

M = [[0] * W for i in range(H)]
LT = [0]
for i in range(H):
  for j in range(W):
    if i == 0 and j == 0:
      continue
    flag = False
    if i != 0:
      if D[i][j] != D[i-1][j]:
        M[i][j] = M[i-1][j]
        flag = True
    if j != 0:
      if D[i][j] != D[i][j-1]:
        M[i][j] = M[i][j-1]
        if flag == True:
          if LT[M[i-1][j]] > LT[M[i][j-1]]:
            LT[M[i-1][j]] = LT[M[i][j-1]]
          else:
            LT[M[i][j-1]] = LT[M[i-1][j]]
        flag = True
    if flag == False:
        M[i][j] = len(LT)
        LT.append(len(LT))
for i in range(len(LT)):
  LT[i] = LT[LT[i]]

L = [[] for i in range(len(LT))]
for i in range(H):
  for j in range(W):
  	L[LT[M[i][j]]].append((i, j))
#print(M)
#print(LT)
#print(L)
cnt = 0
for i in L:
  E = 0
  A = 0
  for j in i:
    if (j[0] + j[1]) % 2 == 0:
      E += 1
    else:
      A += 1
  cnt += E * A
print(cnt)

Submission status: Wrong Answer

Solution code:
def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

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

D = []
for i in range(H):
  D.append(input())

M = [[0] * W for i in range(H)]
LT = [0]
for i in range(H):
  for j in range(W):
    if i == 0 and j == 0:
      continue
    flag = False
    if i != 0:
      if D[i][j] != D[i-1][j]:
        M[i][j] = M[i-1][j]
        flag = True
    if j != 0:
      if D[i][j] != D[i][j-1]:
        M[i][j] = M[i][j-1]
        if flag == True:
          LT[max(LT[M[i-1][j]], LT[M[i][j-1]])] = LT[min(LT[M[i][j-1]], LT[M[i-1][j]])]
        flag = True
    if flag == False:
        M[i][j] = len(LT)
        LT.append(len(LT))
for i in range(len(LT)):
  LT[i] = LT[LT[i]]

L = [[] for i in range(len(LT))]
for i in range(H):
  for j in range(W):
  	L[LT[M[i][j]]].append((i, j))
#print(M)
#print(LT)
#print(L)
cnt = 0
for i in L:
  E = 0
  A = 0
  for j in i:
    if (j[0] + j[1]) % 2 == 0:
      E += 1
    else:
      A += 1
  cnt += E * A
print(cnt)

Submission status: Wrong Answer

Solution code:
import queue
import copy

def solve(h, w, m, mm):
    t = copy.deepcopy(mm)
    d0 = [1,0,-1,0]
    d1 = [0,-1,0,1]
    comp=0
    c=0
    for i in range(1,h+1):
        for j in range(1,w+1):
            if (m[i][j]=='#' and t[i][j]=='#'):
                comp+=1
                wh=0
                q = queue.Queue()
                bl = 1
                q.put([i,j])
                while not q.empty():
                    cur = q.get()
                    for d in range(4):
                        nci, ncj = cur[0]+d0[d], cur[1]+d1[d]
                        if t[nci][ncj] == '#':
                            t[nci][ncj] = comp
                            if m[nci][ncj] == '#':
                                bl+=1
                            else:
                                wh+=1
                            q.put([nci,ncj])
                c += bl*wh
    return c

h, w = map(int,input().split())
m = [['*' for i in range(w+2)]]
for i in range(h):
    s = input()
    l = ['*']
    for j in range(w):
        l.append(s[j])
    l.append('*')
    m.append(l)
m.append(['*' for i in range(w+2)])
e = copy.deepcopy(m)
for i in range(1,h+1):
    for j in range(1,w+1):
        if (i+j)%2==0:
            if m[i][j]=='.':
                e[i][j]='*'
        else:
            if m[i][j]=='#':
                e[i][j]='*'
            else:
                e[i][j]='#'
o = copy.deepcopy(m)
for i in range(1,h+1):
    for j in range(1,w+1):
        if (i+j)%2==1:
            if m[i][j]=='.':
                o[i][j]='*'
        else:
            if m[i][j]=='#':
                o[i][j]='*'
            else:
                o[i][j]='#'
print(solve(h,w,m,o)//2+solve(h,w,m,e))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

def dfs(i,j,color): # i,jの色がcolorと同じなら0, colorと異なるなら連結成分でまだカウントされていない要素を数えてその白黒の数を返す
    if not(0<=i<h and 0<=j<w): return 0,0 # i,jが意味をなさないとき
    if s[i][j]==color: return 0,0 # i,jの色がcolorと同じとき
    if t[i][j]: return 0,0 # すでにカウントしたi,jであったとき
    
    t[i][j]=True
    #c = s[i][j]
    wh, bl=0,0
    if s[i][j]=='#':
        bl+=1
    else:
        wh+=1
    
        
    tmp1, tmp2 = dfs(i-1,j,s[i][j])
    bl,wh = bl+tmp1, wh+tmp2

    tmp1, tmp2 = dfs(i+1,j,s[i][j])
    bl,wh = bl+tmp1, wh+tmp2

    tmp1, tmp2 = dfs(i,j-1,s[i][j])
    bl,wh = bl+tmp1, wh+tmp1

    tmp1, tmp2 = dfs(i,j+1,s[i][j])
    bl,wh = bl+tmp1, wh+tmp2

    return bl,wh

ans = 0
for i in range(h):
    for j in range(w):
        a,b = dfs(i,j,'!')
        ans += a*b
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

def dfs(i,j,color): # i,jの色がcolorと同じなら0, colorと異なるなら連結成分でまだカウントされていない要素を数えてその白黒の数を返す
    if not(0<=i<h and 0<=j<w): return 0,0 # i,jが意味をなさないとき
    if s[i][j]==color: return 0,0 # i,jの色がcolorと同じとき
    if t[i][j]: return 0,0 # すでにカウントしたi,jであったとき
    
    t[i][j]=True
    c = s[i][j]
    wh, bl=0,0
    if c=='#':
        bl+=1
    else:
        wh+=1
    
        
    tmp1, tmp2 = dfs(i-1,j,c)
    bl,wh = bl+tmp1, wh+tmp2

    tmp1, tmp2 = dfs(i+1,j,c)
    bl,wh = bl+tmp1, wh+tmp2

    tmp1, tmp2 = dfs(i,j-1,c)
    bl,wh = bl+tmp1, wh+tmp1

    tmp1, tmp2 = dfs(i,j+1,c)
    bl,wh = bl+tmp1, wh+tmp2

    return bl,wh

ans = 0
for i in range(h):
    for j in range(w):
        a,b = dfs(i,j,'!')
        ans += a*b
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

def dfs(i,j,color): # i,jの色がcolorと同じなら0, colorと異なるなら連結成分でまだカウントされていない要素を数えてその白黒の数を返す
    if not(0<=i<h and 0<=j<w): return 0,0 # i,jが意味をなさないとき
    if s[i][j]==color: return 0,0 # i,jの色がcolorと同じとき
    if t[i][j]: return 0,0 # すでにカウントしたi,jであったとき
    
    t[i][j]=True
    c = s[i][j]
    if c=='#':
        bl,wh = 1,0
    else:
        bl,wh = 0,1
    
        
    tmp1, tmp2 = dfs(i-1,j,c)
    bl,wh = bl+tmp1, wh+tmp2

    tmp1, tmp2 = dfs(i+1,j,c)
    bl,wh = bl+tmp1, wh+tmp2

    tmp1, tmp2 = dfs(i,j-1,c)
    bl,wh = bl+tmp1, wh+tmp1

    tmp1, tmp2 = dfs(i,j+1,c)
    bl,wh = bl+tmp1, wh+tmp2

    return bl,wh

ans = 0
for i in range(h):
    for j in range(w):
        a,b = dfs(i,j,'!')
        ans += a*b
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(200000)
h, w = map(int, input().split())
MAP = ["_" * (w + 1)] + ['_' + input() + '_' for _ in range(h)] + ["_" * (w + 1)]
ans = 0
se = set()
m = {0:'#', 1:'.'}
def f(y, x, u):
    ret = 0
    for ny, nx in ((y - 1, x), (y, x - 1), (y, x + 1), (y + 1, x)):
        t = ny * 1000 + nx
        if MAP[ny][nx] == m[u] and t not in se:
            if u == 1:
                ret += 1
            se.add(t)
            f(ny, nx, 1 - u)
    return ret
for i in range(1, h + 1):
    for j in range(1, w + 1):
        if MAP[i][j] == '#':
            se = set([i * 1000 + j])
            ans += f(i, j, 1)
print(ans)

Submission status: Wrong Answer

Solution code:
def search(search_map, group, current_h, current_w, group_index, prev):
    num = 0
    if not(current_h > -1 and current_w > -1 and current_h < H and current_w < W):
        return num
    if current_h in search_map:
        if current_w in search_map[current_h]:
            return num
    current = s_map[current_h][current_w]
    if current == prev:
        return num
    if current_h not in search_map:
        search_map[current_h] = {}
    search_map[current_h][current_w] = True

    if (current == '.'):
        num += 1
    else:
        group[current_h][current_w] = group_index
    # 上
    num += search(search_map, group, current_h+1, current_w, group_index, s_map[current_h][current_w])
    num += search(search_map, group, current_h-1, current_w, group_index, s_map[current_h][current_w])
    num += search(search_map, group, current_h, current_w+1, group_index, s_map[current_h][current_w])
    num += search(search_map, group, current_h, current_w-1, group_index, s_map[current_h][current_w])
    return num


def is_map_exist(m, h, w):
    if h in m:
        if w in m[h]:
            return True
    return False


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

s_map = {}
group = {}
searched_map = {}


for i in range(H):
    s_map[i] = {}
    group[i] = {}
    w = list(A[i])
    for j in range(W):
        s_map[i][j] = w[j]
        group[i][j] = 0

ans = 0
group_index = 1
group_cnt = {}
group_cnt[0] = 0
for i in range(H):
    for j in range(W):
        if s_map[i][j] == '#':
            if group[i][j] != 0:
                ans += group_cnt[group[i][j]]
            else:
                #cnt = search({}, group, i, j, group_index, "")
                #group_cnt[group_index] = cnt
                group_cnt[group_index] = 1
                group_index += 1
                #ans += cnt
print(ans)

'''
4 5
#####
#...#
#...#
#####
'''

'''
5 5
.....
.....
.###.
.###.
.....
'''

Submission status: Wrong Answer

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

k = [[0 for i in range(w)] for k in range(h)]

m = 2
for a in range(h):
    for b in range(w):
        if (a == 0 and b==0 ):
            k[0][0] = 1

        elif (a == 0 and b>= 1):

            if s[a][b] != s[a][b-1]:
                k[a][b] = k[a][b-1]
            else:
                k[a][b] = m
                m += 1

        elif (1 <= a <= w-1 and b == 0):
            if s[a-1][b] != s[a][b]:
                k[a][b] = k[a-1][b]
            else:
                k[a][b] = m
                m += 1
        else :

            if s[a][b] != s[a-1][b]:
                k[a][b] = k[a-1][b]

                tmp = b
                while(tmp>=0 and s[a][tmp] != s[a][tmp-1]):
                    k[a][tmp-1] =k[a][tmp]
                    tmp = tmp-1

            elif s[a][b] != s[a][b-1]:

                k[a][b] = k[a][b-1]

            else:
                k[a][b] = m
                m += 1

ans = 0
hoge = [[0 for i in range(2)] for i in range(m)]

for a in range(h):
    for b in range(w):
        if s[a][b] == ".":
            hoge[k[a][b]][0] += 1
        else:
            hoge[k[a][b]][1] += 1

for i in range(m):
    ans += hoge[i][0] * hoge[i][1]

print(ans)

Submission status: Wrong Answer

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

k = [[0 for i in range(w)] for k in range(h)]

m = 2
for a in range(h):
    for b in range(w):
        if (a == 0 and b==0 ):
            k[0][0] = 1

        elif (a == 0 and b>= 1):

            if s[a][b] != s[a][b-1]:
                k[a][b] = k[a][b-1]
            else:
                k[a][b] = m
                m += 1

        elif (1 <= a <= w-1 and b == 0):
            if s[a-1][b] != s[a][b]:
                k[a][b] = k[a-1][b]
            else:
                k[a][b] = m
                m += 1
        else :

            if s[a][b] != s[a-1][b]:
                k[a][b] = k[a-1][b]

                tmp = b
                while(tmp>=0 and s[a][tmp] != s[a][tmp-1]):
                    k[a][tmp-1] =k[a][tmp]
                    tmp = tmp-1

            elif s[a][b] != s[a][b-1]:

                k[a][b] = k[a][b-1]

            else:
                k[a][b] = m
                m += 1

for i in range(h):
    print(k[i])

ans = 0
hoge = [[0 for i in range(2)] for i in range(m)]

for a in range(h):
    for b in range(w):
        if s[a][b] == ".":
            hoge[k[a][b]][0] += 1
        else:
            hoge[k[a][b]][1] += 1

for i in range(m):
    ans += hoge[i][0] * hoge[i][1]

print(ans)

Submission status: Wrong Answer

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

k = [[0 for i in range(w)] for k in range(h)]

m = 2
for a in range(h):
    for b in range(w):
        if (a == 0 and b==0 ):
            k[0][0] = 1

        elif (a == 0 and b>= 1):

            if s[a][b] != s[a][b-1]:
                k[a][b] = k[a][b-1]
            else:
                k[a][b] = m
                m += 1

        elif (1 <= a <= w-1 and b == 0):
            if s[a-1][b] != s[a][b]:
                k[a][b] = k[a-1][b]
            else:
                k[a][b] = m
                m += 1
        else :

            if s[a][b] != s[a-1][b]:
                k[a][b] = k[a-1][b]

                tmp = b
                while(tmp>=0):
                    if s[a][tmp] != s[a][tmp-1]:
                        k[a][tmp-1] =k[a][tmp]
                    tmp = tmp-1
                    
            elif s[a][b] != s[a][b-1]:

                k[a][b] = k[a][b-1]

            else:
                k[a][b] = m
                m += 1

for i in range(h):
    print(k[i])

ans = 0
hoge = [[0 for i in range(2)] for i in range(m)]

for a in range(h):
    for b in range(w):
        if s[a][b] == ".":
            hoge[k[a][b]][0] += 1
        else:
            hoge[k[a][b]][1] += 1

for i in range(m):
    ans += hoge[i][0] * hoge[i][1]

print(ans)

Submission status: Wrong Answer

Solution code:
def search(search_map, group, current_h, current_w, group_index):
    if current_h > -1 and current_w > -1 and current_h < H and current_w < W:
        return 0
    num = 0
    if current_h not in search_map:
        search_map[current_h] = {}
    search_map[current_h][current_w] = True
    current = s_map[current_h][current_w]
    if (current == '.'):
        num += 1
    else:
        group[current_h][current_w] = group_index
    # 上
    if current_h > 0:
        next_h = current_h-1
        next_w = current_w
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    # 下
    if current_h < H-1:
        next_h = current_h+1
        next_w = current_w
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    # 左
    if current_w > 0:
        next_h = current_h
        next_w = current_w-1
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    # 右
    if current_w < W-1:
        next_h = current_h
        next_w = current_w+1
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    return num


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

s_map = {}
group = {}
searched_map = {}


for i in range(H):
    s_map[i] = {}
    group[i] = {}
    w = list(A[i])
    for j in range(W):
        s_map[i][j] = w[j]
        group[i][j] = 0

ans = 0
group_index = 1
group_cnt = {}
group_cnt[0] = 0
for i in range(H):
    for j in range(W):
        if s_map[i][j] == '#':
            if group[i][j] != 0:
                ans += group_cnt[group[i][j]]
            else:
                cnt = search({}, group, i, j, group_index)
                group_cnt[group_index] = cnt
                group_index += 1
                ans += cnt
print(ans)

'''
4 5
#####
#...#
#...#
#####
'''

'''
5 5
.....
.....
.###.
.###.
.....
'''

Submission status: Wrong Answer

Solution code:
class Cell:
    def __init__(self, value, i, j):
        self.value = value
        self.i = i
        self.j = j
        self.move_list = []

    def _add_move_list(self, cell):
        self.move_list.append(cell)

    # def __eq__(self, cell):
    #     return self.i == cell.i and self.j == cell.j

H, W = map(int, input().split(" "))

array = [[] for i in range(H)]
# array = []
for i in range(H):
    for j, w in enumerate(list(input())):
        value = 0 if w == "." else 1
        cell = Cell(value, i, j)

        # 左
        if j != 0 and value != array[i][-1].value:
            cell._add_move_list(array[i][-1])

        # 下
        if i != 0 and value != array[i - 1][j].value:
            cell._add_move_list(array[i - 1][j])

        array[i].append(cell)
        # array.append(cell)

vector = []
[vector.extend(a) for a in array]

for i in range(H):
    for j in range(W):
        # 右
        if j != W-1 and array[i][j].value != array[i][j + 1].value:
            array[i][j]._add_move_list(array[i][j + 1])

        # 下
        if i != H-1 and array[i][j].value != array[i + 1][j].value:
            array[i][j]._add_move_list(array[i + 1][j])

points = []
for i, cell in enumerate(vector):
    already_list = [cell]
    now_list = cell.move_list
    next_list = []
    count = 0
    while True:
        count = count + 1

        if len(now_list) == 0:
            break

        already_list.extend(now_list)

        [points.append((cell, c)) for c in now_list if cell.value != c.value]

        [next_list.extend(c.move_list) for c in now_list]
        now_list = [c for c in next_list if c not in already_list]

remove_list = []
for i, point in enumerate(points[::-1]):
    if point[0] in [p[1] for p in points] and point[1] in [p[0] for p in points]:
        del points[points.index(point)]

# remove_list.reverse()
# for i in remove_list:
#     del points[i]

print(len(points))

Submission status: Wrong Answer

Solution code:
def search(search_map, group, current_h, current_w, group_index):
    num = 0
    if current_h not in search_map:
        search_map[current_h] = {}
    search_map[current_h][current_w] = True
    current = s_map[current_h][current_w]
    if (current == '.'):
        num += 1
    else:
        group[current_h][current_w] = group_index
    '''
    # 上
    if current_h > 0:
        next_h = current_h-1
        next_w = current_w
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    '''
    # 下
    if current_h < H-1:
        next_h = current_h+1
        next_w = current_w
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    # 左
    if current_w > 0:
        next_h = current_h
        next_w = current_w-1
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    # 右
    if current_w < W-1:
        next_h = current_h
        next_w = current_w+1
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    return num


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

s_map = {}
group = {}
searched_map = {}


for i in range(H):
    s_map[i] = {}
    group[i] = {}
    w = list(A[i])
    for j in range(W):
        s_map[i][j] = w[j]
        group[i][j] = 0

ans = 0
group_index = 1
group_cnt = {}
group_cnt[0] = 0
for i in range(H):
    for j in range(W):
        if s_map[i][j] == '#':
            if group[i][j] != 0:
                ans += group_cnt[group[i][j]]
            else:
                cnt = search({}, group, i, j, group_index)
                group_cnt[group_index] = cnt
                group_index += 1
                ans += cnt
print(ans)

'''
4 5
#####
#...#
#...#
#####
'''

'''
5 5
.....
.....
.###.
.###.
.....
'''

Submission status: Wrong Answer

Solution code:
def search(search_map, group, current_h, current_w, group_index):
    num = 0
    if current_h not in search_map:
        search_map[current_h] = {}
    search_map[current_h][current_w] = True
    current = s_map[current_h][current_w]
    if (current == '.'):
        num += 1
    '''
    else:
        group[current_h][current_w] = group_index
    # 上
    if current_h > 0:
        next_h = current_h-1
        next_w = current_w
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    # 下
    if current_h < H-1:
        next_h = current_h+1
        next_w = current_w
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    # 左
    if current_w > 0:
        next_h = current_h
        next_w = current_w-1
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    # 右
    if current_w < W-1:
        next_h = current_h
        next_w = current_w+1
        isExist = False
        if next_h in search_map:
            if next_w in search_map[next_h]:
                isExist = True
        if s_map[next_h][next_w] != current and not(isExist):
            num += search(search_map, group, next_h, next_w, group_index)
    '''
    return num


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

s_map = {}
group = {}
searched_map = {}


for i in range(H):
    s_map[i] = {}
    group[i] = {}
    w = list(A[i])
    for j in range(W):
        s_map[i][j] = w[j]
        group[i][j] = 0

ans = 0
group_index = 1
group_cnt = {}
group_cnt[0] = 0
for i in range(H):
    for j in range(W):
        if s_map[i][j] == '#':
            if group[i][j] != 0:
                ans += group_cnt[group[i][j]]
            else:
                cnt = search({}, group, i, j, group_index)
                group_cnt[group_index] = cnt
                group_index += 1
                ans += cnt
print(ans)

'''
4 5
#####
#...#
#...#
#####
'''

'''
5 5
.....
.....
.###.
.###.
.....
'''

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(200000)


def input():
    return sys.stdin.readline()[:-1]


def ii(t: type = int):
    return t(input())


def il(t: type = int):
    return list(map(t, input().split()))


def imi(N: int, t: type = int):
    return [ii(t) for _ in range(N)]


def iml(N: int, t: type = int):
    return [il(t) for _ in range(N)]


H, W = il()
S = imi(H, str)
sharp_pos = []
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            sharp_pos.append((i, j))
c = 0
k = 0
pre_cx, pre_cy = 0, 0

board = S[:]
C = 0


def saiki(pos_list, ignore=None):
    global C
    for cx, cy in pos_list:
        p_list = []
        if ignore is None:
            ignore = []
        wanna_char = "." if board[cx][cy] == "#" else "#"
        for d in ((-1, 0), (0, -1), (1, 0), (0, 1)):
            tx = cx + d[1]
            ty = cy + d[0]
            if (
                tx >= 0
                and ty >= 0
                and tx < H
                and ty < W
                and (tx, ty) not in ignore
                and board[tx][ty] == wanna_char
            ):
                ignore.append((cx, cy))
                p_list.append((tx, ty))
                C += 1
        saiki(p_list, ignore)


saiki(sharp_pos)
print(C)

Submission status: Wrong Answer

Solution code:
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [ii for ii in range(n)]
        self.rank = [0 for _ in range(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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

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


def to_one(first, second):
    return first * W + second


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


u = UnionFind(H*W)

for i in range(H):
    for j in range(W):
        if i != H - 1:
            if S[i][j] != S[i + 1][j]:
                u.union(to_one(i, j), to_one(i + 1, j))
        if j != W - 1:
            if S[i][j] != S[i][j + 1]:
                u.union(to_one(i, j), to_one(i, j + 1))


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

for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            count_bw[u.par[to_one(i,j)]][0] += 1
        else:
            count_bw[u.par[to_one(i,j)]][1] += 1

ans = 0

for i in range(H*W):
        ans += count_bw[i][0] * count_bw[i][1]

print(ans)