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:
H,W=map(int,input().split())
L=[]
for i in range(H):
    l=list(input())
    L.append(l)
#print(L)

P=[i for i in range(H*W)]
size=[]
for i in range(H):
    for j in range((W)):
        if L[i][j]==".":
            size.append([1,1,0])
        else:
            size.append([1,0,1])
#print(size)


def find(x):
    if x==P[x]:
        return x
    else:
        return find(P[x])
        
def union(y,z):
    fy=find(y)
    fz=find(z)
    if size[fy][0]>=size[fz][0]:
        P[z]=P[y]
        for i in range(3):
            size[fy][i]+=size[fz][i]
    elif size[fz][0]>size[fy][0]:
        P[y]=P[z]
        for i in range(3):
            size[fz][i]+=size[fy][i]
            
X=[1,-1,0,0]
Y=[0,0,1,-1]
            
for i in range(H):
    for j in range(W):
        if i+1<=H-1:
            if L[i][j]!=L[i+1][j]:
                #print([i,j],[i+1,j])
                if P[find(i*W+j)]==P[find((i+1)*W+j)]:
                    pass
                else:
                    union(i*W+j,(i+1)*W+j)
        if i-1>=0:
            if L[i][j]!=L[i-1][j]:
                if P[find(i*W+j)]==P[find((i-1)*W+j)]:
                    pass
                else:
                    union(i*W+j,(i-1)*W+j)
        
        if j+1<=W-1:
            if L[i][j]!=L[i][j+1]:
                if P[find(i*W+j)]==P[find(i*W+(j+1))]:
                    pass
                else:
                    union(i*W+j,i*W+(j+1))
        
        if j-1>=0:
            if L[i][j]!=L[i][j-1]:
                if P[find(i*W+j)]==P[find(i*W+(j-1))]:
                    pass
                else:
                    union(i*W+j,i*W+(j-1))
#print(P)
#print(size)
ans=0
for i in range(H*W):
    if P[i]==i:
        ans+=(size[i][1]*size[i][2])
print(ans)

Submission status: Wrong Answer

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

isVisited = [ [False]*W for _ in range(H) ]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
# (x, y) から行けるペアの数
def dfs( x, y ):
    ans = 0
    isVisited[x][y] = True
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if S[x][y] == '#':
            if 0 <= nx and nx < H and 0 <= ny and ny < W and not isVisited[nx][ny]:
                if S[nx][ny] == '.': ans += dfs( nx, ny )+1
        else:
            if 0 <= nx and nx < H and 0 <= ny and ny < W and not isVisited[nx][ny]:
                if S[nx][ny] == '#': ans += dfs( nx, ny )+1
    return ans


ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#' and not isVisited:
          ans += dfs( i, j )

print( ans )

Submission status: Wrong Answer

Solution code:
a,b=map(int,input().split())
l=["x"*(b+2)]
for i in range(a):
    l.append("x"+input()+"x")
l.append("x"*(b+2))
print(l)
ans=0
for s in range(1,a+1):
    for t in range(1,b+1):
        for(x,y)in [[0,1],[0,-1],[1,0],[-1,0]]:
            if l[s][t]=="." and l[s+x][t+y]=="#":
                ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

h, w = (int(i) for i in input().split())
a = [input() for i in range(h)]

class UnionFind():
    def __init__(self, N):
        self.par = [i for i in range(N)]
        self.size = [1] * N
        self.N = N

    # xのrootを返す
    def root(self, x):
        if self.par[x] == x:
            return x
        else: 
            self.par[x] = self.root(self.par[x])
            return self.root(self.par[x])

    # x, yが同じrootの場合true
    def same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry

    # x,yのrootが違った場合、併合
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if self.size[rx] < self.size[ry]:
            self.par[rx] = ry
            self.size[ry] += self.size[rx]
        else:
            self.par[ry] = rx
            self.size[rx] += self.size[ry]
            
uf = UnionFind(h*w)

for j in range(h):
    for i in range(w):
        if i != w-1 and a[j][i+1] != a[j][i]:
            uf.unite(w*j+i,w*j+i+1)
        if j != h-1 and a[j+1][i] != a[j][i]:
            uf.unite(w*j+i,w*(j+1)+i)

l_idx = sorted(list(set(uf.par)))

wc = [0]*len(l_idx)
bc = [0]*len(l_idx)
for j in range(h):
    for i in range(w):
        idx = l_idx.index(uf.par[w*j+i])
        if a[j][i] == ".":
            wc[idx] += 1
        else:
            bc[idx] += 1

res = 0
for i in range(len(l_idx)):
    res += wc[i] * bc[i]
print(res)

Submission status: Wrong Answer

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

arr = [[0 for i in range(w)] for j in range(h)]
arr[0][0] = 0
cnt = 1

for j in range(h):
    for i in range(w):
        if arr[j][i] == 0:
            arr[j][i] = cnt
            cnt += 1
        
        if i != w-1 and a[j][i+1] != a[j][i]:
            arr[j][i+1] = arr[j][i]
        if j != h-1 and a[j+1][i] != a[j][i]:
            arr[j+1][i] = arr[j][i]

wc = [0]*(cnt)
bc = [0]*(cnt)

for j in range(h):
    for i in range(w):
        if a[j][i] == ".":
            wc[arr[j][i]] += 1
        else:
            bc[arr[j][i]] += 1

res = 0
for i in range(cnt):
    res += wc[i] * bc[i]
print(res)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n = II()
    h = II()
    w = II()
    print((n-h+1)*(n-w+1))
    return

#B
def B():
    n = II()
    a, b = LI()
    p = LI()
    p.sort()
    ans = [0 for i in range(3)]
    for p_ in p:
        if p_ <= a:
            ans[0] += 1
        elif a < p_ <= b:
            ans[1] += 1
        else:
            ans[2] += 1
    print(min(ans))
    return

#C
def C():
    h, w = LI()
    s = SR(h)
    def bfs1(x, y):
        xy_ = [(0, -1), (1, 0), (0, 1), (-1, 0)]
        res = 0
        for xy in xy_:
            if 0 <= xy[0] + x < w and 0 <= xy[1] + y < h:
                if s[xy[1] + y][xy[0] + x] == ".":
                    res += 1
        return res
    field = [[0 for i in range(w)] for k in range(h)]
    for y in range(h):
        for x in range(w):
            if s[y][x] == "#":
                field[y][x] = bfs1(x, y)
    def bfs2(x, y):
        xy_ = [(0, -1), (1, 0), (0, 1), (-1, 0)]
        res = 0
        for xy in xy_:
            if 0 <= xy[0] + x < w and 0 <= xy[1] + y < h:
                if s[xy[1] + y][xy[0] + x] == ".":
                    for x_, y_ in xy_:
                        if 0 <= xy[0] + x + x_ < w and 0 <= xy[1] + y + y_ < h:
                            res += max(0, field[xy[1] + y + y_][xy[0] + x + x_] - 1)
        return res
    ans = 0
    for y in range(h):
        for x in range(w):
            if s[y][x] == "#":
                ans = max(bfs2(x, y), ans)
    print(ans)
    
        
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    C()

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())

L=[]
S=["*" for i in range(W+2)]
L.append(S)
for i in range(H):
    s=input()
    s="*"+s+"*"
    s=list(s)
    L.append(s)
L.append(S)

#print(L)

E=[]
O=[]
for i in range(H+2):
    e=[]
    o=[]
    for j in range(W+2):
        if (i+j)%2==0:
            if L[i][j]==".":
                e.append(L[i][j])
                o.append("*")
            else:
                e.append("*")
                o.append(L[i][j])
        else:
            if L[i][j]==".":
                o.append(L[i][j])
                e.append("*")
            else:
                o.append("*")
                e.append(L[i][j])
    E.append(e)
    O.append(o)
#print(O)

E1=[[0 for i in range(W+2)] for j in range(H+2)]
O1=[[0 for i in range(W+2)] for j in range(H+2)]

ans=0
b=0
w=0

X=[1,-1,0,0]
Y=[0,0,1,-1]

for i in range(1,H+1):
    for j in range(1,W+1):
        if E[i][j]=="." or E[i][j]=="#":
            Q=[[i,j]]
            E1[i][j]=1
            if E[i][j]==".":
                w+=1
            else:
                b+=1
            for a in range(20000):
                #print(Q,b,w)
                if Q==[]:
                    ans+=b*w
                    #print(b,w)
                    b=0
                    w=0
                    #print(ans)
                    break
                else:
                    E1[Q[0][0]][Q[0][1]]=1
                    for c in range(4):
                        
                        if E[Q[0][0]+X[c]][Q[0][1]+Y[c]]=="." or E[Q[0][0]+X[c]][Q[0][1]+Y[c]]=="#":
                            if E1[Q[0][0]+X[c]][Q[0][1]+Y[c]]==0:
                                Q.append([Q[0][0]+X[c],Q[0][1]+Y[c]])
                                E1[Q[0][0]+X[c]][Q[0][1]+Y[c]]=1
                                if E[Q[0][0]+X[c]][Q[0][1]+Y[c]]==".":
                                    w+=1
                                else:
                                    b+=1
                    del Q[0]
                    
for i in range(1,H+1):
    for j in range(1,W+1):
        if O[i][j]=="." or O[i][j]=="#":
            Q=[[i,j]]
            O1[i][j]=1
            if O[i][j]==".":
                w+=1
            else:
                b+=1
            for a in range(20000):
                #print(Q,b,w)
                if Q==[]:
                    ans+=b*w
                    #print(b,w)
                    b=0
                    w=0
                    #print(ans)
                    break
                else:
                    O1[Q[0][0]][Q[0][1]]=1
                    for c in range(4):
                        
                        if O[Q[0][0]+X[c]][Q[0][1]+Y[c]]=="." or O[Q[0][0]+X[c]][Q[0][1]+Y[c]]=="#":
                            if O1[Q[0][0]+X[c]][Q[0][1]+Y[c]]==0:
                                Q.append([Q[0][0]+X[c],Q[0][1]+Y[c]])
                                O1[Q[0][0]+X[c]][Q[0][1]+Y[c]]=1
                                if O[Q[0][0]+X[c]][Q[0][1]+Y[c]]==".":
                                    w+=1
                                else:
                                    b+=1
                    del Q[0]


print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i 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)
 
h,m=map(int, input().split())
s=[list(input()) for i in range(h)]
uf1=UnionFind(h*m)
for i in range(h):
    for j in range(m):
        if s[i][j]!=s[min(i+1,h-1)][j]:uf1.union(i*m+j,i*m+j+m)
        if s[i][j]!=s[i][min(j+1,m-1)]:uf1.union(i*m+j,i*m+j+1)
for i in range(h*m):uf1.find(i)
from collections import Counter
c1=Counter(uf1.par[::2])
c2=Counter(uf1.par[1::2])
ans=0
for i in range(h*m):
    ans+=c1[i]*c2[i]
print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i 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)

h,m=map(int, input().split())
s=[list(input()) for i in range(h)]
uf1=UnionFind(h*m)
for i in range(h):
    for j in range(m):
        if s[i][j]!=s[min(i+1,h-1)][j]:uf1.union(i*m+j,i*m+j+m)
        if s[i][j]!=s[i][min(j+1,m-1)]:uf1.union(i*m+j,i*m+j+1)
from collections import Counter
c1=Counter(uf1.par[::2])
c2=Counter(uf1.par[1::2])
ans=0
for i in range(h*m):
    ans+=c1[i]*c2[i]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

def search_obj(x,y,grids):
    ans = [0,0]
    curr_state = grids[y][x]
    grids[y][x] = '0'    
    obj_state = '.'
    if(curr_state == '.'):
        ans[0] += 1
        obj_state = '#'
    elif(curr_state == '#'):
        ans[1] += 1
    
    if(grids[y-1][x] == obj_state):
        a,b = search_obj(x,y-1,grids)
        ans[0] += a
        ans[1] += b

    if(grids[y][x-1] == obj_state):
        a,b = search_obj(x-1,y,grids)
        ans[0] += a
        ans[1] += b

    if(grids[y+1][x] == obj_state):
        a,b = search_obj(x,y+1,grids)
        ans[0] += a
        ans[1] += b

    if(grids[y][x+1] == obj_state):
        a,b = search_obj(x+1,y,grids)
        ans[0] += a
        ans[1] += b

    return ans
    

H,W = (int(x) for x in input().split())
s = ""
ans = 0
for _ in range(W+2):
    s+="0"
s = list(s)
grids = [s]

for _ in range(H):
    si = input()
    si = "0"+si+"0"
    grids.append(list(si))
    
grids.append(s)

for i in range(W):
    for j in range(H):
        a,b = search_obj(i+1,j+1,grids)
        ans += a*b

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import io

@np.vectorize
def trans(s):
    return 1 if s == "#" else 0

def parse(inp):
    H, W = map(int, next(inp).split())
    return np.array([trans([w for w in next(inp).strip()]) for _ in range(H)])

def find_root(uft, i):
    lst = list()
    while True:
        lst.append(i)
        io = i
        i = uft[i]
        if i == io:
            break
    ri = lst.pop()
    while lst:
        i = lst.pop()
        uft[i] = uft[ri]
    return ri
        

def union_find_tree(inp):
    shape = inp.shape
    H, W = shape
    grp = inp.flatten()
    uft = np.arange(len(grp))
    for i in range(H):
        for j in range(W-1):
            if grp[i*W+j+1] != grp[i*W+j]:
                uft[i*W + j+1] = uft[i*W + j]
    for j in range(W):
        for i in range(H-1):
            if grp[(i+1)*W+j] != grp[i*W+j]:
                uft[find_root(uft, (i+1)*W+j)] = find_root(uft, i*W+j)
    for i in range(len(uft)):
        find_root(uft, i)
    return set(uft), uft


def test(inp):
    roots, uft = union_find_tree(inp)
    nmax = max(roots) + 1
    n1 = np.full(nmax, 0)
    n0 = np.full(nmax, 0)
    for i, u in zip(inp.flatten(), uft):
        if i:
            n1[u] += 1
        else:
            n0[u] += 1
    return np.sum(n1 * n0)
    
import sys
print(test(parse(sys.stdin)))

Submission status: Wrong Answer

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
H,W      = list(map(int, input().split()))
S        =  [ list(input()) for _ in range(H)]

import sys
sys.setrecursionlimit(2600000)

united_count = [ ]
# [ (黒1個、白2個) ,... k 個] 

directions = [(1,0), (0,1), (-1,0), (0,-1)] # y,x の順番


def dfs(pos, c, now_k):
    # pos : (1,2)
    # 引数は現在の連結成分の番号
    # 座標と、現在の1,0 が渡される
    # 渡されたnow_kで塗りつぶす
    y,x = pos
    for d in directions:
        try:
            if y+d[0] < 0 or x+d[1] < 0:
                continue
            content = S[y+d[0]][x+d[1]] 

            if c != content and (content == "#" or content == ".") :
                S[y+d[0]][x+d[1]] = now_k
                inplace_tuple     = united_count[now_k]
                united_count[now_k]     = ( inplace_tuple[0] + 1, inplace_tuple[1]) if content == "#" else \
                                    ( inplace_tuple[0]    , inplace_tuple[1]+1) # タプルなので新しく作る

                dfs( (y+d[0], x+d[1]),  content,  now_k)  # DFSかける

            else:
                continue
        except:
            continue



now_k = 0
for y in range(H):
    for x in range(W):
        c = S[y][x]  
        if c == "#" or c == "." :
            united_count.append( (1,0) if  c == "#" else (0,1) ) # now_k番目
            S[y][x] = now_k  # cの値は黒だったら、1 を入れてdfsに投げる

            pos = (y,x)
            dfs(pos, c, now_k)
            now_k         += 1

        else:
            continue # もう数字が入っている場合は、パス

# for y in range(H):
#     for x in range(W):
#         print(S[y][x], end="")
#     print("")


answer = 0
mod    = int(1e9)+7
for uni in united_count:
    answer = ((uni[0]*uni[1])%mod + answer) % mod

print(answer)

Submission status: Wrong Answer

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
H,W      = list(map(int, input().split()))
S        =  [ list(input()) for _ in range(H)]

import sys
sys.setrecursionlimit(260000)

united_count = [ ]
# [ (黒1個、白2個) ,... k 個] 

directions = [(1,0), (0,1), (-1,0), (0,-1)] # y,x の順番


def dfs(pos, c, now_k):
    # pos : (1,2)
    # 引数は現在の連結成分の番号
    # 座標と、現在の1,0 が渡される
    # 渡されたnow_kで塗りつぶす
    y,x = pos
    for d in directions:
        try:
            if y+d[0] < 0 or x+d[1] < 0:
                continue
            content = S[y+d[0]][x+d[1]] 

            if c != content and (content == "#" or content == ".") :
                S[y+d[0]][x+d[1]] = now_k
                inplace_tuple     = united_count[now_k]
                united_count[now_k]     = ( inplace_tuple[0] + 1, inplace_tuple[1]) if content == "#" else \
                                    ( inplace_tuple[0]    , inplace_tuple[1]+1) # タプルなので新しく作る

                dfs( (y+d[0], x+d[1]),  content,  now_k)  # DFSかける

            else:
                continue
        except:
            continue



now_k = 0
for y in range(H):
    for x in range(W):
        c = S[y][x]  
        if c == "#" or c == "." :
            united_count.append( (1,0) if  c == "#" else (0,1) ) # now_k番目
            S[y][x] = now_k  # cの値は黒だったら、1 を入れてdfsに投げる

            pos = (y,x)
            dfs(pos, c, now_k)
            now_k         += 1

        else:
            continue # もう数字が入っている場合は、パス

# for y in range(H):
#     for x in range(W):
#         print(S[y][x], end="")
#     print("")


answer = 0
mod    = int(1e9)+7
for uni in united_count:
    answer = ((uni[0]*uni[1])%mod + answer) % mod

print(answer)

Submission status: Wrong Answer

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


def dfs(p, q):
    if A[p][q] == 1:
        return 0
    count = 0
    stack = [[p, q]]
    while stack:
        x, y = stack.pop()
        if A[x][y] != 1:
            count += 1
            A[x][y] = 1
            dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]
            for dx, dy in dxy:
                nx, ny = x + dx, y + dy
                if 0 <= nx < H and 0 <= ny < W and S[x][y] != S[nx][ny]:
                    stack += [[nx, ny]]
    return count


print(sum([dfs(i, j) for i, j in itertools.product(range(H), range(W))]))

Submission status: Wrong Answer

Solution code:
import itertools
H, W = [int(_) for _ in input().split()]
S = [input() for _ in range(H)]
A = [[0 for _ in range(W)] for _ in range(H)]
count = {}


def dfs(p, q):
    if A[p][q] == 1:
        return
    count[p * H + q] = {'#': 0, '.': 0}
    stack = [[p, q]]
    while stack:
        x, y = stack.pop()
        if A[x][y] != 1:
            count[p * H + q][S[x][y]] += 1
            A[x][y] = 1
            dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]
            for dx, dy in dxy:
                nx, ny = x + dx, y + dy
                if 0 <= nx < H and 0 <= ny < W and S[x][y] != S[nx][ny]:
                    stack += [[nx, ny]]


for i, j in itertools.product(range(H), range(W)):
    dfs(i, j)
ans = 0
for i in count:
    ans += count[i]['#'] * count[i]['.']
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
H, W = [int(_) for _ in input().split()]
S = [input() for _ in range(H)]
A = [[0 for _ in range(W)] for _ in range(H)]
count = {}


def dfs(p, q):
    if A[p][q] == 1:
        return
    count[p * H + q] = {'#': 0, '.': 0}
    stack = [[p, q]]
    while stack:
        x, y = stack.pop()
        if A[x][y] != 1:
            count[p * H + q][S[x][y]] += 1
            A[x][y] = 1
            dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]
            for dx, dy in dxy:
                nx, ny = x + dx, y + dy
                if 0 <= nx < H and 0 <= ny < W and S[x][y] != S[nx][ny]:
                    stack += [[nx, ny]]


for i, j in itertools.product(range(H), range(W)):
    dfs(i, j)
ans = 0
for i in count:
    ans += count[i].get('#', 0) * count[i].get('.', 0)
print(ans, count)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

def bfs(i, j):
    b, w = 0, 0
    visited[i][j] = True
    que = deque([(i, j)])

    while que:
        ci, cj = que.popleft()
        if S[ci][cj] == '#':
            b += 1
        else:
            w += 1

        for di, dj in move:
            ni, nj = ci + di, cj + dj
            if not (0 <= ni < H and 0 <= nj < W) or visited[ni][nj]:
                continue
            if S[ci][cj] != S[ni][nj]:
                visited[ni][nj] = True
                que.append((ni, nj))

    return b * w


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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)


h, w = map(int, input().split())
s_array = ["+" * (w + 2)]
for i in range(h):
    s_array.append("+" + input() + "+")
else:
    s_array.append("+" * (w + 2))
moving = [[0, 1], [0, -1], [1, 0], [-1, 0]]
visit = [[False for x in range(w+2)] for x in range(h+2)]


def recursive(mark, mark_point, mark_sharp, row, point):
    # 訪問済みならreturn
    if visit[row][point]:
        return mark_point, mark_sharp
    else:
        visit[row][point] = True

    for x, y in moving:
        # 範囲外かどうかと連結かどうか
        if s_array[row + x][point + y] != "+" and s_array[row + x][point + y] != s_array[row][point]:
            if visit[row+x][point+y]:
                continue
            # 移動先のマークの確認
            if s_array[row + x][point + y] == "#":
                mark_sharp += 1
            else:
                mark_point += 1
            mark_point, mark_sharp = recursive(mark, mark_point, mark_sharp, row + x, point + y)
    else:
        return mark_point, mark_sharp


res = 0
for row in range(1, h + 1):
    for point in range(1, w + 1):
        m, n = recursive(s_array[1][1], s_array[1][1].count("."), s_array[1][1].count("#"), row, point)
        res += m*n
print(res)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

from collections import deque

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

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

dir = [(0, 1), (0, -1), (1, 0), (-1, 0)]

ans = 0
for i in range(h):
    for j in range(w):
        if memo[i][j] == 1:
            continue
        memo[i][j] = 1
        black = 0
        white = 0
        if s[i][j] == ".":
            white += 1
        else:
            black += 1
        q = deque([(i, j)])

        while q:
            x, y = q.popleft()
            for dx, dy in dir:
                if not ((0 <= x + dx <= h-1) and (0 <= y + dy <= w-1)):
                    continue
                if memo[x + dx][y + dy] == 0:
                    memo[x + dx][y + dy] = 1
                    if s[x + dx][y + dy] == ".":
                        white += 1
                    else:
                        black += 1
                    q.append((x+dx, y+dy))

        ans += black * white

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

from collections import deque

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

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


ans = 0
for i in range(h):
    for j in range(w):
        if memo[i][j] == 1:
            continue
        memo[i][j] = 1
        black = 0
        white = 0
        if s[i][j] == ".":
            white += 1
        else:
            black += 1
        q = deque([(i, j)])

        while q:
            i, j = q.popleft()
            if i > 0:
                if memo[i - 1][j] == 0 and s[i - 1][j] != s[i][j]:
                    memo[i - 1][j] = 1
                    if s[i - 1][j] == ".":
                        white += 1
                    else:
                        black += 1
                    q.append((i - 1, j))
            if i < h - 1:
                if memo[i + 1][j] == 0 and s[i + 1][j] != s[i][j]:
                    memo[i + 1][j] = 1
                    if s[i + 1][j] == ".":
                        white += 1
                    else:
                        black += 1
                    q.append((i + 1, j))
            if j > 0:
                if memo[i][j - 1] == 0 and s[i][j - 1] != s[i][j]:
                    memo[i][j - 1] = 1
                    if s[i][j - 1] == ".":
                        white += 1
                    else:
                        black += 1
                    q.append((i, j - 1))
            if j < w - 1:
                if memo[i][j + 1] == 0 and s[i][j + 1] != s[i][j]:
                    memo[i][j + 1] = 1
                    if s[i][j + 1] == ".":
                        white += 1
                    else:
                        black += 1
                    q.append((i, j + 1))

        ans += black * white

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

from collections import deque

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

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


ans = 0
for i in range(h):
    for j in range(w):
        if memo[i][j] == 1 or s[i][j] == ".":
            continue
        memo[i][j] = 1
        black = 1
        white = 0
        q = deque([(i, j)])

        while q:
            i, j = q.popleft()
            if i > 0:
                if memo[i - 1][j] == 0 and s[i - 1][j] != s[i][j]:
                    memo[i - 1][j] = 1
                    if s[i - 1][j] == ".":
                        white += 1
                    else:
                        black += 1
                    q.append((i - 1, j))
            if i < h - 1:
                if memo[i + 1][j] == 0 and s[i + 1][j] != s[i][j]:
                    memo[i + 1][j] = 1
                    if s[i + 1][j] == ".":
                        white += 1
                    else:
                        black += 1
                    q.append((i + 1, j))
            if j > 0:
                if memo[i][j - 1] == 0 and s[i][j - 1] != s[i][j]:
                    memo[i][j - 1] = 1
                    if s[i][j - 1] == ".":
                        white += 1
                    else:
                        black += 1
                    q.append((i, j - 1))
            if j < w - 1:
                if memo[i][j + 1] == 0 and s[i][j + 1] != s[i][j]:
                    memo[i][j + 1] = 1
                    if s[i][j + 1] == ".":
                        white += 1
                    else:
                        black += 1
                    q.append((i, j + 1))

        ans += black * white

print(ans)

Submission status: Wrong Answer

Solution code:
import queue
import copy

def solve(h, w, m, t):
    d0 = [1,0,-1,0]
    d1 = [0,-1,0,1]
    c=0
    for i in range(1,h+1):
        for j in range(1,w+1):
            if (m[i][j]=='#' and t[i][j]=='#'):
                bl, wh = 0, 0
                q = queue.Queue()
                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] = t[nci][:ncj]+'*'+t[nci][(ncj+1):]
                            if m[nci][ncj] == '#':
                                bl+=1
                            else:
                                wh+=1
                            q.put([nci,ncj])
                c += bl*wh
            elif (m[i][j]=='#' and t[i][j]=='.'):
                bl, wh = 0, 0
                q = queue.Queue()
                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] = t[nci][:ncj]+'*'+t[nci][(ncj+1):]
                            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 = ["*"*(w+2)]
for i in range(h):
    m.append("*"+input()+"*")
m.append("*"*(w+2))
print(m)
mm = 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]=='#':
                mm[i] = mm[i][:j]+'.'+mm[i][(j+1):]
            else:
                mm[i] = mm[i][:j]+'#'+mm[i][(j+1):]
print(solve(h,w,m,mm))