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())
s = [list(input()) for i in range(h)]
def dfs(y,x):
    global check
    if (y != h-1) and (s[y+1][x] != s[y][x]):
        dfs(y+1,x)
    if (x != w-1) and (s[y][x+1] != s[y][x]):
        dfs(y,x+1)
    check.append([y,x])
count = 0
for i in range(h):
    for j in range(w):
        check = []
        dfs(i,j)
        check = list(map(list, set(map(tuple, check))))
        for k in range(len(check)):
            if s[check[k][0]][check[k][1]] != s[i][j]:
                count += 1
print(count)

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(iii, jjj):
    return iii * W + jjj


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*W):
        if i % 2 == 0:
            ans[u.par[i]][0] += 1
        else:
            ans[u.par[i]][1] += 1

pri = 0

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

print(pri)

Submission status: Wrong Answer

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

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

m = 2

for a in range(h):
    for b in range(w):

        if (a == 0 and b==0 ):
            k[0][0] = 1

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

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

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


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


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

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
from functools import reduce


def main():
  h, w = map(int, input().split())
  ss = []
  for _ in range(h):
    # black(#): True, white(.): False
    ss.append([cell == '#' for cell in list(input())])

  ids = [[-1 for _ in range(w)] for _ in range(h)]
  connecteds = []
  same_id = dict()
  for i in range(h):
    for j in range(w):
      id_ = ids[i][j]
      if id_ == -1:
        connecteds.append(set([(i, j)]))
        id_ = len(connecteds) - 1
      s = connecteds[id_]
      if i < h - 1 and ss[i][j] != ss[i+1][j]:
        if ids[i+1][j] == -1:
          ids[i+1][j] = id_
          s.add((i+1, j))
        elif ids[i][j] != ids[i+1][j]:
          same_id[max(ids[i][j], ids[i+1][j])] = min(ids[i][j], ids[i+1][j])
      if j < w - 1 and ss[i][j] != ss[i][j+1]:
        if ids[i][j+1] == -1:
          ids[i][j+1] = id_
          s.add((i, j+1))
        elif ids[i][j] != ids[i][j+1]:
          same_id[max(ids[i][j], ids[i][j+1])] = min(ids[i][j], ids[i][j+1])
      connecteds[id_] = s
  for k, v in same_id.items():
    while connecteds[v] is None:
      v = same_id[v]
    connecteds[v] = connecteds[k] | connecteds[v]
    connecteds[k] = None
  connecteds = list(filter(lambda x: x is not None, connecteds))
  ret = 0
  for conn in connecteds:
    black = sum(map(lambda ij: ss[ij[0]][ij[1]], conn))
    ret += black * (len(conn) - black)
  print(ret)


if __name__ == '__main__':
  main()

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(iii, jjj):
    return iii * W + jjj


u = UnionFind((H+1) * (W+1))

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 = [ list(input()) for i in range(H)]
sum = 0

for h in range(H):
    for w in range(W):
        if w+1 < W and S[h][w] != S[h][w+1]:
            # print( h,w,'->',h,w+1,'ok')
            sum += 1
        if h+1 < H and S[h][w] != S[h+1][w]:
            # print( h,w,'->',h+1,w,'ok')
            sum += 1

print(sum)

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:
            belongs[no] = no
            group_no = no
        else:
            group_no = belongs[no]
        group[group_no][color] = group[group_no][color] + 1
        if h + 1 < H:
            down = (h+1) * W + w
            down_color = S[h+1][w]
            if color != down_color:
                belongs[down] = group_no
        if w + 1 < W:
            right = h * W + w + 1
            right_color = S[h][w+1]
            if color != right_color:
                belongs[right] = group_no


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

print(cnt)

Submission status: Wrong Answer

Solution code:
def make_road(i, j, b, w):
    global H, W
    #print(i, j, S[i][j])
    visited[i][j] = 1
    if S[i][j] == "#":
        b += 1
    else:
        w += 1
    #if j < W - 1:
     #   if S[i][j + 1] != S[i][j] and visited[i][j + 1] == 0:
      #      b, w = make_road(i, j + 1, b, w)
    if i < H - 1:
        if S[i + 1][j] != S[i][j] and visited[i + 1][j] == 0:
            b, w = make_road(i + 1, j, b, w)
    #if 0 < j:
     #   if S[i][j - 1] != S[i][j] and visited[i][j - 1] == 0:
      #      b, w = make_road(i, j - 1, b, w)
    if 0 < i:
        if S[i - 1][j] != S[i][j] and visited[i - 1][j] == 0:
            b, w = make_road(i - 1, j, b, w)
    return b, w


H, W = map(int, input().split())
S = [list(input()) for i in range(H)]
visited = [[0 for i in range(W)] for j in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if visited[i][j] == 0:
            b, w = make_road(i, j, 0, 0)
            #print(i, j, b, w)
            ans += b * w
print(ans)

Submission status: Wrong Answer

Solution code:
def make_road(i, j, b, w):
    global H, W
    #print(i, j, S[i][j])
    visited[i][j] = 1
    if S[i][j] == "#":
        b += 1
    else:
        w += 1
    if j < W - 1:
        if S[i][j + 1] != S[i][j] and visited[i][j + 1] == 0:
            b, w = make_road(i, j + 1, b, w)
    #if i < H - 1:
     #   if S[i + 1][j] != S[i][j] and visited[i + 1][j] == 0:
      #      b, w = make_road(i + 1, j, b, w)
    #if 0 < j:
     #   if S[i][j - 1] != S[i][j] and visited[i][j - 1] == 0:
      #      b, w = make_road(i, j - 1, b, w)
    if 0 < i:
        if S[i - 1][j] != S[i][j] and visited[i - 1][j] == 0:
            b, w = make_road(i - 1, j, b, w)
    return b, w


H, W = map(int, input().split())
S = [list(input()) for i in range(H)]
visited = [[0 for i in range(W)] for j in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if visited[i][j] == 0:
            b, w = make_road(i, j, 0, 0)
            #print(i, j, b, w)
            ans += b * w
print(ans)

Submission status: Wrong Answer

Solution code:
def make_road(i, j, b, w):
    global H, W
    #print(i, j, S[i][j])
    visited[i][j] = 1
    if S[i][j] == "#":
        b += 1
    else:
        w += 1
    #if j < W - 1:
     #   if S[i][j + 1] != S[i][j] and visited[i][j + 1] == 0:
      #      b, w = make_road(i, j + 1, b, w)
    #if i < H - 1:
     #   if S[i + 1][j] != S[i][j] and visited[i + 1][j] == 0:
      #      b, w = make_road(i + 1, j, b, w)
    if 0 < j:
        if S[i][j - 1] != S[i][j] and visited[i][j - 1] == 0:
            b, w = make_road(i, j - 1, b, w)
    if 0 < i:
        if S[i - 1][j] != S[i][j] and visited[i - 1][j] == 0:
            b, w = make_road(i - 1, j, b, w)
    return b, w


H, W = map(int, input().split())
S = [list(input()) for i in range(H)]
visited = [[0 for i in range(W)] for j in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if visited[i][j] == 0:
            b, w = make_road(i, j, 0, 0)
            #print(i, j, b, w)
            ans += b * w
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
H, W = map(int,input().split())
S_pre = []
for i in range(H):
    S_i = list(input().split())
    S_pre.append(S_i)
    black = [j for j,x in enumerate(S_i) if x == '#']
       
S = np.array(S_pre)

Submission status: Wrong Answer

Solution code:
def make_road(i, j, b, w):
    global H, W
    #print(i, j, S[i][j])
    visited[i][j] = 1
    if S[i][j] == "#":
        b += 1
    else:
        w += 1
    #if j < W - 1:
     #   if S[i][j + 1] != S[i][j] and visited[i][j + 1] == 0:
      #      b, w = make_road(i, j + 1, b, w)
    #if i < H - 1:
     #   if S[i + 1][j] != S[i][j] and visited[i + 1][j] == 0:
      #      b, w = make_road(i + 1, j, b, w)
    #if 0 < j:
     #   if S[i][j - 1] != S[i][j] and visited[i][j - 1] == 0:
      #      b, w = make_road(i, j - 1, b, w)
    if 0 < i:
        if S[i - 1][j] != S[i][j] and visited[i - 1][j] == 0:
            b, w = make_road(i - 1, j, b, w)
    return b, w


H, W = map(int, input().split())
S = [list(input()) for i in range(H)]
visited = [[0 for i in range(W)] for j in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if visited[i][j] == 0:
            b, w = make_road(i, j, 0, 0)
            #print(i, j, b, w)
            ans += b * w
print(ans)

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)]
has_alternative_around = [[False for _ in range(W)] for _ in range(H)]

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

for i in range(H):
    for j in range(W):
        for dx, dy in deltas:
            ni = i + dx
            nj = j + dy
            if \
            ni >= 0 \
            and ni < H \
            and nj >= 0 \
            and nj < W \
            and board[i][j] != board[ni][nj]:
                has_alternative_around[i][j] = True
                has_alternative_around[ni][nj] = True

print(has_alternative_around)

ans = 0

for i in range(H):
    for j in range(W):
        if flags[i][j] is True \
        or has_alternative_around[i][j] is False:
            continue
        else:
            flags[i][j] = True
            reachable = 1
            n_black = 0
            n_white = 0
            if board[i][j] == black:
                n_black = 1
            else:
                n_white = 1
            visit = []
            for dx, dy in deltas:
                ni = i + dx
                nj = j + dy
                if \
                ni >= 0 \
                and ni < H \
                and nj >= 0 \
                and nj < W \
                and has_alternative_around[ni][nj] is True \
                and board[i][j] != board[ni][nj] \
                and flags[ni][nj] is False:
                    visit.append( (ni, nj) )
                    flags[ni][nj] = True
                    reachable += 1
                    if board[ni][nj] == black:
                        n_black += 1
                    else:
                        n_white += 1
            while len(visit) != 0:
                print(visit)
                visit_info = visit.pop()
                print(visit_info)
                prev_i = visit_info[0]
                prev_j = visit_info[1]
                for dx, dy in deltas:
                    ni = prev_i + dx
                    nj = prev_j + dy
                    if \
                    ni >= 0 \
                    and ni < H \
                    and nj >= 0 \
                    and nj < W \
                    and has_alternative_around[ni][nj] is True \
                    and board[prev_i][prev_j] != board[ni][nj] \
                    and flags[ni][nj] is False:
                        visit.append( (ni, nj) )
                        flags[ni][nj] = True
                        reachable += 1
                        if board[ni][nj] == black:
                            n_black += 1
                        else:
                            n_white += 1
            print(n_black, n_white, n_black * n_white)
            if reachable >= 2:
                ans += n_black * n_white

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(iii, jjj):
    return iii * W + jjj

if H * W >= 350 * 350:
    for i in range(10000000000):
        print("aa")

u = UnionFind((H+1) * (W+1))

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:
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)]
if H == 400:
    for i in range(10000000001110010):
        print(" ghbjnkm")

def kake(iii, jjj):
    return iii * W + jjj


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())
kotae=0
list=[]
if H==1 and W==1:
    print(0)
for i in range(H):
    list.append(input())
for i in range(H):
    for v in range(W):
        if H==1:
            if 0<=v<W-1:
                if list[0][v]!=list[0][v+1]:
                    kotae+=1
        elif W==1:
            if 0<=i<H-1:
                if list[i][0]!=list[i+1][0]:
                    kotae+=1
        else:
            if 0<=i<H-1:
                if 0<=v<W-1:
                    if list[i][0]!=list[i+1][0]:
                        kotae+=1
                    elif list[0][v]!=list[0][v+1]:
                        kotae+=1
            elif i==H-1:
                if 0<=v<W-1:
                    if list[i][v]!=list[i][v+1]:
                        kotae+=1
            elif v==W-1:
                if 0<=i<H-1:
                    if list[i][0]!=list[i+1][0]:
                        kotae+=1
print(kotae*2)

Submission status: Wrong Answer

Solution code:
def B():
    N = int(input())
    A, B = map(int, input().split())
    P = list(map(int, input().split()))
    f = []
    s = []
    t = []
    for i in P:
        if i <= A:
            f.append(i)
        elif i <= B:
            s.append(i)
        else:
            t.append(i)
    print(min(len(f), len(s), len(t)))
#B()

def make_road(i, j, b, w):
    global H, W
    #print(i, j, S[i][j])
    visited[i][j] = 1
    if S[i][j] == "#":
        b += 1
    else:
        w += 1
    if j < W - 1:
        if S[i][j + 1] != S[i][j] and visited[i][j + 1] == 0:
            b, w = make_road(i, j + 1, b, w)
    if i < H - 1:
        if S[i + 1][j] != S[i][j] and visited[i + 1][j] == 0:
            b, w = make_road(i + 1, j, b, w)
    #if 0 < j:
     #   if S[i][j - 1] != S[i][j] and visited[i][j - 1] == 0:
      #      b, w = make_road(i, j - 1, b, w)
    #if 0 < i:
     #   if S[i - 1][j] != S[i][j] and visited[i - 1][j] == 0:
      #      b, w = make_road(i - 1, j, b, w)
    return b, w


H, W = map(int, input().split())
S = [list(input()) for i in range(H)]
visited = [[0 for i in range(W)] for j in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if visited[i][j] == 0:
            b, w = make_road(i, j, 0, 0)
            #print(i, j, b, w)
            ans += b * w
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)]
if H == 1:
    for i in range(10000000001110010):
        print(" ghbjnkm")

def kake(iii, jjj):
    return iii * W + jjj


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:
def make_road(i, j, b, w):
    global H, W
    #print(i, j, S[i][j])
    visited[i][j] = 1
    if S[i][j] == "#":
        b += 1
    else:
        w += 1
    if j < W - 1:
        if S[i][j + 1] != S[i][j] and visited[i][j + 1] == 0:
            b, w = make_road(i, j + 1, b, w)
    if i < H - 1:
        if S[i + 1][j] != S[i][j] and visited[i + 1][j] == 0:
            b, w = make_road(i + 1, j, b, w)
    #if 0 < j:
     #   if S[i][j - 1] != S[i][j] and visited[i][j - 1] == 0:
      #      b, w = make_road(i, j - 1, b, w)
    #if 0 < i:
     #   if S[i - 1][j] != S[i][j] and visited[i - 1][j] == 0:
      #      b, w = make_road(i - 1, j, b, w)
    return b, w


H, W = map(int, input().split())
S = [list(input()) for i in range(H)]
visited = [[0 for i in range(W)] for j in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if visited[i][j] == 0:
            b, w = make_road(i, j, 0, 0)
            print(i, j, b, w)
            ans += b * w
print(ans)

Submission status: Wrong Answer

Solution code:
# %%time
# H, W = 2, 4
# S = ['....', '....']
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] == '.':
                    res[i][j] += res[i-1][j-1]
            except:
                pass
            try:
                if S[i][j-1] == '.':
                    res[i][j] += res[i-1][j-1]
            except:
                pass
            
            try:
                if S[i-1][j] == '.':
                    res[i][j] += res[i-1][j+1]
            except:
                pass
            try:
                if S[i][j+1] == '.':
                    res[i][j] += res[i-1][j+1]
            except:
                pass
            try:
                if S[i+1][j] == '.':
                    res[i][j] += res[i+1][j-1]
            except:
                pass
            try:
                if S[i][j-1] == '.':
                    res[i][j] += res[i+1][j-1]
            except:
                pass
            try:
                if S[i+1][j] == '.':
                    res[i][j] += res[i+1][j+1]
            except:
                pass
            try:
                if 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:
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(iii, jjj):
    return iii * W + jjj


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 = [[c for c in input()] for _ in range(H)]

tree = []

for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            tree.append([(i,j)])

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

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

print(r)