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:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    
H,W=map(int,input().split())
m=[list(input()) for _ in range(H)]
tree = UnionFind(H*W)
set_w = set()
set_b = set()
for i in range(H):
    for j in range(W):
        if m[i][j] == ".":
            set_w.add(i*W+j)
        else:
            set_b.add(i*W+j)
            
for i in range(H):
    for j in range(W-1):
        if m[i][j] != m[i][j+1]:
            tree.union(i*W+j,i*W+j+1)
for j in range(W):
    for i in range(H-1):
        if m[i][j] != m[i+1][j]:
            tree.union(i*W+j,(i+1)*W+j)
ans=0
print(set_w,set_b)

Submission status: Wrong Answer

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    
H,W=map(int,input().split())
m=[list(input()) for _ in range(H)]
tree = UnionFind(H*W)
set_w = set()
set_b = set()
for i in range(H):
    for j in range(W):
        if m[i][j] == ".":
            set_w.add(i*W+j)
        else:
            set_b.add(i*W+j)
            
for i in range(H):
    for j in range(W-1):
        if m[i][j] != m[i][j+1]:
            tree.union(i*W+j,i*W+j+1)
for j in range(W):
    for i in range(H-1):
        if m[i][j] != m[i+1][j]:
            tree.union(i*W+j,(i+1)*W+j)
ans=0
print(set_w,set_b)
for r in tree.roots():
    l = set(tree.members(r))
    w = len(set_w & l)
    b = len(set_b & l)
    #w = len([0 for x in l if m[x//W][x%W] =='.'])
    #b = len([0 for x in l if m[x//W][x%W] =='#'])
    ans += w*b
print(ans)

Submission status: Wrong Answer

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    
H,W=map(int,input().split())
m=[list(input()) for _ in range(H)]
tree = UnionFind(H*W)
for i in range(H):
    for j in range(W-1):
        if m[i][j] != m[i][j+1]:
            tree.union(i*W+j,i*W+j+1)
for j in range(W):
    for i in range(H-1):
        if m[i][j] != m[i+1][j]:
            tree.union(i*W+j,(i+1)*W+j)
ans=0

Submission status: Wrong Answer

Solution code:
from collections import deque

H,W=map(int,input().split())
S=[]
for i in range(H):
    S.append([c=='#' for c in input()]) # 黒いマスであるか

a=[[[] for j in range(W)] for i in range(H)] # 隣接リスト
for i in range(H-1): # これだけだと，H-1行目のマス同士，W-1列目のマス同士を繋ぐ辺が漏れる
    for j in range(W-1):
        # (i,j)->(i,j+1)
        if S[i][j]^S[i][j+1]:
            a[i][j].append((i,j+1))
            a[i][j+1].append((i,j))
        # (i,j)->(i+1,j)
        if S[i][j]^S[i+1][j]:
            a[i][j].append((i+1,j))
            a[i+1][j].append((i,j))
for j in range(W-1):
    # (H-1,j)->(H-1,j+1) 第H-1行(最下行)
    if S[H-1][j]^S[H-1][j+1]:
        a[H-1][j].append((H-1,j+1))
        a[H-1][j+1].append((H-1,j))
for i in range(H-1):
    # (i,W-1)->(i+1,W-1) 第W-1列(最右列)
    if S[i][W-1]^S[i+1][W-1]:
        a[i][W-1].append((i+1,W-1))
        a[i+1][W-1].append((i,W-1))
# print(a) #DB

ans=0
r=[[False for j in range(W)] for i in range(H)]
q=deque()
for i in range(H):
    for j in range(W):
        if not r[i][j]:            
            q.append((i,j));r[i][j]=True
            root=[S[i][j]]
            while q:
                # print(q) #DB
                i,j=q.popleft()
                for v in a[i][j]:                    
                    k,l=v
                    if not r[k][l]:
                        root.append(S[k][l])
                        q.append((k,l));r[k][l]=True
            ans+=root.count(True)*root.count(False)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

H,W=map(int,input().split())
S=[]
for i in range(H):
    S.append([c=='#' for c in input()])

ans=0
r=[[False for j in range(W)] for i in range(H)]
q=deque()
for i in range(H):
    for j in range(W):
        if not r[i][j]:
            b,w=0,0
            q.append((i,j));r[i][j]=True
            if S[i][j]:
                b+=1
            else:
                w+=1
            while q:
                # print(q) #DB
                i,j=q.popleft()
                for v in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
                    k,l=v
                    if 0<=k<=H-1 and 0<=l<=W-1 and S[i][j]^S[k][l] and not r[k][l]:
                        q.append(v);r[k][l]=True
                        if S[k][l]:
                            b+=1
                        else:
                            w+=1
            ans+=b*w
            # print(ans) #DB

print(ans)

Submission status: Wrong Answer

Solution code:
def main():

    H, W = map(int, input().split())
    A = []
    for _ in range(H): A.append(input())
    print(A)
    ans = 0
    mv = [[1,0],[0,1],[-1,0],[0,-1]]
    for i in range(H):
        for j in range(W):
            if A[i][j] == "#":
                # print(i, j)
                visited = set()
                visited.add((i, j))
                cnt = 0
                cur = [[i, j]]
                while cur:
                    temp = []
                    cnt += 1
                    if cnt % 2 == 1: c = "."
                    else: c = "#"
                    for i1, j1 in cur:
                        for di, dj in mv:
                            k, l = i1+di, j1+dj
                            if 0<=k<H and 0<=l<W and (k, l) not in visited and A[k][l] == c:
                                visited.add((k, l))
                                temp.append([k, l])
                                if c == ".":
                                    ans += 1
                    cur = temp
                # print(i, j, ans)

    return ans

if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
from collections import deque

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

S = []

for i in range(H):

    s = input()

    S.append(s)

lis = [ [True] * W for i in range(H) ]

ans = 0

for h in range(H):

    for w in range(W):

        if not lis[h][w]:
            continue
        
        q = deque([[h,w]])
        lis[h][w] = False

        if S[h][w] == "#":
            bnum = 1
            wnum = 0
        else:
            bnum = 0
            wnum = 1

        while len(q) > 0:

            now = q.popleft()
            nh = now[0]
            nw = now[1]

            if S[nh][nw] == "#":

                if nh > 0 and S[nh-1][nw] == "." and lis[nh-1][nw]:

                    wnum += 1
                    lis[nh-1][nw] = False
                    q.append([nh-1,nw])

                if nh < H-1 and S[nh+1][nw] == "." and lis[nh+1][nw]:

                    wnum += 1
                    lis[nh+1][nw] = False
                    q.append([nh+1,nw])

                if nw > 0 and S[nh][nw-1] == "." and lis[nh][nw-1]:

                    wnum += 1
                    lis[nh-1][nw] = False
                    q.append([nh,nw-1])

                if nw < W-1 and S[nh][nw+1] == "." and lis[nh][nw+1]:

                    wnum += 1
                    lis[nh][nw+1] = False
                    q.append([nh,nw+1])

            if S[nh][nw] == ".":

                if nh > 0 and S[nh-1][nw] == "#" and lis[nh-1][nw]:

                    bnum += 1
                    lis[nh-1][nw] = False
                    q.append([nh-1,nw])

                if nh < H-1 and S[nh+1][nw] == "#" and lis[nh+1][nw]:

                    bnum += 1
                    lis[nh+1][nw] = False
                    q.append([nh+1,nw])

                if nw > 0 and S[nh][nw-1] == "#" and lis[nh][nw-1]:

                    bnum += 1
                    lis[nh][nw-1] = False
                    q.append([nh,nw-1])

                if nw < W-1 and S[nh][nw+1] == "#" and lis[nh][nw+1]:

                    bnum += 1
                    lis[nh][nw+1] = False
                    q.append([nh,nw+1])
                    
        ans += wnum * bnum


print (ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

S = []

for i in range(H):

    s = input()

    S.append(s)

lis = [ [True] * W for i in range(H) ]

ans = 0

for h in range(H):

    for w in range(W):

        if not lis[h][w]:
            continue
        
        q = deque([[h,w]])
        lis[h][w] = False

        if S[h][w] == "#":
            bnum = 1
            wnum = 0
        else:
            bnum = 0
            wnum = 1

        while len(q) > 0:

            now = q.popleft()
            nh = now[0]
            nw = now[1]

            if S[nh][nw] == "#":

                if nh > 0 and S[nh-1][nw] == "." and lis[nh-1][nw]:

                    wnum += 1
                    lis[nh-1][nw] = False
                    q.append([nh-1,nw])

                if nh < H-1 and S[nh+1][nw] == "." and lis[nh+1][nw]:

                    wnum += 1
                    lis[nh+1][nw] = False
                    q.append([nh+1,nw])

                if nw > 0 and S[nh][nw-1] == "." and lis[nh][nw-1]:

                    wnum += 1
                    lis[nh-1][nw] = False
                    q.append([nh,nw-1])

                if nw < W-1 and S[nh][nw+1] == "." and lis[nh][nw+1]:

                    wnum += 1
                    lis[nh][nw+1] = False
                    q.append([nh,nw+1])

            if S[nh][nw] == ".":

                if nh > 0 and S[nh-1][nw] == "#" and lis[nh-1][nw]:

                    bnum += 1
                    lis[nh-1][nw] = False
                    q.append([nh-1,nw])

                if nh < H-1 and S[nh+1][nw] == "#" and lis[nh+1][nw]:

                    bnum += 1
                    lis[nh+1][nw] = False
                    q.append([nh+1,nw])

                if nw > 0 and S[nh][nw-1] == "#" and lis[nh][nw-1]:

                    bnum += 1
                    lis[nh][nw-1] = False
                    q.append([nh-1,nw])

                if nw < W-1 and S[nh][nw+1] == "#" and lis[nh][nw+1]:

                    bnum += 1
                    lis[nh][nw+1] = False
                    q.append([nh,nw+1])
                    
        ans += wnum * bnum


print (ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

S = []

for i in range(H):

    s = input()

    S.append(s)

lis = [ [True] * W for i in range(H) ]

ans = 0

for h in range(H):

    for w in range(W):

        if not lis[h][w]:
            continue
        
        q = deque([[h,w]])
        lis[h][w] = False

        if S[h][w] == "#":
            bnum = 1
            wnum = 0
        else:
            bnum = 0
            wnum = 1

        while len(q) > 0:

            now = q.popleft()
            nh = now[0]
            nw = now[1]

            if S[nh][nw] == "#":

                if nh > 0 and S[nh-1][nw] == "." and lis[nh-1][nw]:

                    wnum += 1
                    lis[nh-1][nw] = False
                    q.append([nh-1,nw])

                if nh < H-1 and S[nh+1][nw] == "." and lis[nh+1][nw]:

                    wnum += 1
                    lis[nh+1][nw] = False
                    q.append([nh+1,nw])

                if nw > 0 and S[nh][nw-1] == "." and lis[nh][nw-1]:

                    wnum += 1
                    lis[nh-1][nw] = False
                    q.append([nh-1,nw])

                if nw < W-1 and S[nh][nw+1] == "." and lis[nh][nw+1]:

                    wnum += 1
                    lis[nh][nw+1] = False
                    q.append([nh,nw+1])

            if S[nh][nw] == ".":

                if nh > 0 and S[nh-1][nw] == "#" and lis[nh-1][nw]:

                    bnum += 1
                    lis[nh-1][nw] = False
                    q.append([nh-1,nw])

                if nh < H-1 and S[nh+1][nw] == "#" and lis[nh+1][nw]:

                    bnum += 1
                    lis[nh+1][nw] = False
                    q.append([nh+1,nw])

                if nw > 0 and S[nh][nw-1] == "#" and lis[nh][nw-1]:

                    bnum += 1
                    lis[nh-1][nw] = False
                    q.append([nh-1,nw])

                if nw < W-1 and S[nh][nw+1] == "#" and lis[nh][nw+1]:

                    bnum += 1
                    lis[nh][nw+1] = False
                    q.append([nh,nw+1])
                    
        ans += wnum * bnum


print (ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools

import queue
from collections import deque

def check(x, y, now_add, color, high, width):
    global data
    move_dic = [(1, 0), (0, 1)]
    for move_x, move_y in move_dic:
        next_x = x + move_x
        next_y = y + move_y
        if 0 <= next_x < high and 0 <= next_y < width:
            if data[next_x][next_y] == 0:
                continue
            if data[next_x][next_y] != data[x][y]:
                now_add.add((i, j))
                color[data[next_x][next_y]] += 1
                check(next_x, next_y, now_add, color, high, width)


def main():
    high, width = map(int, input().split())
    data = [list(input()) for i in range(high)]

    ans = 0
    move_dic = [[1, 0], [0, 1]]

    for i in range(high):
        for j in range(width):
            if data[i][j] == 0:
                continue

            all_ele = set()
            now_ele = set()
            next_ele = set()
            count = defaultdict(int)

            now_ele.add((i, j))
            all_ele.add((i, j))
            count[data[i][j]] += 1

            while len(now_ele) > 0:
                for x, y in now_ele:
                    for move_x, move_y in move_dic:
                        next_x = x + move_x
                        next_y = y + move_y
                        if 0 <= next_x < high and 0 <= next_y < width:
                            if data[next_x][next_y] == 0 or (next_x, next_y) in all_ele:
                                continue
                            if data[next_x][next_y] != data[x][y]:
                                next_ele.add((next_x, next_y))
                                all_ele.add((next_x, next_y))
                                count[data[next_x][next_y]] += 1
                now_ele = next_ele
                next_ele = set()

            ans += count['.'] * count['#']
            for x, y in all_ele:
                data[x][y] = 0

    print(ans)




if __name__ == '__main__':
    main()
    # test()

Submission status: Wrong Answer

Solution code:
# aising2019C - Alternating Path
def dfs(sx: int, sy: int) -> None:
    color, stack = [0] * 2, [(sx, sy, S[sx][sy])]
    while stack:
        x, y, col = stack.pop()
        color[col] += 1
        S[x][y] = 2  # make the grid visited
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == col ^ 1:
                stack.append((nx, ny, S[nx][ny]))
    return color[0] * color[1]


def main():
    # separate S to connected components
    global H, W, S, dxy
    H, W, *S = open(0).read().split()
    H, W = int(H), int(W)
    S = [[1 if i == "#" else 0 for i in s] for s in S]
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    ans = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] != 2:
                ans += dfs(i, j)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

for i in range(H):
    for j in range(W):
        if j < W-1 and S[i][j] != S[i][j+1]:
            es[(i,j)].append((i,j+1))
        if i < H-1 and S[i][j] != S[i+1][j]:
            es[(i,j)].append(((i+1), j))

checked = [False for _ in range(H*W)]

ans = 0
for i in range(H):
    for j in range(W):
        if checked[i*W+j]:
            continue
        checked[i*W+j] =  True
        cnt_b = 0
        cnt_w = 0
        if S[i][j] == "#":
            cnt_b += 1
        else:
            cnt_w += 1
        stack = es[(i,j)]
        
        while True:
            ns = []
            #print(stack)
            for p,q in stack:
                #print("www")
                if checked[p*W+q] == False:
                    #print("aaaaaaaaaaaaaa")
                    checked[p*W+q] = True
                    if S[p][q] == "#":
                        cnt_b += 1
                    else:
                        cnt_w += 1
                    ns.extend(es[(p,q)])
            #print("ns", ns)
            if len(ns) == 0:
                break
            else:
                stack = ns
        ans += cnt_b * cnt_w

print(ans)

Submission status: Wrong Answer

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

def unite(node_a, node_b):
    root_a, depth_a = node_a.root()
    root_b, depth_b = node_b.root()
    if root_a == root_b:# すでに連結成分
        return
    elif depth_a >= depth_b:# aの方が深い
        root_b.is_root = False
        root_b.parent = root_a
        root_a.white += root_b.white
        root_a.black += root_b.black
    else:# bの方が深い
        root_a.is_root = False
        root_a.parent = root_b
        root_b.white += root_a.white
        root_b.black += root_a.black

class Node:
    def __init__(self, color):# color: 0:white, 1:black
        self.parent = None
        self.is_root = True
        self.white = 1 if color == 0 else 0
        self.black = 1 if color == 1 else 0
    
    def root(self):
        node = self
        depth = 0
        while not node.is_root:
            node = node.parent
            depth += 1
        return node, depth

def main():
    H, W = map(int, input().split())
    s = [input().strip() for i in range(H)]
    
    nodes = [[Node(0 if s[j][i] == "." else 1) for i in range(W)] for j in range(H)]

    for y in range(H):
        for x in range(W):
            now = s[y][x]
            for nx, ny in [(x, y-1), (x+1, y), (x, y+1), (x-1, y)]:
                if 0 <= nx and nx < W and 0 <= ny and ny < H:
                    if s[ny][nx] != now:
                        unite(nodes[y][x], nodes[ny][nx])
    
    ans = 0
    count_roots = 0
    for y in range(H):
        for x in range(W):
            if nodes[y][x].is_root:
                count_roots += 1
                node = nodes[y][x]
                ans += node.white * node.black
    print(ans)
    print(count_roots)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def unite(node_a, node_b):
    root_a, depth_a = node_a.root()
    root_b, depth_b = node_b.root()
    if root_a == root_b:# すでに連結成分
        return
    elif depth_a >= depth_b:# aの方が深い
        root_b.is_root = False
        root_b.parent = root_a
        root_a.white += root_b.white
        root_a.black += root_b.black
    else:# bの方が深い
        root_a.is_root = False
        root_a.parent = root_b
        root_a.white += root_b.white
        root_a.black += root_b.black

class Node:
    def __init__(self, color):# color: 0:white, 1:black
        self.parent = None
        self.is_root = True
        self.white = 1 if color == 0 else 0
        self.black = 1 if color == 1 else 0
    
    def root(self):
        node = self
        depth = 0
        while not node.is_root:
            node = node.parent
            depth += 1
        return node, depth

def main():
    H, W = map(int, input().split())
    s = [input().strip() for i in range(H)]
    
    nodes = [[Node(0 if s[j][i] == "." else 1) for i in range(W)] for j in range(H)]

    for y in range(H):
        for x in range(W):
            now = s[y][x]
            for nx, ny in [(x, y-1), (x+1, y), (x, y+1), (x-1, y)]:
                if 0 <= nx and nx < W and 0 <= ny and ny < H:
                    if s[ny][nx] != now:
                        unite(nodes[y][x], nodes[ny][nx])
    
    ans = 0
    for y in range(H):
        for x in range(W):
            if nodes[y][x].is_root:
                node = nodes[y][x]
                ans += node.white * node.black
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
h,w = map(int,input().split())
S = [input() for _ in range(h)]


avail = [[True]*w for _ in range(h)]


def search(i,j,data):
    if S[i][j] == "#":
        data[0] += 1
    else:
        data[1] += 1
    avail[i][j] = False

    if i+1 < h and S[i+1][j] != S[i][j] and avail[i+1][j]:
        search(i+1,j,data)
    if j+1 < w and S[i][j+1] != S[i][j] and avail[i][j+1]:
        search(i,j+1,data)

ans = 0
for i in range(h):
    for j in range(w):
        if avail[i][j]:
            data = [0,0]
            search(i,j,data)
            ans+= data[0]*data[1]

print(ans)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
P=[]
for i in range(h):
  C=[str(_) for _ in input()]
  P+=C
par=[[-1,0,0] for _ in range(h*w)]
def find(x):
  if par[x][0]<0:
    return x
  else:
    par[x][0]=find(par[x][0])
    return par[x][0]
def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return False
  else:
    if par[x][0]>par[y][0]:
      x,y=y,x
    par[x][0]+=par[y][0]
    par[y][0]=x
    return True
def same(x,y):
  return find(x)==find(y)
def size(x):
  return -par[find(x)][0]
for i in range(h*w):
  if P[i]=="#":
    par[i][1]+=1
    if (i+1)%w!=0 and P[i+1]==".":
      unite(i,i+1)
    if (i+w)<(h*w) and P[i+w]==".":
      unite(i,i+w)
  else:
    par[i][2]+=1
    if (i+1)%w!=0 and P[i+1]=="#":
      unite(i,i+1)
    if (i+w)<(h*w) and P[i+w]=="#":
      unite(i,i+w)
ans=0
for p,x,y in par:
  if p>=0:
    par[p][1]+=x
    par[p][2]+=y
for p,x,y in par:
  if p<-1:
    ans+=x*y
print(ans)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
P=[]
for i in range(h):
  C=[str(_) for _ in input()]
  P+=C
par=[[-1,0,0] for _ in range(h*w)]
def find(x):
  if par[x][0]<0:
    return x
  else:
    par[x][0]=find(par[x][0])
    return par[x][0]
def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return False
  else:
    if par[x][0]>par[y][0]:
      x,y=y,x
    par[x][0]+=par[y][0]
    par[y][0]=x
    return True
def same(x,y):
  return find(x)==find(y)
def size(x):
  return -par[find(x)][0]
for i in range(h*w):
  if P[i]=="#":
    par[i][1]+=1
    if (i+1)%w!=0 and P[i+1]==".":
      unite(i,i+1)
    if (i+w)<(h*w) and P[i+w]==".":
      unite(i,i+w)
  if P[i]==".":
    par[i][2]+=1
    if (i+1)%w!=0 and P[i+1]=="#":
      unite(i,i+1)
    if (i+w)<(h*w) and P[i+w]=="#":
      unite(i,i+w)
ans=0
for p,x,y in par:
  if p>=0:
    par[p][1]+=x
    par[p][2]+=y
for p,x,y in par:
  if p<-1:
    ans+=x*y
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W=map(int, input().split())
instr = [input() for _ in range(H)]

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

res = 0
for i in range(1, W):
    fromB, fromW = memo[0][i-1]
    if instr[0][i-1] == '#':
        if instr[0][i] == '.':
            memo[0][i][0] = fromB + 1
            memo[0][i][1] = fromW
            res += fromB + 1
    else:
        if instr[0][i] == '#':
            memo[0][i][0] = fromB
            memo[0][i][1] = fromW + 1
            res += fromW + 1

for i in range(1, H):
    for j in range(0, W):
        fromB1, fromW1 = memo[i-1][j]
        fromB2, fromW2 = memo[i][j-1]
        counted = 1

        if instr[i-1][j] == '#':
            if instr[i][j] == '.': 
                memo[i][j][0] += fromB1 + counted
                memo[i][j][1] += fromW1
                res += fromB1 + counted
                counted = 0
        else:
            if instr[i][j] == '#':
                memo[i][j][0] += fromB1
                memo[i][j][1] += fromW1 + counted
                res += fromW1 + counted
                counted = 0

        if j >= 1:
            if instr[i][j-1] == '#':
                if instr[i][j] == '.':
                    memo[i][j][0] += fromB2 + counted
                    memo[i][j][1] += fromW2
                    res += fromB2 + counted
            else:
                if instr[i][j] == '#':
                    memo[i][j][0] += fromB2
                    memo[i][j][1] += fromW2 + counted
                    res += fromW2 + counted
# print(memo)
print(res)

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 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))
        
        
#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)