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: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int,input().split())
S = [list(input()) for i in range(H)]
blacklist = []
for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            blacklist.append((h,w))
count = 0
alr = [[0 for i in range(W)] for j in range(H)]
h1 = [0,0,1,-1]
w1 = [1,-1,0,0]
for h,w in blacklist:
    que = deque()
    que.append((h,w,True))
    alr[h][w] = 1
    alr2 = [(h,w)]
    while que:
        hn,wn,black = que.popleft()
        black = not black
        for i in range(4):
            if 0 <= hn+h1[i] <= H-1 and 0 <= wn+w1[i] <= W-1 and (hn+h1[i],wn+w1[i]) not in alr2:
                if (not black) and S[hn+h1[i]][wn+w1[i]] == '.':
                    if not alr[hn+h1[i]][wn+w1[i]]:
                        count += 1
                    que.append((hn+h1[i],wn+w1[i],black))
                    alr2.append((hn+h1[i],wn+w1[i]))
                elif black and S[hn+h1[i]][wn+w1[i]] == '#':
                    que.append((hn+h1[i],wn+w1[i],black))
                    alr2.append((hn+h1[i],wn+w1[i]))
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int,input().split())
S = [list(input()) for i in range(H)]
blacklist = []
for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            blacklist.append((h,w))
count = 0
alr = []
h1 = [0,0,1,-1]
w1 = [1,-1,0,0]
for h,w in blacklist:
    que = deque()
    que.append((h,w,True))
    alr.append((h,w))
    alr2 = [(h,w)]
    while que:
        hn,wn,black = que.popleft()
        black = not black
        for i in range(4):
            if 0 <= hn+h1[i] <= H-1 and 0 <= wn+w1[i] <= W-1 and (hn+h1[i],wn+w1[i]) not in alr2:
                if (not black) and S[hn+h1[i]][wn+w1[i]] == '.':
                    if (hn+h1[i],wn+w1[i]) not in alr:
                        count += 1
                    que.append((hn+h1[i],wn+w1[i],black))
                    alr2.append((hn+h1[i],wn+w1[i]))
                elif black and S[hn+h1[i]][wn+w1[i]] == '#':
                    que.append((hn+h1[i],wn+w1[i],black))
                    alr2.append((hn+h1[i],wn+w1[i]))
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int,input().split())
S = [list(input()) for i in range(H)]
count = 0
alr = []
h1 = [0,0,1,-1]
w1 = [1,-1,0,0]
for h in range(H):
    for w in range(W):
        if S[h][w] == '#' and (h,w) not in alr:
            que = deque()
            que.append((h,w,True))
            alr.append((h,w))
            alr2 = [(h,w)]
            while que:
                hn,wn,black = que.popleft()
                black = not black
                for i in range(4):
                    if 0 <= hn+h1[i] <= H-1 and 0 <= wn+w1[i] <= W-1 and (hn+h1[i],wn+w1[i]) not in alr2:
                        if (not black) and S[hn+h1[i]][wn+w1[i]] == '.':
                            if (hn+h1[i],wn+w1[i]) not in alr:
                                count += 1
                            que.append((hn+h1[i],wn+w1[i],black))
                            alr2.append((hn+h1[i],wn+w1[i]))
                        elif black and S[hn+h1[i]][wn+w1[i]] == '#':

                            que.append((hn+h1[i],wn+w1[i],black))
                            alr2.append((hn+h1[i],wn+w1[i]))
print(count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.q = l
        heapq.heapify(self.q)
        return

    def push(self, n):
        heapq.heappush(self.q, n)
        return

    def pop(self):
        return heapq.heappop(self.q)


MOD = int(1e09) + 7
INF = int(1e15)


def main():
    # sys.stdin = open("sample.txt")
    H, W = Scanner.map_int()
    S = Scanner.string_list(H)

    def func(h, w):
        visited = [[False for _ in range(W)]for _ in range(H)]
        visited[h][w] = True
        q = []
        q.append((w, h))
        res = 0
        while q != []:
            x, y = q.pop()
            DIR = [(-1, 0), (1, 0), (0, -1), (0, 1)]
            for d in DIR:
                nx, ny = x + d[0], y + d[1]
                if not (0 <= nx < W):
                    continue
                if not(0 <= ny < H):
                    continue
                if visited[ny][nx]:
                    continue
                if S[ny][nx] == S[y][x]:
                    continue
                visited[ny][nx] = True
                if S[ny][nx] == '.':
                    res += 1
                q.append((nx, ny))
        return res

    ans = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                continue
            ans += func(h, w)
    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

V = {}
for i in range(H):
  for j in range(W):
    V[str(i) + "_" + str(j)] = []
    
for i in range(H):
  for j in range(W):
    
    for dy,dx in [(-1,0), (1,0), (0,-1), (0,1)]:
      y,x = i+dy, j+dx
      if y < 0 or H <= y or x < 0 or W <= x:
        continue
      if S[i][j] == S[y][x]:
        continue
      V[str(i) + "_" + str(j)].append([y,x])
      
ans = 0
visited = [[False for i in range(W)] for j in range(H)]
willsearch = [[False for i in range(W)] for j in range(H)]
Q = deque()
#print(V)
def dfs(y,x):
  wc, bc = 0, 0
  Q.append([y,x])
  while len(Q) > 0:
    b,a = Q.pop()
    #print("pop;", b, a, Q)
    visited[b][a] = True
    if S[b][a] == '.':
      wc += 1
    else:
      bc += 1
    for q,p in V[str(b) + "_" + str(a)]:
      #print("yeah:", q,p)
      if visited[q][p] or willsearch[q][p]:
        continue
      Q.append([q,p])
      willsearch[q][p] = True
    #print(b,a,"|",Q)
  #print(y,x,wc,bc)
  return wc*bc

for i in range(H):
  for j in range(W):
    ans += dfs(i,j)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W=map(int,input().split())
S=[input() for i in range(H)]
checked=[[0 for i in range(W)] for m in range(H)]

count=0
for h1 in range(H):
    for w1 in range(W):
        if S[h1][w1]=="#" and checked[h1][w1]==0:
            visited=[[0 for i in range(W)] for m in range(H)]
            checked[h1][w1]=1
            stack=deque([[h1,w1,"#"]])
            kuro=1
            siro=0
            while stack:
                h,w,iro=stack.popleft()
                for y,x in [[-1,0],[1,0],[0,1],[0,-1]]:
                    Y,X=y+h,x+w
                    if 0<=Y<H and 0<=X<W and visited[Y][X]==0:
                        if iro=="#" and S[Y][X]==".":
                            siro+=1
                            visited[Y][X]=1
                            stack.append([Y,X,"."])
                        elif iro=="." and S[Y][X]=="#" and checked[Y][X]==0:
                            kuro+=1
                            visited[Y][X]=1
                            checked[Y][X]=1
                            stack.append([Y,X,"#"])
            count+=kuro*siro
print(count)

Submission status: Time Limit Exceeded

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

sl = []

for _ in range(h):
    s = list(input())
    sl.append(s)

uf = UnionFind(h*w)
for i in range(h):
    for j in range(w):
        if j+1 < w:
            if sl[i][j] != sl[i][j+1]:
                uf.union(i*w+j, i*w+j+1)
        if i+1 < h:
            if sl[i][j] != sl[i+1][j]:
                uf.union(i * w + j, i * w + j + w)

ans = 0
for group in uf.all_group_members().values():
    a = 0
    b = 0
    for p in group:
        i = p // w
        j = p % w
        if sl[i][j] == "#":
            a += 1
        else:
            b += 1
    ans += a*b

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int, input().split())
M=[list(map(lambda x:1 if x=='#' else 0,input())) for _ in range(H)]

R=[[0 for _ in range(H*W+W)] for __ in range(H*W+W)]

#横1マス
for y in range(H):
    l=M[y]
    for x in range(W-1):
        if l[x]^l[x+1]:
            R[y*W+x][y*W+x+1]=1
            R[y*W+x+1][y*W+x]=1

#縦1マス
for x in range(W):
    for y in range(H-1):
        if M[y][x]^M[y+1][x]:
            R[y*W+x][(y+1)*W+x]=1
            R[(y+1)*W+x][y*W+x]=1

for z in range(H*W+W):
    for p in range(H*W+W):
        for q in range(H*W+W):
            if R[p][z] and R[q][z]:
                if R[p][q]&1: continue
                d=R[p][z]+R[q][z]
                R[p][q]=R[q][p]=d

ans=0
for p in range(H*W+W):
    for q in range(p+1,H*W+W):
        if R[p][q]&1: ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
checked = [[False for _ in range(w)] for _ in range(h)]
for h_i in range(h):
    for w_i in range(w):
      if maze[h_i][w_i] == ".":
        maze[h_i][w_i] = 0
      else:
        maze[h_i][w_i] = 1
      
def do_append(point, x_diff, y_diff):
  new_x = point[1] + x_diff
  new_y = point[0] + y_diff
  new_color = ((point[2]+1)%2)
  if new_x == -1 or new_x == w or new_y == -1 or new_y == h or new_color != maze[new_y][new_x]:
    return False, False
  elif checked[new_y][new_x] == True:
    return False, False
    
  else:
    return True, (new_y, new_x, new_color)

def wfs(pos):
  count = 0
  y_pos = pos[0]
  x_pos = pos[1]
  color = 0 # 0 white 1 black
  
  que = collections.deque()
  que.append((y_pos, x_pos, color))
  checked[y_pos][x_pos] = True
  while len(que) > 0:
    point = que.popleft()
    result, new_point = do_append(point, 1, 0)
    if result:
      checked[new_point[0]][new_point[1]] = True
      que.append(new_point)
      if new_point[2] == 1:
        count += 1
    result, new_point = do_append(point, -1, 0)
    if result:
      checked[new_point[0]][new_point[1]] = True
      que.append(new_point)
      if new_point[2] == 1:
        count += 1
    
    result, new_point = do_append(point, 0, 1)
    if result:
      checked[new_point[0]][new_point[1]] = True
      que.append(new_point)
      if new_point[2] == 1:
        count += 1
        
    result, new_point = do_append(point, 0, -1)
    if result:
      checked[new_point[0]][new_point[1]] = True
      que.append(new_point)
      if new_point[2] == 1:
        count += 1
    
  return count
if __name__ == "__main__":
  count = 0
  for h_i in range(h):
    for w_i in range(w):
      if maze[h_i][w_i] == 0:
        checked = [[False for _ in range(w)] for _ in range(h)]
        pos = (h_i, w_i)
        count += wfs(pos)
  print(count)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
lis = [str(input()) for i in range(h)]
ans = 0
ch = [[0] * w for i in range(h)]

def firstcheck(x,y):
    if lis[x][y] != "#" or ch[x][y] != 0:
        return False
    if x > 0:
        if lis[x-1][y] == ".":
            return True
    if x < h-1:
        if lis[x+1][y] == ".":
            return True
    if y > 0:
        if lis[x][y-1] == ".":
            return True
    if y < w-1:
        if lis[x][y+1] == ".":
            return True
    return False

for sx in range(h):
    for sy in range(w):
        if firstcheck(sx,sy):
            cnt = 1
            nu = 0
            ch[sx][sy] = 1
            num = [[0] * w for i in range(h)]
            now = {(sx,sy,1)}
            while now != set():
                tmp = set()
                for x,y,iro in now:
                    if x > 0:
                        if lis[x-1][y] != lis[x][y] and num[x-1][y] == 0:
                            nu += iro
                            tmp.add((x-1,y,(iro+1)%2))
                            num[x-1][y] = 1
                            if lis[x-1][y] == "#" and ch[x-1][y] == 0:
                                cnt += 1
                                ch[x-1][y] = 1
                    if x < h-1:
                        if lis[x+1][y] != lis[x][y] and num[x+1][y] == 0:
                            nu += iro
                            tmp.add((x+1,y,(iro+1)%2))
                            num[x+1][y] = 1
                            if lis[x+1][y] == "#" and ch[x+1][y] == 0:
                                cnt += 1
                                ch[x+1][y] = 1
                    if y > 0:
                        if lis[x][y-1] != lis[x][y] and num[x][y-1] == 0:
                            nu += iro
                            tmp.add((x,y-1,(iro+1)%2))
                            num[x][y-1] = 1
                            if lis[x][y-1] == "#" and ch[x][y-1] == 0:
                                cnt += 1
                                ch[x][y-1] = 1
                    if y < w-1:
                        if lis[x][y+1] != lis[x][y] and num[x][y+1] == 0:
                            nu += iro
                            tmp.add((x,y+1,(iro+1)%2))
                            num[x][y+1] = 1
                            if lis[x][y+1] == "#" and ch[x][y+1] == 0:
                                cnt += 1
                                ch[x][y+1] = 1
                now = tmp
            ans += nu * cnt
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
lis = [str(input()) for i in range(h)]
ans = 0
ch = [[0] * w for i in range(h)]

def firstcheck(x,y):
    if lis[x][y] != "#" or ch[x][y] != 0:
        return False
    if x > 0:
        if lis[x-1][y] == ".":
            return True
    if x < h-1:
        if lis[x+1][y] == ".":
            return True
    if y > 0:
        if lis[x][y-1] == ".":
            return True
    if y < w-1:
        if lis[x][y+1] == ".":
            return True
    return False

for sx in range(h):
    for sy in range(w):
        if firstcheck(sx,sy):
            cnt = 1
            nu = 0
            ch[sx][sy] = 1
            num = [[0] * w for i in range(h)]
            now = {(sx,sy,1)}
            while len(now) != 0:
                tmp = set()
                for x,y,iro in now:
                    if x > 0:
                        if lis[x-1][y] != lis[x][y] and num[x-1][y] == 0:
                            nu += iro
                            tmp.add((x-1,y,(iro+1)%2))
                            num[x-1][y] = 1
                            if lis[x-1][y] == "#" and ch[x-1][y] == 0:
                                cnt += 1
                                ch[x-1][y] = 1
                    if x < h-1:
                        if lis[x+1][y] != lis[x][y] and num[x+1][y] == 0:
                            nu += iro
                            tmp.add((x+1,y,(iro+1)%2))
                            num[x+1][y] = 1
                            if lis[x+1][y] == "#" and ch[x+1][y] == 0:
                                cnt += 1
                                ch[x+1][y] = 1
                    if y > 0:
                        if lis[x][y-1] != lis[x][y] and num[x][y-1] == 0:
                            nu += iro
                            tmp.add((x,y-1,(iro+1)%2))
                            num[x][y-1] = 1
                            if lis[x][y-1] == "#" and ch[x][y-1] == 0:
                                cnt += 1
                                ch[x][y-1] = 1
                    if y < w-1:
                        if lis[x][y+1] != lis[x][y] and num[x][y+1] == 0:
                            nu += iro
                            tmp.add((x,y+1,(iro+1)%2))
                            num[x][y+1] = 1
                            if lis[x][y+1] == "#" and ch[x][y+1] == 0:
                                cnt += 1
                                ch[x][y+1] = 1
                now = tmp
            ans += nu * cnt
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
lis = [str(input()) for i in range(h)]
ans = 0
ch = [[0] * w for i in range(h)]
for sx in range(h):
    for sy in range(w):
        if lis[sx][sy] == "#" and ch[sx][sy] == 0:
            cnt = 1
            nu = 0
            ch[sx][sy] = 1
            num = [[0] * w for i in range(h)]
            now = {(sx,sy,1)}
            while len(now) != 0:
                tmp = set()
                for x,y,iro in now:
                    if x > 0:
                        if lis[x-1][y] != lis[x][y] and num[x-1][y] == 0:
                            nu += iro
                            tmp.add((x-1,y,(iro+1)%2))
                            num[x-1][y] = 1
                            if lis[x-1][y] == "#" and ch[x-1][y] == 0:
                                cnt += 1
                                ch[x-1][y] = 1
                    if x < h-1:
                        if lis[x+1][y] != lis[x][y] and num[x+1][y] == 0:
                            nu += iro
                            tmp.add((x+1,y,(iro+1)%2))
                            num[x+1][y] = 1
                            if lis[x+1][y] == "#" and ch[x+1][y] == 0:
                                cnt += 1
                                ch[x+1][y] = 1
                    if y > 0:
                        if lis[x][y-1] != lis[x][y] and num[x][y-1] == 0:
                            nu += iro
                            tmp.add((x,y-1,(iro+1)%2))
                            num[x][y-1] = 1
                            if lis[x][y-1] == "#" and ch[x][y-1] == 0:
                                cnt += 1
                                ch[x][y-1] = 1
                    if y < w-1:
                        if lis[x][y+1] != lis[x][y] and num[x][y+1] == 0:
                            nu += iro
                            tmp.add((x,y+1,(iro+1)%2))
                            num[x][y+1] = 1
                            if lis[x][y+1] == "#" and ch[x][y+1] == 0:
                                cnt += 1
                                ch[x][y+1] = 1
                now = tmp
            ans += nu * cnt
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
lis = [str(input()) for i in range(h)]
ans = 0
for sx in range(h):
    for sy in range(w):
        if lis[sx][sy] == "#":
            num = [[0] * w for i in range(h)]
            now = {(sx,sy,1)}
            while len(now) != 0:
                tmp = set()
                for x,y,iro in now:
                    if x > 0:
                        if lis[x-1][y] != lis[x][y] and num[x-1][y] == 0:
                            ans += iro
                            tmp.add((x-1,y,(iro+1)%2))
                            num[x-1][y] = 1
                    if x < h-1:
                        if lis[x+1][y] != lis[x][y] and num[x+1][y] == 0:
                            ans += iro
                            tmp.add((x+1,y,(iro+1)%2))
                            num[x+1][y] = 1
                    if y > 0:
                        if lis[x][y-1] != lis[x][y] and num[x][y-1] == 0:
                            ans += iro
                            tmp.add((x,y-1,(iro+1)%2))
                            num[x][y-1] = 1
                    if y < w-1:
                        if lis[x][y+1] != lis[x][y] and num[x][y+1] == 0:
                            ans += iro
                            tmp.add((x,y+1,(iro+1)%2))
                            num[x][y+1] = 1
                now = tmp

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
lis = [str(input()) for i in range(h)]
ans = 0
for sx in range(h):
    for sy in range(w):
        if lis[sx][sy] == "#":
            num = [[0] * w for i in range(h)]
            now = {(sx,sy,1)}
            for _ in range(1600):
                tmp = set()
                for x,y,iro in now:
                    if x > 0:
                        if lis[x-1][y] != lis[x][y] and num[x-1][y] == 0:
                            ans += iro
                            tmp.add((x-1,y,(iro+1)%2))
                            num[x-1][y] = 1
                    if x < h-1:
                        if lis[x+1][y] != lis[x][y] and num[x+1][y] == 0:
                            ans += iro
                            tmp.add((x+1,y,(iro+1)%2))
                            num[x+1][y] = 1
                    if y > 0:
                        if lis[x][y-1] != lis[x][y] and num[x][y-1] == 0:
                            ans += iro
                            tmp.add((x,y-1,(iro+1)%2))
                            num[x][y-1] = 1
                    if y < w-1:
                        if lis[x][y+1] != lis[x][y] and num[x][y+1] == 0:
                            ans += iro
                            tmp.add((x,y+1,(iro+1)%2))
                            num[x][y+1] = 1
                now = tmp

print(ans)

Submission status: Time Limit Exceeded

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


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


def main():
    H, W = map(int, input().split())
    S = []
    for h in range(H):
        S.append(input().strip())

    uf = UnionFind(H*W)
    for i in range(H):
        for j in range(W):
            if i < H-1 and S[i][j] != S[i+1][j]:
                uf.union(i*W+j, (i+1)*W+j)
            if j < W-1 and S[i][j] != S[i][j+1]:
                uf.union(i*W+j, i*W+(j+1))
    ans = 0
    for ms in uf.all_group_members().values():
        b = w = 0
        for m in ms:
            if S[m // W][m % W] == "#":
                b += 1
            else:
                w += 1
        ans += b*w
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


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


def main():
    H, W = map(int, input().split())
    S = []
    for h in range(H):
        S.append(input().strip())

    uf = UnionFind(H*W)
    for i in range(H):
        for j in range(W):
            if i > 0 and S[i][j] != S[i-1][j]:
                uf.union(i*W+j, (i-1)*W+j)
            if i < H-1 and S[i][j] != S[i+1][j]:
                uf.union(i*W+j, (i+1)*W+j)
            if j > 0 and S[i][j] != S[i][j-1]:
                uf.union(i*W+j, i*W+(j-1))
            if j < W-1 and S[i][j] != S[i][j+1]:
                uf.union(i*W+j, i*W+(j+1))
    ans = 0
    for u in uf.roots():
        b = 0
        w = 0
        for m in uf.members(u):
            i = m // W
            j = m % W
            if S[i][j] == "#":
                b += 1
            else:
                w += 1
        ans += b*w
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(si,sj):
  if S[sj][si] != '#':return 0
  
  q = deque()
  q.append([si,sj,1])
  ans = 0
  used = set([si,sj])
  ini_col = S[sj][si]
  while len(q)>0:
    prvi, prvj,prvcnt = q.popleft()
    for i,j in [[prvi+1,prvj],[prvi-1,prvj],[prvi,prvj+1],[prvi,prvj-1]]:
      if (i,j) in used:continue
      elif (prvcnt%2==0 and S[j][i] == ini_col) or (prvcnt%2==1 and S[j][i] not in [ini_col,'-']):
          q.append([i,j,prvcnt+1])
          used.add((i,j))
            
          if S[j][i] == '.':
            ans += 1
  return ans    

H,W = map(int,input().split())
S = [['-' for _ in range(W+2)]] + [['-'] + [s for s in input()] + ['-'] for _ in range(H)] + [['-' for _ in range(W+2)]]
ans = 0
used = set([])
for i in range(1,W+1):
  for j in range(1,H+1):
    ans += bfs(i,j)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(si,sj):
  if S[sj][si] != '#':return 0
  
  q = deque()
  q.append([si,sj,1])
  ans = 0
  used = set([si,sj,1])
  ini_col = S[sj][si]
  while len(q)>0:
    prvi, prvj,prvcnt = q.popleft()
    for i,j in [[prvi+1,prvj],[prvi-1,prvj],[prvi,prvj+1],[prvi,prvj-1]]:
      if (i,j) in used:continue
      elif (prvcnt%2==0 and S[j][i] == ini_col) or (prvcnt%2==1 and S[j][i] not in [ini_col,'-']):
          q.append([i,j,prvcnt+1])
          used.add((i,j))
            
          if S[j][i] == '.':
            ans += 1
  return ans    

H,W = map(int,input().split())
S = [['-' for _ in range(W+2)]] + [['-'] + [s for s in input()] + ['-'] for _ in range(H)] + [['-' for _ in range(W+2)]]
ans = 0
for i in range(1,W+1):
  for j in range(1,H+1):
    ans += bfs(i,j)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
grid = [[1 if i == "#" else 0 for i in input()] for _ in range(h)]
seen = [[0] * w for _ in range(h)]
DX = (0, 1, 0, -1)
DY = (1, 0, -1, 0)
ans = 0


def white(X, Y, cnt):
    todo = [(X, Y)]
    seen[X][Y] = cnt
    res = 0
    while todo:
        x, y = todo.pop()
        now = grid[x][y]
        for dx, dy in zip(DX, DY):
            nx = x + dx
            ny = y + dy
            if nx < 0 or ny < 0 or nx >= h or ny >= w:  # インデックスが範囲外ならだめ
                continue
            if seen[nx][ny] == cnt or now == grid[nx][ny]:  # 既に見ていたり、白-白、黒-黒ならばだめ
                continue
            if 1-now:  # 現在位置が白色の場合
                res += 1
            seen[nx][ny] = cnt
            todo.append((nx, ny))
    return res


cnt = 1
for i in range(h):
    for j in range(w):
        if grid[i][j] == 1:
            continue
        ans += white(i, j, cnt)
        cnt += 1

print(ans)