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:
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
MOD = 10**9+7

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

S = [list(input()) for i in range(H)]

dx = [1,-1,0,0]
dy = [0,0,1,-1]

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

def distance(i,j):
    not_visited = [[-1]*W for i in range(H)]
    not_visited[i][j] = 0
    stack = deque()
    stack.append((i,j,"#"))

    while stack != deque([]):
        y,x,mark = stack.popleft()
        for i in range(4):
            if 0<= x+dx[i] <W and 0<= y+dy[i] <H and mark != S[y+dy[i]][x+dx[i]]  and not_visited[y+dy[i]][x+dx[i]] == -1:
                not_visited[y+dy[i]][x+dx[i]] =  not_visited[y][x] + 1
                if mark == "#":
                    stack.append((y+dy[i],x+dx[i],"."))
                else:
                    stack.append((y+dy[i],x+dx[i],"#"))

    odd = 0
    for i in range(H):
        for j in range(W):
            if not_visited[i][j] > 0 and not_visited[i][j] % 2 == 1:
                odd += 1
    
    return odd

ans = 0
if start:
    for sta in start:
        i,j = sta[0],sta[1]
        ans += distance(i,j)
    print(ans)
else:
    print(ans)

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

dx = [1,-1,0,0]
dy = [0,0,1,-1]

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

def distance(i,j):
    not_visited = [[-1]*W for i in range(H)]
    not_visited[i][j] = 0
    stack = deque()
    stack.append((i,j,"#"))

    while stack != deque([]):
        y,x,mark = stack.popleft()
        for i in range(4):
            if 0<= x+dx[i] <W and 0<= y+dy[i] <H and mark != S[y+dy[i]][x+dx[i]]  and not_visited[y+dy[i]][x+dx[i]] == -1:
                not_visited[y+dy[i]][x+dx[i]] =  not_visited[y][x] + 1
                if mark == "#":
                    stack.append((y+dy[i],x+dx[i],"."))
                else:
                    stack.append((y+dy[i],x+dx[i],"#"))

    odd = 0
    for i in range(H):
        for j in range(W):
            if not_visited[i][j] > 0 and not_visited[i][j] % 2 == 1:
                odd += 1
    
    return odd

ans = 0
if start:
    for sta in start:
        i,j = sta[0],sta[1]
        ans += distance(i,j)
    print(ans)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

start_black = [[False]*W for _ in range(H)]
bl = []
for row in range(H):
    for col in range(W):
        if s[row][col] == "#":
            start_black[row][col] = True
            bl.append([row, col])

ans = 0
for b in bl:
    if start_black[b[0]][b[1]]:
        d = deque([[b[0], b[1]]])
        passed_black = 1
        passed_white = 0
        visited = [[False]*W for _ in range(H)]
        visited[b[0]][b[1]] = True
        while d:
            b_row, b_col = d.popleft()
            for new_row, new_col in [[b_row+1, b_col], [b_row-1, b_col], [b_row, b_col+1], [b_row, b_col-1]]:
                if 0 <= new_row <= H-1 and 0 <= new_col <= W-1 and s[b_row][b_col] != s[new_row][new_col] and not visited[new_row][new_col]:
                    start_black[new_row][new_col] = False
                    d.append([new_row, new_col])
                    visited[new_row][new_col] = True
                    if s[new_row][new_col] == ".":
                        passed_white += 1
                    else:
                        passed_black += 1
        ans += passed_black * passed_white

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


class UnionFind:
    # 初期化
    def __init__(self, n_nodes):
        self.n_nodes = n_nodes
        # 親要素のノード番号を格納する.初めは全て親ノード.
        # self.parent[x] == x の時，そのノードは根.
        self.parent = [i for i in range(n_nodes)]
        # 木の高さを格納する．
        self.rank = [1] * n_nodes
        # 自分と同じグループの要素数を格納．親要素を参照するようにする
        self.size = [1] * n_nodes

    # 検索. 根を返す.
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            # 一度調べた値は，根に繋ぎ直す.
            self.parent[x] = self.find(self.parent[x])
            return 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[y] = x
            self.size[x] += self.size[y]
        else:
            self.parent[x] = y
            self.size[y] += self.size[x]
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    # 同じ集合に属するか判定
    def check(self, x, y):
        return self.find(x) == self.find(y)

    # 同一グループに所属する要素数を返す
    def get_size(self, x):
        return self.size[self.find(x)]

    # 親要素のリストを返す
    def get_parent_list(self):
        return [i for i in range(self.n_nodes) if self.find(i) == i]

    # グループの数を返す
    def get_n_groups(self):
        return len(self.get_parent_list())

    # 同じグループに所属する要素の集合を返す
    def get_members(self, x):
        parent = self.find(x)
        return [i for i in range(self.n_nodes) if self.find(i) == parent]

    # 全ての根に対する，グループのメンバーを返す．
    def get_members_dict(self):
        return {par: self.get_members(par) for par in self.get_parent_list()}


def main():
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    UF = UnionFind(H * W)
    for h in range(H):
        for w in range(W):
            if S[h][w] == "#":
                for x, y in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
                    if 0 <= h + x < H and 0 <= w + y < W:
                        if S[h + x][w + y] == ".":
                            UF.unite(h * W + w, (h + x) * W + w + y)
    members = UF.get_members_dict()
    parent = UF.get_parent_list()
    answer = 0
    for p in parent:
        member = members[p]
        black = 0
        white = 0
        for m in member:
            w = m % W
            h = m // W
            if S[h][w] == "#":
                black += 1
            else:
                white += 1
        answer += black * white
    print(answer)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

    black = []
    for h in range(H):
        for w in range(W):
            if S[h][w] == "#":
                black.append((h, w))

    ans = 0
    for sh, sw in black:
        visited = [[0] * W for _ in range(H)]
        q = deque([("#", sh, sw)])

        while q:
            s, h, w = q.popleft()

            for dh, dw in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                nh = h + dh
                nw = w + dw
                if 0 <= nh < H and 0 <= nw < W:
                    if visited[nh][nw] == 0:
                        if s == S[nh][nw]:
                            continue
                        else:
                            if S[nh][nw] == ".":
                                ans += 1
                            visited[nh][nw] = 1
                            q.append((S[nh][nw], nh, nw))

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]
dij=[(1,0),(0,1),(-1,0),(0,-1)]

def main():
    h,w=MI()
    ss=[SI() for _ in range(h)]

    def dfs(i,j):
        bc=ss[i][j]=="#"
        wc=ss[i][j]=="."
        for di,dj in dij:
            ni,nj=i+di,j+dj
            if ni<0 or nj<0 or ni>=h or nj>=w:continue
            if fin[ni][nj] or ss[i][j]==ss[ni][nj]:continue
            fin[ni][nj]=True
            ret=dfs(ni,nj)
            bc+=ret[0]
            wc+=ret[1]
        return bc,wc

    ans=0
    fin=[[False]*w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if fin[i][j] or ss[i][j]==".":continue
            fin[i][j]=True
            bc,wc=dfs(i,j)
            ans+=bc*wc
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    H, W = map(int, input().split())
    S = list(list(input()) for _ in range(H))
    visited_black = [[False] * W for _ in range(H)]
    blacks = []
    ans = 0
    dh = [0,1,0,-1]
    dw = [1,0,-1,0]
    for h in range(H):
        for w in range(W):
            if S[h][w] == '#':
                blacks.append((h,w))

    for h, w in blacks:
        if not visited_black[h][w]:
            visited_white = [[False] * W for _ in range(H)]
            Q = deque([(h,w)])
            white = 0
            black = 1
            visited_black[h][w] = True
            while Q:
                i, j = Q.popleft()
                now = S[i][j]

                for n in range(4):
                    nh = i + dh[n]
                    nw = j + dw[n]

                    if not (0 <= nh < H and 0 <= nw < W):
                        continue
                    if now == '#':
                        if S[nh][nw] == '.' and (not visited_white[nh][nw]):
                            white += 1
                            visited_white[nh][nw] = True
                            Q.append((nh,nw))
                    else:
                        if S[nh][nw] == '#' and (not visited_black[nh][nw]):
                            black += 1
                            visited_black[nh][nw] = True
                            Q.append((nh,nw))
            ans += white * black

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    H, W = map(int, input().split())
    S = list(list(input()) for _ in range(H))
    visited_black = [[False] * W for _ in range(H)]
    blacks = []
    ans = 0
    dh = [0,1,0,-1]
    dw = [1,0,-1,0]
    for h in range(H):
        for w in range(W):
            if S[h][w] == '#':
                blacks.append([h,w])

    for h, w in blacks:
        if not visited_black[h][w]:
            visited_white = [[False] * W for _ in range(H)]
            Q = deque([[h,w]])
            white = 0
            black = 1
            visited_black[h][w] = True
            while Q:
                i, j = Q.popleft()
                now = S[i][j]

                for n in range(4):
                    nh = i + dh[n]
                    nw = j + dw[n]

                    if not (0 <= nh < H and 0 <= nw < W):
                        continue
                    if now == '#':
                        if S[nh][nw] == '.' and (not visited_white[nh][nw]):
                            white += 1
                            visited_white[nh][nw] = True
                            Q.append([nh,nw])
                    else:
                        if S[nh][nw] == '#' and (not visited_black[nh][nw]):
                            black += 1
                            visited_black[nh][nw] = True
                            Q.append([nh,nw])
            ans += white * black

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    H, W = map(int, input().split())
    S = list(input() for _ in range(H))
    visited_black = [[False] * W for _ in range(H)]
    ans = 0
    dh = [0,1,0,-1]
    dw = [1,0,-1,0]
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                continue
            if S[h][w] == '#' and visited_black[h][w]:
                continue
            visited_white = [[False] * W for _ in range(H)]
            Q = deque([[h,w]])
            white = 0
            black = 1
            visited_black[h][w] = True
            while Q:
                i, j = Q.popleft()
                now = S[i][j]

                for n in range(4):
                    nh = i + dh[n]
                    nw = j + dw[n]

                    if not (0 <= nh < H and 0 <= nw < W):
                        continue
                    if now == '#':
                        if S[nh][nw] == '.' and (not visited_white[nh][nw]):
                            white += 1
                            visited_white[nh][nw] = True
                            Q.append([nh,nw])
                    else:
                        if S[nh][nw] == '#' and (not visited_black[nh][nw]):
                            black += 1
                            visited_black[nh][nw] = True
                            Q.append([nh,nw])
            ans += white * black

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)
H,W=map(int,input().split())
S=[]
for i in range(H):
    S.append(input())

ans=0
dx=[0,0,1,-1]
dy=[1,-1,0,0]

was=[[0 for i in range(W)] for j in range(H)]

def dfs(x,y):
    global cc
    global was
    was[x][y]=1
    if S[x][y]=="#":
        cc[1]+=1
    else:
        cc[0]+=1
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if nx>=0 and ny>=0 and nx<H and ny<W and S[nx][ny]!=S[x][y] and not was[nx][ny]:
            dfs(nx,ny)

for i in range(H):
    for j in range(W):
        if not was[i][j]:
            cc=[0]*2
            dfs(i,j)
            ans+= cc[1]*cc[0]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)

h,w= map(int, input().split())
maze = [[-1 for i in range(w)] for j in range(h)]

ans = 0
for i in range(h):
    maze[i] = input()

ans = 0

from collections import defaultdict
memo = defaultdict(list)

for sy in range(h):
    for sx in range(w):
        if maze[sy][sx] == '.':
            continue
        else:
            visited = [[-1 for i in range(w)] for j in range(h)]

        queue = deque()
        queue.appendleft((sy, sx))
        visited[sy][sx] = 0
        while len(queue):
            y, x = queue.pop()
            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                if 0 <= nx < w and 0 <= ny < h:
                    if maze[ny][nx] != maze[y][x] and visited[ny][nx] == -1:
                        queue.appendleft((ny, nx))
                        visited[ny][nx] = 1
                        if memo[(ny,nx)]:
                            tmp = memo[(sy,sx)] + memo[(ny,nx)]
                            memo[(sy,sx)] = list(set(tmp))
                            for yy,xx in memo[(ny,nx)]:
                                visited[yy][xx]=1
                        elif maze[ny][nx]=='.':
                                memo[(sy,sx)].append((ny,nx))

        tmp = memo[(sy,sx)]
        ans += len(set(tmp))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)

h,w= map(int, input().split())
maze = [[-1 for i in range(w)] for j in range(h)]

ans = 0
for i in range(h):
    maze[i] = input()

ans = 0

from collections import defaultdict
memo = defaultdict(list)

for sy in range(h):
    for sx in range(w):
        if maze[sy][sx] == '.':
            continue
        else:
            visited = [[-1 for i in range(w)] for j in range(h)]

        queue = deque()
        queue.appendleft((sy, sx))
        visited[sy][sx] = 0
        while len(queue):
            y, x = queue.pop()
            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                if 0 <= nx < w and 0 <= ny < h:
                    if maze[ny][nx] != maze[y][x] and visited[ny][nx] == -1:
                        queue.appendleft((ny, nx))
                        visited[ny][nx] = 1
                        if memo[(ny,nx)]:
                            tmp = memo[(sy,sx)] + memo[(ny,nx)]
                            memo[(sy,sx)] = list(set(tmp))
                        elif maze[ny][nx]=='.':
                                memo[(sy,sx)].append((ny,nx))

        tmp = memo[(sy,sx)]
        ans += len(set(tmp))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)

h,w= map(int, input().split())
maze = [[-1 for i in range(w)] for j in range(h)]

ans = 0
for i in range(h):
    maze[i] = input()

ans = 0

from collections import defaultdict
memo = defaultdict(list)

for sy in range(h):
    for sx in range(w):
        if maze[sy][sx] == '.':
            continue
        else:
            visited = [[-1 for i in range(w)] for j in range(h)]

        queue = deque()
        queue.appendleft((sy, sx))
        visited[sy][sx] = 0
        while len(queue):
            y, x = queue.pop()
            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                if 0 <= nx < w and 0 <= ny < h:
                    if maze[ny][nx] != maze[y][x] and visited[ny][nx] == -1:
                        queue.appendleft((ny, nx))
                        visited[ny][nx] = 1
                        if maze[ny][nx]=='.':
                            memo[(sy,sx)].append((ny,nx))
                        else:
                            if memo[(ny,nx)]:
                                tmp = memo[(sy,sx)] + memo[(ny,nx)]
                                memo[(sy,sx)] = list(set(tmp))

        tmp = memo[(sy,sx)]
        ans += len(set(tmp))

print(ans)

Submission status: Time Limit Exceeded

Solution code:

from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)

h,w= map(int, input().split())
maze = [[-1 for i in range(w)] for j in range(h)]

ans = 0
for i in range(h):
    maze[i] = input()

ans = 0

from collections import defaultdict
memo = defaultdict(list)

for sy in range(h):
    for sx in range(w):
        if maze[sy][sx] == '.':
            continue
        else:
            visited = [[-1 for i in range(w)] for j in range(h)]

        queue = deque()
        froq = deque()
        queue.appendleft((sy, sx))
        visited[sy][sx] = 0
        while len(queue):
            y, x = queue.pop()
            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                if 0 <= nx < w and 0 <= ny < h:
                    if maze[ny][nx] != maze[y][x] and visited[ny][nx] == -1:
                        queue.appendleft((ny, nx))
                        visited[ny][nx] = 1
                        if maze[ny][nx]=='.':
                            memo[(sy,sx)].append((ny,nx))
                        else:
                            if memo[(ny,nx)]:
                                memo[(sy,sx)].extend((memo[(ny,nx)]))

        tmp = memo[(sy,sx)]
        ans += len(set(tmp))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)
import numpy as np

h,w= map(int, input().split())
maze = [[-1 for i in range(w)] for j in range(h)]

ans = 0
for i in range(h):
    maze[i] = input()

INF = 10000
ans = 0


for sy in range(h):
    for sx in range(w):
        if maze[sy][sx] == '.':
            continue
        else:
            visited = [[-1 for i in range(w)] for j in range(h)]

        queue = deque()
        queue.appendleft((sy, sx))
        visited[sy][sx] = 0
        while len(queue):
            y, x = queue.pop()
            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                if 0 <= nx < w and 0 <= ny < h:
                    if maze[ny][nx] != maze[y][x] and visited[ny][nx] == -1:
                        queue.appendleft((ny, nx))
                        visited[ny][nx] = 1
                        if maze[ny][nx]=='.': ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
s_list = []
for _ in range(H):
    s = input()
    s_list.append(s)
ans = 0
for h in range(H):
    for w in range(W):
        if s_list[h][w] == '.':
            d = deque()
            d.append([h, w])
            visited = set({})
            while d:
                i, j = d.pop()
                visited.add(str(i) + '_' + str(j))
                for ii, jj in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                    if (0 <= (i + ii) < H) & (0 <= (j + jj) < W):
                        if str(i + ii) + '_' + str(j + jj) not in visited:
                            if s_list[i][j] != s_list[i + ii][j + jj]:
                                d.append([i + ii, j + jj])
                                if s_list[i + ii][j + jj] == '#':                                    
                                    ans += 1
                            visited.add(str(i + ii) + '_' + str(j + jj))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
class UnionFind():
    def __init__(self, n):
        self.n=n
        self.parents=[-1]*n # 親(uf.find()で経路圧縮して根)の番号。根の場合は-(そのグループの要素数)
    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 unite(self,x,y):
        #要素x,yのグループを併合
        x,y=self.find(x),self.find(y)
        if x==y:return
        if self.parents[x]>self.parents[y]:#要素数の大きい方をxに
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x #要素数が大きい方に併合
    def size(self,x):
        #xが属するグループの要素数
        return -self.parents[self.find(x)]
    def same(self,x,y):
        #xとyが同じグループ？
        return self.find(x)==self.find(y)
    def members(self,x):
        #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 all_group_members_list(self):
        #各ルート要素のグループに含まれる要素のリストのリスト
        #[[0, 2], [1, 3, 4, 5]]
        return list(self.all_group_members().values())
    def __str__(self):
        #各ルート要素のグループに含まれる要素のリストをprint()
        return '\n'.join('{}: {}'.format(r,self.members(r)) for r in self.roots())
def main():
    h,w=map(int,input().split())
    S=[input() for _ in range(h)]
    uf=UnionFind(h*w)
    for i in range(h):
        for j in range(w):
            ss=S[i][j]
            for row,col in ((1,0),(-1,0),(0,1),(0,-1)):
                if i+row>=0 and i+row<h and j+col>=0 and j+col<w and ss!=S[i+row][j+col]:
                    uf.unite((i+row)*w+j+col,i*w+j) 
    ans=0
    for par in uf.all_group_members_list():
        cunt_b=0
        cunt_w=0
        for x in par:
            col=x%w
            row=x//w
            if S[row][col]=="#":cunt_b+=1
            else:cunt_w+=1
        ans+=cunt_b*cunt_w
    print(ans)
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
class UnionFind():
    def __init__(self, n):
        self.n=n
        self.parents=[-1]*n # 親(uf.find()で経路圧縮して根)の番号。根の場合は-(そのグループの要素数)
    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 unite(self,x,y):
        #要素x,yのグループを併合
        x,y=self.find(x),self.find(y)
        if x==y:return
        if self.parents[x]>self.parents[y]:#要素数の大きい方をxに
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x #要素数が大きい方に併合
    def size(self,x):
        #xが属するグループの要素数
        return -self.parents[self.find(x)]
    def same(self,x,y):
        #xとyが同じグループ？
        return self.find(x)==self.find(y)
    def members(self,x):
        #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 all_group_members_list(self):
        #各ルート要素のグループに含まれる要素のリストのリスト
        #[[0, 2], [1, 3, 4, 5]]
        return list(self.all_group_members().values())
    def __str__(self):
        #各ルート要素のグループに含まれる要素のリストをprint()
        return '\n'.join('{}: {}'.format(r,self.members(r)) for r in self.roots())

class UnionFindLabel(UnionFind):
    def __init__(self, labels):
        assert len(labels)==len(set(labels))
        self.n=len(labels)
        self.parents=[-1]*self.n
        self.d={x: i for i,x in enumerate(labels)}
        self.d_inv={i: x for i,x in enumerate(labels)}
    def find_label(self,x):
        return self.d_inv[super().find(self.d[x])]
    def unite(self,x,y):
        super().unite(self.d[x],self.d[y])
    def size(self,x):
        return super().size(self.d[x])
    def same(self,x,y):
        return super().same(self.d[x],self.d[y])
    def members(self,x):
        root=self.find(self.d[x])
        return [self.d_inv[i] for i in range(self.n) if self.find(i)==root]
    def roots(self):
        return [self.d_inv[i] for i,x in enumerate(self.parents) if x<0]

def main():
    h,w=map(int,input().split())
    S=[input() for _ in range(h)]
    lis=[(i,j) for j in range(w) for i in range(h)]
    uf=UnionFindLabel(lis)
    for i in range(h):
        for j in range(w):
            ss=S[i][j]
            if i-1>=0 and S[i-1][j]!=ss:uf.unite((i,j),(i-1,j))
            if i+1<h and S[i+1][j]!=ss:uf.unite((i,j),(i+1,j))
            if j-1>=0 and S[i][j-1]!=ss:uf.unite((i,j),(i,j-1))
            if j+1<w and S[i][j+1]!=ss:uf.unite((i,j),(i,j+1))
    ans=0
    for ll in uf.all_group_members_list():
        cunt_b=0
        cunt_w=0
        for r,l in ll:
            if S[r][l]=="#":cunt_b+=1
            else:cunt_w+=1
        ans+=cunt_b*cunt_w
    print(ans)
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
class UnionFind():
    def __init__(self, n):
        self.n=n
        self.parents=[-1]*n # 親(uf.find()で経路圧縮して根)の番号。根の場合は-(そのグループの要素数)
    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 unite(self,x,y):
        #要素x,yのグループを併合
        x,y=self.find(x),self.find(y)
        if x==y:return
        if self.parents[x]>self.parents[y]:#要素数の大きい方をxに
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x #要素数が大きい方に併合
    def size(self,x):
        #xが属するグループの要素数
        return -self.parents[self.find(x)]
    def same(self,x,y):
        #xとyが同じグループ？
        return self.find(x)==self.find(y)
    def members(self,x):
        #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 all_group_members_list(self):
        #各ルート要素のグループに含まれる要素のリストのリスト
        #[[0, 2], [1, 3, 4, 5]]
        return list(self.all_group_members().values())
    def __str__(self):
        #各ルート要素のグループに含まれる要素のリストをprint()
        return '\n'.join('{}: {}'.format(r,self.members(r)) for r in self.roots())

class UnionFindLabel(UnionFind):
    def __init__(self, labels):
        assert len(labels)==len(set(labels))
        self.n=len(labels)
        self.parents=[-1]*self.n
        self.d={x: i for i,x in enumerate(labels)}
        self.d_inv={i: x for i,x in enumerate(labels)}
    def find_label(self,x):
        return self.d_inv[super().find(self.d[x])]
    def unite(self,x,y):
        super().unite(self.d[x],self.d[y])
    def size(self,x):
        return super().size(self.d[x])
    def same(self,x,y):
        return super().same(self.d[x],self.d[y])
    def members(self,x):
        root=self.find(self.d[x])
        return [self.d_inv[i] for i in range(self.n) if self.find(i)==root]
    def roots(self):
        return [self.d_inv[i] for i,x in enumerate(self.parents) if x<0]

def main():
    h,w=map(int,input().split())
    S=[input() for _ in range(h)]
    lis=[(i,j) for j in range(w) for i in range(h)]
    uf=UnionFindLabel(lis)
    for i,s in enumerate(S):
        for j,ss in enumerate(s):
            for row,col in ((1,0),(-1,0),(0,1),(0,-1)):
                if i+row>=0 and i+row<h and j+col>=0 and j+col<w and S[i+row][j+col]!=ss:
                    uf.unite((i,j),(i+row,j+col))
    lis_uf=uf.all_group_members_list()
    ans=0
    for ll in lis_uf:
        cunt_b=0
        cunt_w=0
        for r,l in ll:
            if S[r][l]=="#":cunt_b+=1
            else:cunt_w+=1
        ans+=cunt_b*cunt_w
    print(ans)
if __name__=='__main__':
    main()