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:
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())
N = H*W
def num(i,j):
    return i*W+j
def coo(num):
    i = num // W
    j = num % W
    return(i,j)

uf = UnionFind(N)
color = [-1]*N
grid = []
for i in range(H):
    grid.append(list(input()))
for i in range(H):
    for j in range(W):
        color[num(i,j)]= grid[i][j]
for i in range(H):
    for j in range(W-1):
        if grid[i][j] != grid[i][j+1]:
            uf.union(num(i,j),num(i,j+1))
for i in range(H-1):
    for j in range(W):
        if grid[i][j] != grid[i+1][j]:
            uf.union(num(i,j),num(i+1,j))
ans = 0
for li in uf.all_group_members().values():
    w = 0
    b = 0
    for num in li:
        if color[num] == "#":
            b += 1
        else:
            w += 1
    ans += b*w
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

H, W = MAP()
S = [input() for _ in range(H)]

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

for y0 in range(H):
	for x0 in range(W):
		if S[y0][x0] ==  ".":
			continue
		check = [[0]*W for _ in range(H)]
		check[y0][x0] = 1
		q = deque([(y0, x0, 1)])
		while q:
			#print(q)
			y, x, color = q.popleft()
			for i in range(4):
				ny = y + dy[i]
				nx = x + dx[i]
				if 0 <= ny < H and 0 <= nx < W:
					if color == 1 and S[ny][nx] == "." and check[ny][nx] == 0:
						check[ny][nx] = 1
						#print((y0, x0), (ny, nx))
						ans += 1
						q.append((ny, nx, 0))
					if color == 0 and S[ny][nx] == "#" and check[ny][nx] == 0:
						check[ny][nx] = 1
						q.append((ny, nx, 1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

H, W = MAP()
S = [input() for _ in range(H)]

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

for y0 in range(H):
	for x0 in range(W):
		if S[y0][x0] ==  ".":
			continue
		check = [[0]*W for _ in range(H)]
		check[y0][x0] = 1
		q = deque([(y0, x0, 1)])
		while q:
			#print(q)
			y, x, color = q.popleft()
			for i in range(4):
				ny = y + dy[i]
				nx = x + dx[i]
				if 0 <= ny < H and 0 <= nx < W:
					if color == 1 and S[ny][nx] == "." and check[ny][nx] == 0:
						check[ny][nx] = 1
						#print((y0, x0), (ny, nx))
						ans += 1
						q.append((ny, nx, 0))
					if color == 0 and S[ny][nx] == "#" and check[ny][nx] == 0:
						q.append((ny, nx, 1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:

import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]

H, W = read_values()
def f(F, h, w):
    S = deque()
    S.append((h, w))
    P = [[False for _ in range(W)] for _ in range(H)]
    res = 0
    while S:
        h, w = S.popleft()
        for hh, ww in [(h + 1, w), (h - 1, w), (h, w + 1), (h, w - 1)]:
            if not (0 <= hh < H and 0 <= ww < W):
                continue
            if P[hh][ww]:
                continue
            if F[hh][ww] == F[h][w]:
                continue
            P[hh][ww] = True
            res += 1 if F[hh][ww] == "." else 0
            S.append((hh, ww))
    return res


def main():
    F = [input().strip() for i in range(H)]
    
    res = 0
    for h in range(H):
        for w in range(W):
            if F[h][w] == "#":
                res += f(F, h, w)
    print(res)
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]

H, W = read_values()
def f(F, h, w):
    S = deque()
    S.append((h, w))
    P = {(h, w)}
    res = 0
    while S:
        h, w = S.popleft()
        for hh, ww in [(h + 1, w), (h - 1, w), (h, w + 1), (h, w - 1)]:
            if not (0 <= hh < H and 0 <= ww < W):
                continue
            if (hh, ww) in P:
                continue
            if F[hh][ww] == F[h][w]:
                continue
            P.add((hh, ww))
            res += 1 if F[hh][ww] == "." else 0
            S.append((hh, ww))
    return res


def main():
    F = [input().strip() for i in range(H)]
    
    res = 0
    for h in range(H):
        for w in range(W):
            if F[h][w] == "#":
                res += f(F, h, w)
    print(res)
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

    cnt = 0
    for h in range(H):
        for w in range(W):
            cnt += search(h,w,field)
    
    print(cnt)

def search(h,w,field):
    if field[h][w] == '.':
        return 0

    visited = [[False] * len(field[0]) for _ in range(len(field))]

    cnt = 0
    q = deque()
    isBlack = True if field[h][w] == '#' else False
    q.append((h,w,isBlack))

    while len(q) > 0:
        now_h,now_w,now_isBlack = q.popleft()
        d = ((1,0), (0,1), (-1,0), (0,-1))
        for dh, dw in d:
            next_h = now_h + dh
            next_w = now_w + dw
            if not(0 <= next_h < len(field)) or not(0 <= next_w < len(field[0])):
                continue

            next_isBlack = True if field[next_h][next_w] == '#' else False
            if not visited[next_h][next_w] and now_isBlack != next_isBlack:
                q.append((next_h,next_w, next_isBlack))
                visited[next_h][next_w] = True
                if not next_isBlack:
                    cnt += 1

    return cnt 

if __name__ == '__main__':
    solve()

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



def calc(i,j):
    return i*w+j
def calc_inv(x):
    return x//w, x%w
def judge(x,y):
    i0,j0 = calc_inv(x)
    i1,j1 = calc_inv(y)
    if s[i0][j0] != s[i1][j1]:
        return True
    return False


h,w = map(int,input().split())
s = [[(i == "#")*1 for i in list(input())] for _ in range(h)]
uf = UnionFind(h*w)

for i in range(h):
    for j in range(w):
        now = calc(i,j)
        nxt = calc(i+1,j)
        if i+1 < h:
            if judge(now,nxt):
                uf.union(now,nxt)
        nxt = calc(i,j+1)
        if j+1 < w:
            if judge(now,nxt):
                uf.union(now,nxt)


cnt = [[0,0] for _ in range(h*w)]
ind = 0
for l in uf.all_group_members().values():
    for x in l:
        i,j = calc_inv(x)
        if s[i][j]:
            cnt[ind][0] += 1
        else:
            cnt[ind][1] += 1
    ind += 1
ans = 0
for i in range(ind):
    ans += cnt[i][0]*cnt[i][1]
print(ans)

Submission status: Time Limit Exceeded

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

def DFS(y,x,S):
    m=[[0]*W for _ in range(H)]
    d=deque([])
    d.append((y,x,0))
    ans=0
    while d:
        p,q,n=d.popleft()
        if m[p][q]==1:
            continue
        else:
            if n%2==0 and S[p][q]=='#':
    
                m[p][q]=1
                if 0<=p+1<=H-1 and S[p+1][q]=='.':
                    d.append((p+1,q,n+1))
                if 0<=p-1<=H-1 and S[p-1][q]=='.':
                    d.append((p-1,q,n+1))
                if 0<=q+1<=W-1 and S[p][q+1]=='.':
                    d.append((p,q+1,n+1))
                if 0<=q-1<=W-1 and S[p][q-1]=='.':
                    d.append((p,q-1,n+1))
            
            elif n%2==1 and S[p][q]=='.':
                ans+=1
                
                m[p][q]=1
                if 0<=p+1<=H-1 and S[p+1][q]=='#':
                    d.append((p+1,q,n+1))
                if 0<=p-1<=H-1 and S[p-1][q]=='#':
                    d.append((p-1,q,n+1))
                if 0<=q+1<=W-1 and S[p][q+1]=='#':
                    d.append((p,q+1,n+1))
                if 0<=q-1<=W-1 and S[p][q-1]=='#':
                    d.append((p,q-1,n+1))
    return ans

total=0
for i in range(H):
    for j in range(W):
        total+=DFS(i,j,S)

print(total)

Submission status: Time Limit Exceeded

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

def DFS(y,x,S):
    m=[[0]*W for _ in range(H)]
    d=deque([])
    d.append((y,x,0))
    ans=0
    while d:
        p,q,n=d.pop()
        if m[p][q]==1:
            continue
        else:
            if n%2==0 and S[p][q]=='#':
    
                m[p][q]=1
                if 0<=p+1<=H-1 and S[p+1][q]=='.':
                    d.append((p+1,q,n+1))
                if 0<=p-1<=H-1 and S[p-1][q]=='.':
                    d.append((p-1,q,n+1))
                if 0<=q+1<=W-1 and S[p][q+1]=='.':
                    d.append((p,q+1,n+1))
                if 0<=q-1<=W-1 and S[p][q-1]=='.':
                    d.append((p,q-1,n+1))
            
            elif n%2==1 and S[p][q]=='.':
                ans+=1
                
                m[p][q]=1
                if 0<=p+1<=H-1 and S[p+1][q]=='#':
                    d.append((p+1,q,n+1))
                if 0<=p-1<=H-1 and S[p-1][q]=='#':
                    d.append((p-1,q,n+1))
                if 0<=q+1<=W-1 and S[p][q+1]=='#':
                    d.append((p,q+1,n+1))
                if 0<=q-1<=W-1 and S[p][q-1]=='#':
                    d.append((p,q-1,n+1))
    return ans

total=0
for i in range(H):
    for j in range(W):
        total+=DFS(i,j,S)

print(total)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    import sys
    input = sys.stdin.readline
    H, W = (int(i) for i in input().split())
    c = [[s for s in input()] for i in range(H)]

    def bfs(c, sy, sx, H, W):
        que = deque()
        dist = [[-1]*W for i in range(H)]

        dist[sy][sx] = 0
        que.append((sy, sx))
        d = ((1, 0), (0, 1), (-1, 0), (0, -1))
        ret = 0
        flag = False  # 黒色マスにいるとき，True
        while que:
            uh, uw = que.popleft()
            if c[uh][uw] == "#":
                flag = True
            else:
                flag = False
            for dy, dx in d:
                next_h = uh + dy
                next_w = uw + dx
                if not(0 <= next_h < H and 0 <= next_w < W):
                    continue
                if dist[next_h][next_w] != -1:
                    continue
                if flag and c[next_h][next_w] == '#':
                    continue
                if not flag and c[next_h][next_w] == ".":
                    continue
                dist[next_h][next_w] = dist[uh][uw] + 1
                if c[next_h][next_w] == ".":
                    ret += 1
                que.append((next_h, next_w))
        return ret

    ans = 0
    for h in range(H):
        for w in range(W):
            if c[h][w] == "#":
                ans += bfs(c, h, w, H, W)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

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

move = (-1, 1)
count = []

def dfs(i, j, seen):
    seen.add((i, j))
    if F[i][j] == '#':
        next = '.'
    else:
        next = '#'

    for m in move:
        if 0 <= i+m < H and F[i+m][j] == next and (i+m, j) not in seen:
            seen.add((i+m, j))
            if F[i][j] == '#':
                count.append((i+m, j))

            dfs(i+m, j, seen)
        if 0 <= j+m < W and F[i][j+m] == next and (i, j+m) not in seen:
            seen.add((i, j+m))
            if F[i][j] == '#':
                count.append((i, j+m))
            dfs(i, j+m, seen)

for i in range(H):
    for j in range(W):
        if F[i][j] == '#':
            dfs(i, j, set())

print(len(count))

Submission status: Time Limit Exceeded

Solution code:
#from numba import jit
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline

#@jit
def DFS(add,next):
    global cnt
    x,y=add
    for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
        X,Y=x+i,y+j
        if 0<=X<h and 0<=Y<w:
            if S[X][Y]==next and color[X][Y]=="white":
                color[X][Y]="black"
                DFS([X,Y],"." if next=="#" else "#")
                if next==".":cnt +=1


h,w=map(int,input().split())
S=[list(input()) for _ in range(h)]
cnt=0

for i in range(h):
    for j in range(w):
        if S[i][j]=="#":
            color=[["white" for _ in range(w)] for _ in range(h)]
            color[i][j]="black"
            DFS([i,j],".")

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

class UnionFind:
    #n個の要素を初期化
    def __init__(self, n):
        self.n = n
        self.par = [-1] * n
        self.rank = [0] * n
    
    #木の根を求める
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    #xとyの属する集合を併合
    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.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    #xとyが同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    #要素xが属するグループに属する要素をリストで返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    #xが属する集合の個数
    def size(self, x):
        return self.par.count(self.find(x))
    
    def roots(self):
        return [i for i, x in enumerate(self.par) if x < 0]

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

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

uf = UnionFind(H*W)

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

for i in range(H):
    for j in range(W):
        p = field[i][j]
        for dx, dy in d:
            x = i + dx
            y = j + dy
            if 0 <= x <= H-1 and 0 <= y <= W-1:
                if p != field[x][y]:
                    uf.unite(i*W+j, x*W+y)
roots = uf.roots()
ans = 0
for r in roots:
    bw = {".": 0, "#": 0}
    members = uf.members(r)
    for m in members:
        x = m // W
        y = m % W
        bw[field[x][y]] += 1
    ans += bw["."]*bw["#"]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500*500)

h,w=list(map(int,input().split()))
s=[[1 if c=='#' else 0 for c in input()] for _ in range(h)]
g=[[] for _ in range(h*w)]

for i in range(w):
    for j in range(h):
        for di in [-1,0,1]:
            for dj in [-1,0,1]:
                if abs(di)+abs(dj)!=1:
                    continue
                if 0<=i+di<w and 0<=j+dj<h:
                    if s[j][i]!=s[j+dj][i+di]:
                        g[j*w+i].append(i+di+(j+dj)*w)

visit=[0]*(h*w)
black=[0]*(h*w)
white=[0]*(h*w)

def rec(j,i,rj,ri):
    if s[j][i]:
        black[rj*w+ri]+=1
    else:
        white[rj*w+ri]+=1
    
    for n in g[j*w+i]:
        if visit[n]==1:
            continue

        visit[n]=1

        rec(n//w,n%w,rj,ri)

ans=0

for i in range(w):
    for j in range(h):
        if visit[w*j+i]:
            continue
        visit[w*j+i]=1

        rec(j,i,j,i)
        
        ans+=black[w*j+i]*white[w*j+i]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500*500)

h,w=list(map(int,input().split()))
s=[input() for _ in range(h)]
g=[[] for _ in range(h*w)]

for i in range(w):
    for j in range(h):
        for di in [-1,0,1]:
            for dj in [-1,0,1]:
                if abs(di)+abs(dj)!=1:
                    continue
                if 0<=i+di<w and 0<=j+dj<h:
                    if s[j][i]!=s[j+dj][i+di]:
                        g[j*w+i].append(i+di+(j+dj)*w)

visit=[0]*(h*w)
ans=0
black=[0]*(h*w)
white=[0]*(h*w)

def rec(j,i,rj,ri):
    if s[j][i]=='#':
        black[rj*w+ri]+=1
    else:
        white[rj*w+ri]+=1
    
    for n in g[j*w+i]:
        if visit[n]==1:
            continue

        nj=n//w
        ni=n%w

        visit[n]=1

        rec(nj,ni,rj,ri)

for i in range(w):
    for j in range(h):
        if visit[w*j+i]:
            continue
        visit[w*j+i]=1

        rec(j,i,j,i)
        
        ans+=black[w*j+i]*white[w*j+i]

print(ans)

Submission status: Time Limit Exceeded

Solution code:


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    ################
    class UnionFind():
        """
        parents : 親要素(findしない場合は根ではないことの注意)，根の場合は"-(要素数）"
        find(x):要素xの属するグループの根を返す
        size(x):要素xの属するグループの要素数を返す
        same(x,y):x,yが同じグループに属しているか返す
        members(x):要素xが属するグループに属する要素をリストで返す
        roots:全ての根の要素を返す
        group_count():グループの数を返す
        all_group_members():{根要素：[そのグループに含まれる要素のリスト]}の辞書を返す
        """
        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=MI()
    S=[]
    for i in range(H):
        s=input()
        S.append(s)
    uf=UnionFind(H*W)
    
    dx=[0,1]
    dy=[1,0]
    
    def make(ii,jj):
        return ii*W+jj
    
    def rev(v):
        jj=v%W
        ii=(v-jj)//W
        return (ii,jj)
    
    for i in range(H):
        for j in range(W):
            for k in range(2):
                ni=i+dx[k]
                nj=j+dy[k]
                if 0<=ni<H and 0<=nj<W:
                    if S[i][j]!=S[ni][nj]:
                        uf.union(make(i,j),make(ni,nj))
                        
    ans=0
    from collections import defaultdict
    ddb = defaultdict(int)
    ddh = defaultdict(int)
    
    roots=uf.roots()
    dic=uf.all_group_members()

    
    for root in roots:
        L=dic[root]
        for v in L:
            ii,jj=rev(v)
            if S[ii][jj]=="#":
                ddb[root]+=1
            else:
                ddh[root]+=1
            
    for k,v in ddb.items():
        ans+=v*ddh[k]
        
        
    print(ans)
            
    
        
main()

Submission status: Time Limit Exceeded

Solution code:


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    ################
    class UnionFind():
        """
        parents : 親要素(findしない場合は根ではないことの注意)，根の場合は"-(要素数）"
        find(x):要素xの属するグループの根を返す
        size(x):要素xの属するグループの要素数を返す
        same(x,y):x,yが同じグループに属しているか返す
        members(x):要素xが属するグループに属する要素をリストで返す
        roots:全ての根の要素を返す
        group_count():グループの数を返す
        all_group_members():{根要素：[そのグループに含まれる要素のリスト]}の辞書を返す
        """
        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=MI()
    S=[]
    for i in range(H):
        s=input()
        S.append(s)
    uf=UnionFind(H*W)
    
    dx=[0,1]
    dy=[1,0]
    
    def make(ii,jj):
        return ii*W+jj
    
    def rev(v):
        jj=v%W
        ii=(v-jj)//W
        return (ii,jj)
    
    for i in range(H):
        for j in range(W):
            for k in range(2):
                ni=i+dx[k]
                nj=j+dy[k]
                if 0<=ni<H and 0<=nj<W:
                    if S[i][j]!=S[ni][nj]:
                        uf.union(make(i,j),make(ni,nj))
                        
    ans=0
    for root in uf.roots():
        L=uf.members(root)
        bk=0
        wh=0
        for v in L:
            ii,jj=rev(v)
            if S[ii][jj]=="#":
                bk+=1
            else:
                wh+=1
        ans+=bk*wh
        
    print(ans)
            
    
        
main()

Submission status: Time Limit Exceeded

Solution code:


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    ################
    class UnionFind():
        """
        parents : 親要素(findしない場合は根ではないことの注意)，根の場合は"-(要素数）"
        find(x):要素xの属するグループの根を返す
        size(x):要素xの属するグループの要素数を返す
        same(x,y):x,yが同じグループに属しているか返す
        members(x):要素xが属するグループに属する要素をリストで返す
        roots:全ての根の要素を返す
        group_count():グループの数を返す
        all_group_members():{根要素：[そのグループに含まれる要素のリスト]}の辞書を返す
        """
        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())
        
    ################


    mod=10**9+7
    H,W=MI()
    S=[]
    for i in range(H):
        s=input()
        S.append(s)
    uf=UnionFind(H*W)
    
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    
    def make(ii,jj):
        return ii*W+jj
    
    def rev(v):
        jj=v%W
        ii=(v-jj)//W
        return (ii,jj)
    
    for i in range(H):
        for j in range(W):
            for k in range(4):
                ni=i+dx[k]
                nj=j+dy[k]
                if 0<=ni<H and 0<=nj<W:
                    if S[i][j]!=S[ni][nj]:
                        uf.union(make(i,j),make(ni,nj))
                        
    ans=0
    for root in uf.roots():
        L=uf.members(root)
        bk=0
        wh=0
        for v in L:
            ii,jj=rev(v)
            if S[ii][jj]=="#":
                bk+=1
            else:
                wh+=1
        ans+=bk*wh
        
    print(ans)
            
    
        
main()