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 search(search_map, group, current_h, current_w, group_index, calc):
    calc[0] += 1
    if current_h in search_map:
        search_map[current_h]
    else:
        search_map[current_h] = {}
        search_map[current_h][current_w] = True
    search_map[current_h][current_w] = True
    current = s_map[current_h][current_w]
    num = 0
    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, calc)
    # 下
    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, calc)
    # 左
    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, calc)
    # 右
    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, calc)
    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
calc = [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]]
                calc[0] += 1
            else:
                #cnt = search({}, group, i, j, group_index, calc)
                #group_cnt[group_index] = cnt
                group_index += 1
                #ans += cnt
print(ans)

'''
1 1
#
'''

'''
1 1
.
'''

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

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


'''
3 1
#
.
#
'''


'''
3 3
###
#.#
###
'''

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

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

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

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

Submission status: Wrong Answer

Solution code:
def search(search_map, group, current_h, current_w, group_index, calc):
    calc[0] += 1
    if current_h in search_map:
        search_map[current_h]
    else:
        search_map[current_h] = {}
        search_map[current_h][current_w] = True
    search_map[current_h][current_w] = True
    current = s_map[current_h][current_w]
    num = 0
    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, calc)
    # 下
    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, calc)
    # 左
    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, calc)
    # 右
    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, calc)
    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 = {}
calc = [0]
for i in range(H):
    for j in range(W):
        if s_map[i][j] == '#':
            if group[i][j] != 0:
                calc[0] += 1
            '''
                ans += group_cnt[group[i][j]]
                # calc[0] += 1
            else:
                cnt = search({}, group, i, j, group_index, calc)
                group_cnt[group_index] = cnt
                group_index += 1
                ans += cnt
            '''
print(ans)

'''
1 1
#
'''

'''
1 1
.
'''

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

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


'''
3 1
#
.
#
'''


'''
3 3
###
#.#
###
'''

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

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

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

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

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
s=[input()for _ in range(h)]
a=[[0]*w for _ in range(h)]
ans=0
p=[]
q=[]
for i in range(h):
    for j in range(w):
        if s[i][j]=='.':continue
        for dx,dy in zip([-1,1,0,0],[0,0,-1,1]):
            if i+dy<0 or i+dy>=h or j+dx<0 or j+dx>=w:continue
            if s[i+dy][j+dx]=='.':
                a[i][j]+=1
        if i+1<h and s[i+1][j]=='.':
            if j-1>=0 and s[i+1][j-1]=='#':
                if s[i][j-1]=='.':
                    p.append([[i,j],[i+1,j-1]])
                else:
                    q.append([[i,j],[i+1,j-1]])
            if j+1<w and s[i+1][j+1]=='#':
                if s[i][j+1]=='.':
                    p.append([[i,j],[i+1,j+1]])
                else:
                    q.append([[i,j],[i+1,j+1]])
        if i+2<h and s[i+1][j]=='.' and a[i+2][j]=='#':
            q.append([[i,j],[i+2,j]])
        if j+2<w and s[i][j+1]=='.' and a[i][j+2]=='#':
            q.append([[i,j],[i,j+2]])
for t in p:
    u,v=t
    uy,ux=u
    vy,vx=v
    tem1=a[uy][ux]-2
    tem2=a[vy][vx]-2
    a[vy][vx]+=tem1
    a[uy][ux]+=tem2
for t in q:
    u,v=t
    uy,ux=u
    vy,vx=v
    tem1=a[uy][ux]-1
    tem2=a[vy][vx]-1
    a[vy][vx]+=tem1
    a[uy][ux]+=tem2
for t in a:
    ans+=sum(t)
print(ans)

Submission status: Wrong Answer

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

#横
a = [[0]*w for i in range(h)]
if w >= 2:
    for i in range(h):
        for j in range(w-2,-1,-1):
            if s[i][j] !=  s[i][j+1]:
                a[i][j] += 1
                if j +2 <w:
                    a[i][j] += a[i][j+2]

#縦
b = [[0]*w for i in range(h)]
if h >= 2:
    for j in range(w):
        for i in range(h-2,-1,-1):
            if s[i][j] !=  s[i+1][j]:
                b[i][j] += 1
                if i +2 <h:
                    b[i][j] += b[i+2][j]
                
dp = [[0]*w for i in range(h)]

def f(x,j):
    pp = 0
    if  x+1 < w and s[x][j] != s[x+1][j]:
        k[r] = 1
        

for i in range(h-1,-1,-1):
    for j in range(w-1,-1,-1):
        c = [0,0,0]
        if i+1 < h and s[i+1][j] != s[i][j]:
            dp[i][j] += 1
            if i+2 <h and s[i+2][j] == s[i][j]:
                c[0] = 1
            if j + 1 <w and s[i+1][j+1] == s[i][j]:
                c[1] = 1
        if j+1 <w and s[i][j+1] != s[i][j+1]:
            dp[i][j] += 1
            if i+1 <h and s[i+1][j+1] == s[i][j]:
                c[1] = 1
            if j+2 < w and s[i][j+2] == s[i][j]:
                c[2] = 1
        
        if c == [1,0,0]:
            dp[i][j] += dp[i+2][j]
        elif c == [0,1,0]:
            dp[i][j] += dp[i+1][j+1]
        elif c == [0,0,1]:
            dp[i][j] += dp[i][j+2]
        elif c ==[1,1,0]:
            dp[i][j] += dp[i+2][j] + b[i+1][j+1]
        elif c ==[0,1,1]:
            dp[i][j] += dp[i][j+2] + a[i+1][j+1]
        elif c ==[1,1,1]:
            dp[i][j] += dp[i+2][j] + b[i+1][j+1]+b[i][j+2]
        
        elif c == [1,0,1]:
            dp[i][j] += dp[i][j+2]+a[i+2][j]
  
            for r in range(i+2,w):
                if  s[i][r] != s[i+1][r] and s[i+1][r] != s[i][j]:
                    dp[i][j]+=1
                    
res = 0
for i in range(h):
    for j in range(w):
        res += dp[i][j]
print(res)

Submission status: Wrong Answer

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



def search(s, h, w, pos, count, s_pos, t_pos):
    t_pos[pos[0]][pos[1]] = 1
    if(s[pos[0]][pos[1]] != s[s_pos[0]][s_pos[1]]):
        count += 1


    flag = False

    if(pos[0] != h-1 and t_pos[pos[0]+1][pos[1]] == 0):
        if(s[pos[0]][pos[1]] != s[pos[0]+1][pos[1]]):
            count = search(s, h, w, [pos[0]+1, pos[1]], count, s_pos, t_pos)
            flag = True

    """
    if(pos[0] != 0 and t_pos[pos[0]-1][pos[1]] == 0):
        if(s[pos[0]][pos[1]] != s[pos[0]-1][pos[1]]):
            count = search(s, h, w, [pos[0]-1, pos[1]], count, s_pos, t_pos)
            flag = True
    """

    if(pos[1] != w-1 and t_pos[pos[0]][pos[1]+1] == 0):
        if(s[pos[0]][pos[1]] != s[pos[0]][pos[1]+1]):
            count = search(s, h, w, [pos[0], pos[1]+1], count, s_pos, t_pos)
            flag = True
    """
    if(pos[1] != 0 and t_pos[pos[0]][pos[1]-1] == 0):
        if(s[pos[0]][pos[1]] != s[pos[0]][pos[1]-1]):
            count = search(s, h, w, [pos[0], pos[1]-1], count, s_pos, t_pos)
            flag = True
    """
    return count


count = 0
flag = 0
for i in range(h):
    for j in range(w):
        flag2 = False
        if(i != h-1):
            if(s[i][j] != s[i+1][j]):
                count += 1 + flag // 2
                flag2 = True
        if(j != w-1):
            if(s[i][j] != s[i][j+1]):
                count += 1 + flag // 2

        if(flag2 == True): flag += 1
        else: flag = 0

print(count)

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]
                if s[a][b] != s[a][b-1]:
                    k[a][b-1] =k[a][b]
                    continue
            elif s[a][b-1] != s[a][b]:
                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 = [[c for c in input()] for _ in range(H)]

"""
tree = [[(i,j) for j in range(W) if S[i][j] == "#"] for i in range(H)]
"""
tree = []
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            child = []
            if 0 < i:
                if S[i-1][j] == ".":
                    c = (i-1,j)
                    child.append(c)
            if i < H-1:
                if S[i+1][j] == ".":
                    c = (i+1,j)
                    child.append(c)
            if 0 < j:
                if S[i][j-1] == ".":
                    c = (i,j-1)
                    child.append(c)
            if j < W-1:
                if S[i][j+1] == ".":
                    c = (i,j+1)
                    child.append(c)
            if len(child) > 0:
                tree.append([(i,j), child])


r = 0
for node in tree:
    z = node[1]
    x = []
    for c in z:
        for d in tree:
            if c in d[1]:
                x += d[1]
    x += z
    r += len(set(x))

print(r)

Submission status: Wrong Answer

Solution code:
from queue import Queue as Qe

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

D = [[-1 for j in range(W)] for i in range(H)]
S = [input() for i in range(H)]

D[0][0] = 1
q = Qe()
q.put((0,0))
White = 1 if S[0][0] == "." else 0
Black = 1 if S[0][0] == "#" else 0
ans = 0

def_h = 0
def_w = 0
while not q.empty():
    h,w = q.get()
    #print(h,w,White,Black)
    if h-1>=0 and S[h][w]!=S[h-1][w] and D[h-1][w] == -1: #up
        if S[h-1][w]=="#":
            ans += White
            Black += 1
        else:
            ans += Black
            White += 1
        D[h-1][w] = 1
        q.put((h-1,w))
    if h+1<H and S[h][w]!=S[h+1][w] and D[h+1][w] == -1: #down
        if S[h+1][w]=="#":
            ans += White
            Black += 1
        else:
            ans += Black
            White += 1
        D[h+1][w] = 1
        q.put((h+1,w))
    if w-1>=0 and S[h][w]!=S[h][w-1] and D[h][w-1] == -1: #left
        if S[h][w-1]=="#":
            ans += White
            Black += 1
        else:
            ans += Black
            White += 1
        D[h][w-1] = 1
        q.put((h,w-1))
    if w+1<W and S[h][w]!=S[h][w+1] and D[h][w+1] == -1: #right
        if S[h][w+1]=="#":
            ans += White
            Black += 1
        else:
            ans += Black
            White += 1
        D[h][w+1] = 1
        q.put((h,w+1))
    if q.empty():
        okei = False
        if def_w == W-1:
            def_w = 0
            def_h += 1
        for i in range(def_h,H):
            for j in range(def_w,W):
                if D[i][j] == -1:
                    D[i][j] = 1
                    q.put((i,j))
                    White = 1 if S[i][j] == "." else 0
                    Black = 1 if S[i][j] == "#" else 0
                    def_h,def_w = i,j
                    okei = True
                    break
            if okei: break
                
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
H,W = list(map(int,input().split()))
Sarr = np.zeros([H,W]).astype(np.int)
for i in range(H):
    Sarr[i,:] = [1 if x=="#" else 0 for x in input()]
Marr = np.zeros([H,W]).astype(np.int)

black_l = np.zeros(H*W).astype(np.int)
white_l = np.zeros(H*W).astype(np.int)
new = 0
for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            Marr[i,j] = new
        elif i == 0:
            if Sarr[i,j-1] == Sarr[i,j]:
                new += 1
                Marr[i,j] = new
            else:
                Marr[i,j] = Marr[i,j-1]
        elif j==0:
            if Sarr[i-1,j] == Sarr[i,j]:
                new += 1
                Marr[i,j] = new
            else:
                Marr[i,j] = Marr[i-1,j]
        else:
            if Sarr[i-1,j] == Sarr[i,j]:
                if Sarr[i,j-1] == Sarr[i,j]:
                    new += 1
                    Marr[i,j] = new
                else:
                    Marr[i,j] = Marr[i,j-1]
            else:
                Marr[i,j] = Marr[i-1,j]
    if i > 0 and W>1:
        if Sarr[i-1,0] == Sarr[i,0] and Sarr[i,0] != Sarr[i,1]:
            Marr[i,0] = Marr[i,1]
for i in range(H):
    for j in range(W):
        if Sarr[i,j] == 1:
            black_l[Marr[i,j]] += 1
        else:
            white_l[Marr[i,j]] += 1

# print(Sarr)
# print(Marr)
# print(black_l)
# print(white_l)

print(black_l.dot(white_l))

Submission status: Wrong Answer

Solution code:

H, W = map(int, input().split())
S = [input() for i in range(H)]
b_list = []
for row in S:
    tmp_raw = []
    for j, t in enumerate(row):
        if t == '#':
            tmp_raw.append(j)
    b_list.append(tmp_raw)
tmp = -1
res = {}
raw_before = []
for i, raw in enumerate(b_list):
    res[i] = {}
    for j in raw:
        res[i][j] = []
        if not((j - 1) in raw or j == 0):
            res[i][j].append((i, j-1))
        if not((j + 1) in raw or j == W -1):
            res[i][j].append((i, j+1))
        if not(i == 0 or j in raw_before):
            res[i][j].append((i-1, j))
        if not(i == H - 1):
            if not(j in b_list[i+1]):
                res[i][j].append((i+1, j))            
    raw_before = raw

connect = {}
for i, raw in enumerate(b_list):
    connect[i] = {}
    for j in raw:
        connect[i][j] = []

coho = []
for i, raw in enumerate(b_list):
    for j in raw:        
        coho.append((i, j))

def check(a, b):
    f = False
    if abs(a[0] - b[0]) == 1:
        if abs(a[1]-b[1]) == 1:
            f = True
    return f

for a in coho:
    for b in coho:
        if check(a, b):
            connect[a[0]][a[1]].append(b)
            connect[b[0]][b[1]].append(a)
for a in coho:
    connect[a[0]][a[1]] = list(set(connect[a[0]][a[1]]))
for a in coho:
    if len(connect[a[0]][a[1]]) > 0:
        for b in connect[a[0]][a[1]]:
            res[a[0]][a[1]] += res[b[0]][b[1]]
result = 0
for a in coho:
    res[a[0]][a[1]] = list(set(res[a[0]][a[1]]))
    result += len(res[a[0]][a[1]])
print(result)

Submission status: Wrong Answer

Solution code:
def search(search_map, group, current_h, current_w, group_index, calc):
    calc[0] += 1
    if current_h in search_map:
        search_map[current_h]
    else:
        search_map[current_h] = {}
        search_map[current_h][current_w] = True
    search_map[current_h][current_w] = True
    current = s_map[current_h][current_w]
    num = 0
    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, calc)
    # 下
    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, calc)
    # 左
    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, calc)
    # 右
    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, calc)
    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 = {}
calc = [0]
for i in range(H):
    for j in range(W):
        if s_map[i][j] == '#':
            calc[0] += 1
            '''
            if group[i][j] != 0:
                ans += group_cnt[group[i][j]]
                # calc[0] += 1
            else:
                cnt = search({}, group, i, j, group_index, calc)
                group_cnt[group_index] = cnt
                group_index += 1
                ans += cnt
            '''
print(ans)

'''
1 1
#
'''

'''
1 1
.
'''

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

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


'''
3 1
#
.
#
'''


'''
3 3
###
#.#
###
'''

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

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

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

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

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
matrix = [[0] * W for i in range(H)]
S = [0] * H
white = []
black = []
for i in range(H):
    s = input()
    S[i] = s
    for index, j in enumerate(s):
        if j == '.':
            white.append([i, index])
            matrix[i][index] = 1
        else:
            black.append([i, index])

def cal(start, goal):
    ans = 0
    check = [[0] * W for i in range(H)]
    check[start[0]][start[1]] = 1

    deque = [[start[0], start[1]]]
    num = 0
    while deque:
        x, y = deque.pop(0)
        for dx, dy in [1, 0], [-1, 0], [0, 1], [0, -1]:
            if 0 <= y+dy <= H-1 and 0 <= x+dx <= W-1:
                tmp = abs(y+dy - goal[0]) + abs(y+dy - goal[1])
                if tmp % 2 == 0 and S[y+dy][x+dx] == '.' or tmp%2 ==1 and S[y+dy][x+dx] == '#':
                    if y + dy == goal[0] and x + dx == goal[1]:
                        ans += 1
                    if check[y+dy][x+dx] == 0:
                        check[y+dy][x+dx] = 1
                        deque.append([y+dy,x+dx])
    return ans

ans = 0
for start in white:
    for goal in black:
        ans += cal(start, goal)
print(ans)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
s=[[0]+list(input())+[0]for i in range(h)]
s.insert(0,[0]*(w+2))
s.append([0]*(w+2))
c=["#","."]
n=0
print(s)
for i in range(1,h+1):
    for j in range(1,w+1):
        g=[0,0]
        if s[i][j]!=0:
            p=c.index(s[i][j])
            g[c.index(s[i][j])]+=1
            k=[[i,j]]
            s[i][j]=0
            while len(k)>0:
                b=[]
                for f in range(len(k)):
                    if s[k[f][0]+1][k[f][1]]==c[(p+1)%2]:
                        b.append([k[f][0]+1,k[f][1]])
                        s[k[f][0]+1][k[f][1]]=0
                    if s[k[f][0]-1][k[f][1]]==c[(p+1)%2]:
                        b.append([k[f][0]-1,k[f][1]])
                        s[k[f][0]-1][k[f][1]]=0
                    if s[k[f][0]][k[f][1]+1]==c[(p+1)%2]:
                        b.append([k[f][0],k[f][1]+1])
                        s[k[f][0]][k[f][1]+1]=0
                    if s[k[f][0]][k[f][1]-1]==c[(p+1)%2]:
                        b.append([k[f][0],k[f][1]-1])
                        s[k[f][0]][k[f][1]-1]=0
                else:
                    k=b
                    g[(p+1)%2]+=len(b)
                    p+=1
            else:
                n+=g[0]*g[1]
else:
    print(n)

Submission status: Wrong Answer

Solution code:
def search(search_map, group, current_h, current_w, group_index, calc):
    calc[0] += 1
    if current_h in search_map:
        search_map[current_h]
    else:
        search_map[current_h] = {}
        search_map[current_h][current_w] = True
    search_map[current_h][current_w] = True
    current = s_map[current_h][current_w]
    num = 0
    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, calc)
    # 下
    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, calc)
    # 左
    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, calc)
    # 右
    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, calc)
    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 = {}
calc = [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]]
                # calc[0] += 1
            else:
                cnt = search({}, group, i, j, group_index, calc)
                group_cnt[group_index] = cnt
                group_index += 1
                ans += cnt
'''
print(ans)

'''
1 1
#
'''

'''
1 1
.
'''

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

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


'''
3 1
#
.
#
'''


'''
3 3
###
#.#
###
'''

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

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

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

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

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]
                if s[a][b] != s[a][b-1]:
                    k[a][b-1] =k[a][b]
            elif s[a][b-1] != s[a][b]:
                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:
from copy import deepcopy
H, W = [int(a) for a in input().split()]
prev_list = list()
prev_map = list()
island_list = list()
prev_sign = ""
for j in range(H):
    s_list = list(input())
    # s_list = list(s_master[j])
    if j > 0:
        for i, s in enumerate(s_list):
            if s == prev_list[i]:
                if i > 0 and s != prev_sign:
                    if s == ".":
                        island_list[prev_map[i - 1]][0] += 1
                    else:
                        island_list[prev_map[i - 1]][1] += 1
                    prev_map[i] = prev_map[i - 1]
                else:
                    if s == ".":
                        island_list.append([1, 0])
                    else:
                        island_list.append([0, 1])
                    prev_map[i] = len(island_list) - 1
            else:
                if i > 0 and s != prev_sign and prev_map[i-1] != prev_map[i]:
                    if s == ".":
                        island_list[prev_map[i - 1]][0] += 1 + island_list[prev_map[i]][0]
                        island_list[prev_map[i - 1]][1] += island_list[prev_map[i]][1]
                    else:
                        island_list[prev_map[i - 1]][0] += island_list[prev_map[i]][0]
                        island_list[prev_map[i - 1]][1] += 1 + island_list[prev_map[i]][1]
                    island_list[prev_map[i]] = [0, 0]
                    prev_map[i] = prev_map[i - 1]
                else:
                    if s == ".":
                        island_list[prev_map[i]][0] += 1
                    else:
                        island_list[prev_map[i]][1] += 1
            prev_sign = s
    else:
        for i, s in enumerate(s_list):
            if i == 0:
                if s == ".":
                    island_list.append([1, 0])
                else:
                    island_list.append([0, 1])
                prev_map.append(0)
            else:
                if s != prev_sign:
                    if s == ".":
                        island_list[-1][0] += 1
                    else:
                        island_list[-1][1] += 1
                    prev_map.append(prev_map[-1])
                else:
                    if s == ".":
                        island_list.append([1, 0])
                    else:
                        island_list.append([0, 1])
                    prev_map.append(prev_map[-1] + 1)
            prev_sign = s
    prev_list = deepcopy(s_list)
print(str(sum([a[0] * a[1] for a in island_list])))