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 = 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


    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

    if(flag == False and (s_pos[0] < pos[0] or s_pos[1] < pos[1])):
        count += 1
    return count


count = 0
for i in range(h):
    for j in range(w):
        pos = [i, j]
        t_pos = [w*[0] for i in range(h)]
        count = search(s, h, w, pos, count, pos, t_pos)

print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np
H, W = map(int, input().split())
s_list_list = [input() for _ in range(H)]

color_matrix = []
for l in s_list_list:
    new_l = []
    for string in l:
        if string == "#":
            new_l.append(1)
        else:
            new_l.append(0)
    color_matrix.append(new_l)

color_matrix = np.array(color_matrix)
score_matrix = np.zeros((H,W))

for row in range(H):
    for col in range(W):
        masu = color_matrix[row][col]
        score = 0
        if masu == 1:
            if not col == 0:
                if color_matrix[row][col-1] == 0:
                    score += 1
            if not col == W-1:
                if color_matrix[row][col+1] == 0:
                    score += 1
            if not row == 0:
                if color_matrix[row-1][col] == 0:
                    score += 1
            if not row == H-1:
                if color_matrix[row+1][col] == 0:
                    score += 1
        score_matrix[row][col] += score

new_score_matrix = np.zeros((H,W))


for row in range(H):
    for col in range(W):
        masu = score_matrix[row][col]
        if masu > 0:
            if not (row == 0 or col == 0): 
                hidariue = score_matrix[row-1][col-1]
            else:
                hidariue = 0
            if not col == 0 and not row == H-1:
                hidarisita = score_matrix[row+1][col-1]
            else:
                hidarisita = 0
            if not row == 0 and not col == W-1:
                migiue = score_matrix[row-1][col+1]
            else:
                migiue = 0
            if not (row==H-1 or col == W-1):
                migisita = score_matrix[row+1][col+1]
            else:
                migisita = 0
            if hidariue > 0:
                unions = [color_matrix[row][col-1], color_matrix[row-1][col]]
                unions = (np.array(unions) - 1)*(-1)
                masu += (hidariue - sum(unions))
            if hidarisita > 0:
                unions = [color_matrix[row][col-1], color_matrix[row+1][col]]
                unions = (np.array(unions) - 1)*(-1)
                masu += (hidarisita - sum(unions))
            if migiue > 0:
                unions = [color_matrix[row][col+1], color_matrix[row-1][col]]
                unions = (np.array(unions) - 1)*(-1)
                masu += (migiue - sum(unions))
            if migisita > 0:
                unions = [color_matrix[row][col+1], color_matrix[row+1][col]]
                unions = (np.array(unions) - 1)*(-1)
                masu += (migisita - sum(unions))

        new_score_matrix[row][col] = masu
                
print(int(sum(new_score_matrix.flatten())))

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)]
k[0][0] =1
m = 2

for a in range(h):
    for b in range(w):
        if (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-1] != s[a][b]:
                k[a][b] = k[a][b-1]
            elif s[a][b] != s[a-1][b]:
                k[a][b] = k[a-1][b]
            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:
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [ii for ii in range(n)]
        self.rank = [0 for _ in range(n)]

    def find(self, x):
        """
        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 と 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):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

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

def kake(i, j):
    return i * W + j

u = UnionFind(H * W)

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

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

for i in range(H):
    for j in range(W):
        if (i+j) % 2 == 0:
            ans[u.par[kake(i, j)]][0] += 1
        else:
            ans[u.par[kake(i, j)]][1] += 1

pri = 0

for i in range(H):
    for j in range(W):
        pri += ans[kake(i, j)][0] * ans[kake(i, j)][1]

print(pri)

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
before = 0
for i, raw in enumerate(b_list):
    for j in raw:
         before += len(res[i][j])
while True:
    for i, raw in enumerate(b_list):
        for j in raw:
            try:
                if S[i-1][j] == '.' or S[i][j-1] == '.':
                    res[i][j] += res[i-1][j-1]
            except:
                pass
            try:
                if S[i+1][j] == '.' or S[i][j-1] == '.':
                    res[i][j] += res[i+1][j-1]
            except:
                pass
            try:
                if S[i-1][j] == '.' or S[i][j+1] == '.':
                    res[i][j] += res[i-1][j+1]
            except:
                pass
            try:
                if S[i+1][j] == '.' or S[i][j+1] == '.':
                    res[i][j] += res[i+1][j+1]
            except:
                pass
    for i, raw in enumerate(b_list):
        for j in raw:
            res[i][j] = list(set(res[i][j]))
    result = 0
    for i, raw in enumerate(b_list):
        for j in raw:
             result += len(res[i][j])
    if before == result:
        break
    before = result
print(result)

Submission status: Wrong Answer

Solution code:
#import sys

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

s =[input() for _ in range(H)]
bw = set()
bb = set()

for n,i in enumerate(s):
    for m,j in enumerate(i):
        if j == '.':
            continue
        if n!=0 and s[n-1][m]=='.':
            bw.add(((n,m),(n-1,m)))
            # if n-1!=0 and s[n-2][m]=='#':
            #     bb.add(((n,m),(n-2,m)))
            # if m!=0 and s[n-1][m-1]=='#':
            #     bb.add(((n,m),(n-1,m-1)))
            # if m!=W-1 and s[n-1][m+1]=='#':
            #     bb.add(((n,m),(n-1,m+1)))

        if m!=0 and s[n][m-1]=='.':
            bw.add(((n,m),(n,m-1)))
            # if n!=0 and s[n-1][m-1]=='#':
            #     bb.add(((n,m),(n-1,m-1)))
            if m-1!=0 and s[n][m-2]=='#':
                bb.add(((n,m),(n,m-2)))
            if n!=H-1 and s[n+1][m-1]=='#':
                bb.add(((n,m),(n+1,m-1)))

        if n!=H-1 and s[n+1][m]=='.':
            bw.add(((n,m),(n+1,m)))
            if m!=0 and s[n+1][m-1]=='#':
                bb.add(((n,m),(n+1,m-1)))
            if n+1!=H-1 and s[n+2][m]=='#':
                bb.add(((n,m),(n+2,m)))
            if m!=W-1 and s[n+1][m+1]=='#':
                bb.add(((n,m),(n+1,m+1)))

        if m!=W-1 and s[n][m+1]=='.':
            bw.add(((n,m),(n,m+1)))
            # if n!=0 and s[n-1][m+1]=='#':
            #     bb.add(((n,m),(n-1,m+1)))
            if n!=H-1 and s[n+1][m+1]=='#':
                bb.add(((n,m),(n+1,m+1)))
            if m+1!=W-1 and s[n][m+2]=='#':
                bb.add(((n,m),(n,m+2)))
bw2 = set()
for i in bb:
    b0,b1 = i
    for j in bw:
        b2,w0 = j
        if b1 == b2:
            bw2.add((b0,w0))
    b1,b0 = b0,b1
    for j in bw:
        b2,w0 = j
        if b1 == b2:
            bw2.add((b0,w0))
            

for l in bw2:
    bw.add(l)
print(len(bw))

Submission status: Wrong Answer

Solution code:
def solve(H, W, Ss):
    d = [[-1 for __ in range(W)] for _ in range(H)]

    index = 0
    for (sh, sw) in [(h, w) for h in range(0, H) for w in range(0, W) if Ss[h][w] == "#"]:
        if d[sh][sw] == -1:
            que = [(sh, sw)]
            index += 1
            d[sh][sw] = index

            while len(que):
                h, w = que.pop()
                for (hi, wi) in [(h + 1, w), (h - 1, w), (h, w - 1), (h, w + 1)]:
                    if 0 <= hi < H and 0 <= wi < W:
                        if Ss[hi][wi] != Ss[h][w] and d[hi][wi] == -1:
                            que.append((hi, wi))
                            d[hi][wi] = index
    c = [[0, 0] for _ in range(index + 1)]
    for h in range(0, H):
        for w in range(0, W):
            if Ss[h][w] == ".":
                c[d[h][w]][0] += 1
            elif Ss[h][w] == "#":
                c[d[h][w]][1] += 1
    ans = sum([b * w for (w, b) in c])
    return ans

if __name__ == "__main__":
    H, W = tuple(map(int, input().split(" ")))
    Ss = list([input() for l in range(H)])
    print(solve(H, W, Ss))

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):
        """
        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 と 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):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

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

def kake(i, j):
    return i * W + j

u = UnionFind(H * W)

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

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

for i in range(H):
    for j in range(W):
        if (i+j)%2 == 0:
            ans[u.par[kake(i, j)]][0] += 1
        else:
            ans[u.par[kake(i, j)]][1] += 1

pri = 0

for i in range(H):
    for j in range(W):
        pri += ans[kake(i, j)][0] * ans[kake(i, j)][1]

print(pri)

Submission status: Wrong Answer

Solution code:
#!/Users/takahiro.kida/git/atcorder/venv/bin/python

import numpy
import scipy

from collections import defaultdict
from pprint import pprint

H,W = [int(x) for x in input().split(" ")]
S = [input() for x in range(H)]
belongs = {}
group = defaultdict(lambda: defaultdict(int))
i = 0
for h in range(H):
    for w in range(W):
        i = i+1
        no = h*W+w
        color = S[h][w]
        group_no = None
        if not no in belongs:
            group[no][color] =+ 1
            belongs[no] = no
            group_no = no
        else:
            group_no = belongs[no]
        if h + 1 < H:
            down = (h+1) * W + w
            down_color = S[h+1][w]
            if not down in belongs and color != down_color:
                group[group_no][down_color] += 1
                belongs[down] = group_no
        if w + 1 < W:
            right = h * W + w + 1
            right_color = S[h][w+1]
            if not right in belongs and color != right_color:
                group[group_no][right_color] += 1
                belongs[right] = group_no


cnt = 0
for g in group.values():
    cnt += g["."] * g["#"]

print(cnt)

Submission status: Wrong Answer

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

num=1
S0[0][0]=0

for i in range(H):
	for j in range(W):
		if i==0 and j==0:
			continue
		if i>0 and j>0:
			if S[i-1][j]!=S[i][j] and S[i][j-1]!=S[i][j]:
				S0[i][j]=S0[i-1][j]
				k=0
				while j-k-1>=0:
					if S[i][j-k-1]==S[i][j-k]:
						break
					S0[i][j-k-1]=S0[i-1][j]
					k+=1
			elif S[i-1][j]!=S[i][j]:
				S0[i][j]=S0[i-1][j]
			elif S[i][j-1]!=S[i][j]:
				S0[i][j]=S0[i][j-1]

			if S[i-1][j]==S[i][j] and S[i][j-1]==S[i][j]:
				S0[i][j]=num
				num+=1
		if i==0:
			if S[i][j-1]!=S[i][j]:
				S0[i][j]=S0[i][j-1]
			if S[i][j-1]==S[i][j]:
				S0[i][j]=num
				num+=1
		if j==0:
			if S[i-1][j]!=S[i][j]:
				S0[i][j]=S0[i-1][j]
			if S[i-1][j]==S[i][j]:
				S0[i][j]=num
				num+=1
# print(S0)
ans=0
a=[[0, 0] for _ in range(num)]

for i in range(H):
	for j in range(W):
			if S[i][j]=='#':
				a[S0[i][j]][0]+=1
			else:
				a[S0[i][j]][1]+=1
# print(a)
for i in range(num):
	ans+=a[i][0]*a[i][1]
print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [0] * (n + 1)

    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 self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


def solve():
    H, W = map(int, input().split())
    C = [[0] * W for _ in range(H)]
    for i, _ in enumerate(range(H)):
        for j, c in enumerate(input()):
            if c == '#':
                C[i][j] = 1

    uf = UnionFind(H * W)

    for i in range(H):
        for j in range(W):
            if i != 0 and C[i][j] != C[i - 1][j]:
                uf.union(i * W + j, (i - 1) * W + j)
            if j != 0 and C[i][j] != C[i][j - 1]:
                uf.union(i * W + j, i * W + j - 1)
    # count
    cnt = dict()
    for i in range(H):
        for j in range(W):
            par = uf.par[i * W + j]
            wh, bl = cnt.get(par, (0, 0))
            if C[i][j] == 0:
                cnt[par] = (wh + 1, bl)
            else:
                cnt[par] = (wh, bl + 1)

    print(sum(map(lambda x: x[0] * x[1], cnt.values())))


if __name__ == '__main__':
    solve()

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
                ans+=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
    ans+=max(0,a[uy][ux]+a[vy][vx]-4)
for t in q:
    u,v=t
    uy,ux=u
    vy,vx=v
    ans+=max(0,a[uy][ux]+a[vy][vx]-2)
print(ans)

Submission status: Wrong Answer

Solution code:
#!/Users/takahiro.kida/git/atcorder/venv/bin/python

import numpy
import scipy

from collections import defaultdict
from pprint import pprint

H,W = [int(x) for x in input().split(" ")]
S = [input() for x in range(H)]
belongs = {}
group = defaultdict(lambda: defaultdict(int))
i = 0
for h in range(H):
    for w in range(W):
        i = i+1
        no = h*W+w
        color = S[h][w]
        group_no = None
        if not (belongs.get(no) or belongs.get(no) == 0):
            group[no][color] =+ 1
            belongs[no] = no
            group_no = no
        else:
            group_no = belongs[no]
        if h + 1 < H:
            down = (h+1) * W + w
            down_color = S[h+1][w]
            if not down in belongs and color != down_color:
                group[group_no][down_color] += 1
                belongs[down] = group_no
        if w + 1 < W:
            right = h * W + w + 1
            right_color = S[h][w+1]
            if not right in belongs and color != right_color:
                group[group_no][right_color] += 1
                belongs[right] = group_no


cnt = 0
for g in group.values():
    cnt += g["."] * g["#"]

print(cnt)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
board = []
black = "#"
white = "."
for _ in range(H):
    board.append(input())

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

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

ans = 0

for start_i in range(H):
    for start_j in range(W):
        if flags[start_i][start_j] is True:
            continue
        else:
            flags[start_i][start_j] = True
            reachable = 1
            n_black = 0
            n_white = 0
            if board[start_i][start_j] == black:
                n_black = 1
            else:
                n_white = 1
            visit = []
            for dx, dy in deltas:
                if \
                start_i + dx >= 0 \
                and start_i + dx < H \
                and start_j + dy >= 0 \
                and start_j + dy < W \
                and board[start_i][start_j] != board[start_i + dx][start_j + dy] \
                and flags[start_i + dx][start_j + dy] is False:
                    visit.append((start_i, start_j, start_i + dx, start_j + dy))
                    reachable += 1
                    flags[start_i + dx][start_j + dy] = True
                    if board[start_i + dx][start_j + dy] == black:
                        n_black += 1
                    else:
                        n_white += 1
            while len(visit) != 0:
                visit_info = visit.pop()
                prev_i = visit_info[0]
                prev_j = visit_info[1]
                next_i = visit_info[2]
                next_j = visit_info[3]

                start_i = next_i
                start_j = next_j
                for dx, dy in deltas:
                    if \
                    start_i + dx >= 0 \
                    and start_i + dx < H \
                    and start_j + dy >= 0 \
                    and start_j + dy < W \
                    and board[start_i][start_j] != board[start_i + dx][start_j + dy] \
                    and flags[start_i + dx][start_j + dy] is False:
                        visit.append((start_i, start_j, start_i + dx, start_j + dy))
                        reachable += 1
                        flags[start_i + dx][start_j + dy] = True
                        if board[start_i + dx][start_j + dy] == black:
                            n_black += 1
                        else:
                            n_white += 1
            if reachable >= 2:
                ans += n_black * n_white

print(ans)

Submission status: Wrong Answer

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

black_l = np.zeros(H*W+1)
white_l = np.zeros(H*W+1)
new = 1
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 Sarr[i,j] == 1:
            black_l[int(Marr[i,j])] += 1
        else:
            white_l[int(Marr[i,j])] += 1

print(int(black_l.dot(white_l)))

Submission status: Wrong Answer

Solution code:
import itertools
h, w = map(int, input().split())
s_list = []
for i in range(h):
  s_list.append(list(input()))
area_list = []
check_list = set()

def rec_create_area(point, tmp_area, current_str):
  new_point_list = []
  new_point_list.append((point[0] + 1, point[1]))
  new_point_list.append((point[0], point[1] + 1))
  for new_point in new_point_list:
    if new_point[0] >= h or new_point[1] >= w:
      continue
    if new_point in check_list:
      continue
    new_str = s_list[new_point[0]][new_point[1]]
    if new_str == current_str:
      continue
    if new_str == "#":
      tmp_area[0] += 1
    else:
      tmp_area[1] += 1
    check_list.add(new_point)
    rec_create_area(new_point, tmp_area, new_str)
  
for a, b in itertools.product(range(h), range(w)):
  check_point = (a, b)
  if check_point in check_list:
    continue
  check_list.add(check_point)
  current_str = s_list[0][0]
  if current_str == "#":
    tmp_area = [1, 0]
  else:
    tmp_area = [0, 1]
  rec_create_area(check_point, tmp_area, current_str)
  area_list.append(tmp_area)
  
print(sum([x[0] * x[1] for x in area_list]))

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
S = ['' for i in range(H)]
for i in range(H):
  S[i] = input()
R = [[[i, j] for j in range(W)] for i in range(H)]
U = [[1 for j in range(W)] for i in range(H)]
def root(A):
  if R[A[0]][A[1]] == A:
    return A
  else:
    R[A[0]][A[1]] = root(R[A[0]][A[1]])
    return R[A[0]][A[1]]
def union(A, B):
  rA = root(A)
  rB = root(B)
  if rA[0] < rB[0]:
    R[rB[0]][rB[1]] = rA
    U[rA[0]][rA[1]] += U[rB[0]][rB[1]]
  elif rB[0] < rA[0]:
    R[rA[0]][rA[1]] = rB
    U[rB[0]][rB[1]] += U[rA[0]][rA[1]]
  elif rA[1] < rB[1]:
    R[rB[0]][rB[1]] = rA
    U[rA[0]][rA[1]] += U[rB[0]][rB[1]]
  elif rB[1] < rA[1]:
    R[rA[0]][rA[1]] = rB
    U[rB[0]][rB[1]] += U[rA[0]][rA[1]]
for i in range(H):
  for j in range(W):
    if S[i][j] == ".":
      if i > 0 and S[i - 1][j] == "#":
        if j > 0 and S[i - 1][j - 1] == ".":
          union([i, j], [i - 1, j - 1])
        if i > 1 and S[i - 2][j] == ".":
          union([i, j], [i - 2, j])
        if j < W - 1 and S[i - 1][j + 1] == ".":
          union([i, j], [i - 1, j + 1])
      if j > 0 and S[i][j - 1] == "#":
        if i > 0 and S[i - 1][j - 1] == ".":
          union([i, j], [i - 1, j - 1])
        if i > 1 and S[i - 2][j] == ".":
          union([i, j], [i - 2, j])
      if j < W - 1 and S[i][j + 1] == "#":
        if i > 0 and S[i -1][j + 1] == ".":
          union([i, j], [i - 1, j + 1])
for i in range(H):
  for j in range(W):
    root([i, j])
cnt = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == "#":
      if i > 0 and S[i - 1][j] == ".":
        r = R[i - 1][j]
        cnt += U[r[0]][r[1]]
      elif i < H - 1 and S[i + 1][j] == ".":
        r = R[i + 1][j]
        cnt += U[r[0]][r[1]]
      elif j > 0 and S[i][j - 1] == ".":
        r = R[i][j - 1]
        cnt += U[r[0]][r[1]]
      elif j < W - 1 and S[i][j + 1] == ".":
        r = R[i][j + 1]
        cnt += U[r[0]][r[1]]
print(cnt)

Submission status: Wrong Answer

Solution code:
class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]


    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])


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

        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

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

def kake(i, j):
    return i * W + j

u = UnionFind(H*W)

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

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

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

for i in range(H):
    for j in range(W):
        if (i+j)%2 == 0:
            ans[u.parent[kake(i, j)]][0] += 1
        else:
            ans[u.parent[kake(i, j)]][1] += 1

pri = 0

for i in range(H):
    for j in range(W):
        pri += ans[kake(i, j)][0] * ans[kake(i, j)][1]

print(pri)

Submission status: Wrong Answer

Solution code:
from collections import Counter
H, W = map(int, input().split())
S = [input() for h in range(H)]
ans = 0
union_white = [[0 for w in range(W)]for h in range(H)]
union_black = Counter()
count_black = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            continue
        count_black += 1
        if i >= 1 and S[i-1][j] == '.':
            if union_white[i-1][j] != 0:
                count_black = union_white[i-1][j]
            union_white[i-1][j] = count_black
        if i < H-1 and S[i+1][j] == '.':
            if union_white[i+1][j] != 0:
                count_black = union_white[i+1][j]
            union_white[i+1][j] = count_black
        if j >= 1 and S[i][j-1] == '.':
            if union_white[i][j-1] != 0:
                count_black = union_white[i][j-1]
            union_white[i][j-1] = count_black
        if j < W-1 and S[i][j+1] == '.':
            if union_white[i][j+1] != 0:
                count_black = union_white[i][j+1]
            union_white[i][j+1] = count_black
        union_black[count_black] += 1
# print(ans)
counter = Counter([x for Si in union_white for x in Si])
# print(counter)
# print(union_black)
ans = 0
for i in union_black.keys():
    ans += counter[i] * union_black[i]

print(ans)