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 sys
sys.setrecursionlimit(10**8)
h, w = [int(i) for i in sys.stdin.readline().split()]
s_ls = []
bl_ls = []
for i in range(h):
    s = [1 if i == "#" else -1 for i in sys.stdin.readline().strip()]
    for j, k in enumerate(s):
        if k == 1:
            bl_ls.append((i, j))
    s_ls.append(s)

memo_ls = dict()
def dfs(y, x, col):
    if (y, x) in memo_ls:
        return memo_ls[(y, x)]
    res = 0
    if col == -1:
        res += 1
    already.add((y, x))
    for move_y, move_x in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        next_y = y + move_y
        next_x = x + move_x
        if 0 <= next_x < w and 0 <= next_y < h and s_ls[next_y][next_x] == (-1) * col and (next_y, next_x) not in already:
            res += dfs(next_y, next_x, (-1) * col)
    return res

ans = 0
for bl in bl_ls:
    already = set()
    res = dfs(bl[0], bl[1], 1)
    ans += res
    for al in list(already):
        memo_ls[al] = res
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
h, w = [int(i) for i in sys.stdin.readline().split()]
s_ls = []
bl_ls = []
for i in range(h):
    s = [1 if i == "#" else -1 for i in sys.stdin.readline().strip()]
    for j, k in enumerate(s):
        if k == 1:
            bl_ls.append((i, j))
    s_ls.append(s)

def dfs(y, x, col):
    res = 0
    if col == -1:
        res += 1
    already.add((y, x))
    for move_y, move_x in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        next_y = y + move_y
        next_x = x + move_x
        if 0 <= next_x < w and 0 <= next_y < h and s_ls[next_y][next_x] == (-1) * col and (next_y, next_x) not in already:
            res += dfs(next_y, next_x, (-1) * col)
    return res

ans = 0
for bl in bl_ls:
    already = set()
    ans += dfs(bl[0], bl[1], 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

def bfs(x, y, c):
    grid = [[None] * W for _ in range(H)]

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

    que = deque()
    que.append(((x, y), c))
    grid[y][x] = 'visited'
    ret = 0

    while que:
        p, color = que.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            next_color = '#' if color == '.' else '.'            
            if 0 <= ny and ny <= H-1 and 0 <= nx and nx <= W-1 and \
                    grid[ny][nx] == None and data[ny][nx] == next_color:
                grid[ny][nx] = 'visited'
                if next_color == '.':
                    ret += 1
                que.append(((nx, ny), next_color))
    return ret

H, W = rl()
data = [list(rs()) for _ in range(H)]
answer = 0

for y in range(H):
    for x in range(W):
        if data[y][x] == '#':
          answer += bfs(x, y, data[y][x])

print(answer)
#46

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

H,W = map(int,input().split())
N = H*W
uf = UnionFind(N)
S = [input() for _ in range(H)]
ans = 0

for k in range(N):
    x = k//W
    y = k-W*x
    if x+1<H and S[x][y]!=S[x+1][y]:
        uf.union(k,(x+1)*W+y)
    if y+1<W and S[x][y]!=S[x][y+1]:
        uf.union(k,x*W+y+1)

for v in uf.all_group_members().values():
    b = 0
    w = 0
    for k in v:
        x = k//W
        y = k-W*x
        if S[x][y]=='#':
            b += 1
        else:
            w += 1
    ans += b*w

print(ans)

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

H,W = map(int,input().split())
N = H*W
uf = UnionFind(N)
S = [input() for _ in range(H)]
dx = [1,0,-1,0]
dy = [0,1,0,-1]
ans = 0

for k in range(N):
    x = k//W
    y = k-W*x
    for d in range(4):
        nx,ny = x+dx[d],y+dy[d]
        nk = nx*W+ny
        if not (0<=nx<H and 0<=ny<W):
            continue
        if S[x][y]!=S[nx][ny]:
            uf.union(k,nk)

for v in uf.all_group_members().values():
    b = 0
    w = 0
    for k in v:
        x = k//W
        y = k-W*x
        if S[x][y]=='#':
            b += 1
        else:
            w += 1
    ans += b*w

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
# from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def main():
    
    h, w = map(int, input().split())
    s = [list(input()) for i in range(h)]
    start = []
    d = {}
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#": 
                start.append([i,j])
                d[(i, j)] = -1

    ans = [0,0]
    vis = [[-1 for i in range(w)] for j in range(h)]
    def f(x, y, pre):
        vis[x][y] = 1
        if s[x][y] == "#":
            ans[0] += 1
        else:
            ans[1]+=1
        for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            nx = i + x
            ny = j + y
            if nx >= 0 and ny >= 0 and nx < h and ny < w and vis[nx][ny] == -1:
                if pre == "B" and s[nx][ny] == ".":
                    f(nx,ny,"W")
                elif pre == "W" and s[nx][ny] == "#":
                    f(nx, ny, "B")
                
    
    ret = 0
    for i, j in start:
        if vis[i][j] == -1:
            f(i, j, "B")
        ret += ans[0] * ans[1]
        ans[0] = ans[1] = 0
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int,input().split())
S = [input().strip() for _ in range(H)]
D = {0:".",1:"#"}
cnt = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            que = deque([(i,j,1)])
            hist = [[0 for _ in range(W)] for _ in range(H)]
            hist[i][j] = 1
            while que:
                s = que.popleft()
                y,x = s[0],s[1]
                a = s[2]
                if x+1<W and hist[y][x+1]==0 and S[y][x+1]==D[1-a]:
                    if a==1:
                        cnt += 1
                    que.append((y,x+1,1-a))
                    hist[y][x+1]=1
                if y-1>-1 and hist[y-1][x]==0 and S[y-1][x]==D[1-a]:
                    if a==1:
                        cnt += 1
                    que.append((y-1,x,1-a))
                    hist[y-1][x]=1
                if x-1>-1 and hist[y][x-1]==0 and S[y][x-1]==D[1-a]:
                    if a==1:
                        cnt += 1
                    que.append((y,x-1,1-a))
                    hist[y][x-1]=1
                if y+1<H and hist[y+1][x]==0 and S[y+1][x]==D[1-a]:
                    if a==1:
                        cnt += 1
                    que.append((y+1,x,1-a))
                    hist[y+1][x]=1
print(cnt)

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())
m=[list(input()) for _ in range(H)]
tree = UnionFind(H*W)
for i in range(H):
    for j in range(W-1):
        if m[i][j] != m[i][j+1]:
            tree.union(i*W+j,i*W+j+1)
for j in range(W):
    for i in range(H-1):
        if m[i][j] != m[i+1][j]:
            tree.union(i*W+j,(i+1)*W+j)
ans=0
for r in tree.roots():
    l = tree.members(r)
    w = len([0 for x in l if m[x//W][x%W] =='.'])
    b = len([0 for x in l if m[x//W][x%W] =='#'])
    ans += w*b
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])

def search(x,y,key):
    global wh,bl,s,done,h,w,que
    if x<0 or h<=x or y<0 or w<=y or  done[x][y]:
        return
    elif (key==0 and s[x][y]=='.') or (key==1 and s[x][y]=='#'):
        return
    elif key==0 and s[x][y]=='#':
        bl+=1
        key=1
        done[x][y]=True
        search(x-1,y,key)
        search(x,y-1,key)
        search(x+1,y,key)
        search(x,y+1,key)
    elif key==1 and s[x][y]=='.':
        wh+=1
        key=0
        done[x][y]=True
        search(x-1,y,key)
        search(x,y-1,key)
        search(x+1,y,key)
        search(x,y+1,key)

def main():
    global wh,bl,s,done,key,h,w,que
    h,w=inpm()
    s=[]
    for _ in range(h):
        s.append(tuple(input()))
    s=tuple(s)
    ans=0
    done = [[False for _ in range(w)] for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if (not done[i][j]) and s[i][j]=='#':
                key=0
                bl=0
                wh=0
                search(i,j,key)
                ans+=bl*wh
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])

def search(x,y,key):
    global wh,bl,s,done,h,w,que
    if x<0 or h<=x or y<0 or w<=y or  done[x][y]:
        return
    elif (key==0 and s[x][y]=='.') or (key==1 and s[x][y]=='#'):
        return
    elif key==0 and s[x][y]=='#':
        bl+=1
        key=1
        done[x][y]=True
        search(x-1,y,key)
        search(x,y-1,key)
        search(x+1,y,key)
        search(x,y+1,key)
    elif key==1 and s[x][y]=='.':
        wh+=1
        key=0
        done[x][y]=True
        search(x-1,y,key)
        search(x,y-1,key)
        search(x+1,y,key)
        search(x,y+1,key)

def main():
    global wh,bl,s,done,key,h,w,que
    h,w=inpm()
    s=[]
    for _ in range(h):
        s.append(tuple(input()))
    s=tuple(s)
    ans=0
    done = [[False for _ in range(w)] for _ in range(h)]
    que=deque([])
    for i in range(h):
        for j in range(w):
            if s[i][j]=='#':
                x0=i
                y0=j
                que.append((x0,y0))
    while len(que)>0:
        x,y=que.pop()
        key=0
        bl=0
        wh=0
        search(x,y,key)
        ans+=bl*wh
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])

def search(x,y,key):
    global wh,bl,s,done,h,w
    if x<0 or h<=x or y<0 or w<=y:
        return
    if done[x][y]:
        return
    if key==0 and s[x][y]=='.':
        return
    elif key==0 and s[x][y]=='#':
        bl+=1
        key=1
        done[x][y]=True
        search(x-1,y,key)
        search(x,y-1,key)
        search(x+1,y,key)
        search(x,y+1,key)
    elif key==1 and s[x][y]=='.':
        wh+=1
        key=0
        done[x][y]=True
        search(x-1,y,key)
        search(x,y-1,key)
        search(x+1,y,key)
        search(x,y+1,key)
    elif key==1 and s[x][y]=='#':
        return
        
def main():
    global key,wh,bl,s,done,key,h,w
    h,w=inpm()
    s=[]
    for _ in range(h):
        s.append(tuple(input()))
    s=tuple(s)
    ans=0
    done = [[False for _ in range(w)] for _ in range(h)]
    for i in range(h):
        for j in range(w):
            key=0
            bl=0
            wh=0
            search(i,j,key)
            ans+=bl*wh
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])

def search(x,y,h,w,key):
    global wh,bl,s,done
    if x<0 or h<=x or y<0 or w<=y:
        return
    if done[x][y]:
        return
    if key==0 and s[x][y]=='.':
        return
    elif key==0 and s[x][y]=='#':
        bl+=1
        key=1
        done[x][y]=True
        search(x-1,y,h,w,key)
        search(x,y-1,h,w,key)
        search(x+1,y,h,w,key)
        search(x,y+1,h,w,key)
    elif key==1 and s[x][y]=='.':
        wh+=1
        key=0
        done[x][y]=True
        search(x-1,y,h,w,key)
        search(x,y-1,h,w,key)
        search(x+1,y,h,w,key)
        search(x,y+1,h,w,key)
    elif key==1 and s[x][y]=='#':
        return
        
def main():
    global key,wh,bl,s,done,key
    h,w=inpm()
    s=[]
    for _ in range(h):
        s.append(list(input()))
    ans=0
    done = [[False for _ in range(w)] for _ in range(h)]
    for i in range(h):
        for j in range(w):
            key=0
            bl=0
            wh=0
            search(i,j,h,w,key)
            ans+=bl*wh
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class UnionFind(object):
    def __init__(self, size):
        self.parent = list(range(size))
    
    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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            self.parent[x] = y

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


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

uf = UnionFind(h * w)

diffs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for i in range(h):
    for j in range(w):
        for di, dj in diffs:
            ni = i + di
            nj = j + dj
            if 0 <= ni < h and 0 <= nj < w and s[i][j] != s[ni][nj]:
                p = i * w + j
                np = ni * w + nj
                uf.union(p, np)
c = 0
for i in range(h * w):
    for j in range(i + 1, h * w):
        if s[i // w][i % w] != s[j // w][j % w] and uf.same(i, j):
            c += 1

print(c)

Submission status: Time Limit Exceeded

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

diffs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
wf = [[float('inf')] * (h * w) for _ in range(h * w)]
for i in range(h):
    for j in range(w):
        for di, dj in diffs:
            ni = i + di
            nj = j + dj
            if 0 <= ni < h and 0 <= nj < w and s[i][j] != s[ni][nj]:
                p = i * w + j
                np = ni * w + nj
                wf[p][np] = 1

for k in range(h * w):
    for i in range(h * w):
        for j in range(h * w):
            wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j])

c = 0
for i in range(h * w):
    for j in range(i + 1, h * w):
        if s[i // w][i % w] != s[j // w][j % w] and wf[i][j] != float('inf'):
            c += 1

print(c)

Submission status: Time Limit Exceeded

Solution code:
def main():

    H, W = map(int, input().split())
    A = []
    for _ in range(H): A.append(input())
    # print(A)
    ans = 0
    mv = [[1,0],[0,1],[-1,0],[0,-1]]
    for i in range(H):
        for j in range(W):
            if A[i][j] == "#":
                # print(i, j)
                visited = set()
                visited.add((i, j))
                cnt = 0
                cur = [[i, j]]
                while cur:
                    temp = []
                    cnt += 1
                    if cnt % 2 == 1: c = "."
                    else: c = "#"
                    for i1, j1 in cur:
                        for di, dj in mv:
                            k, l = i1+di, j1+dj
                            if 0<=k<H and 0<=l<W and (k, l) not in visited and A[k][l] == c:
                                visited.add((k, l))
                                temp.append([k, l])
                                if c == ".":
                                    ans += 1
                    cur = temp
                # print(i, j, ans)

    return ans

if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

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

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

def dfs(th,tw):
    global flag,h,w,s
    flag[th][tw] = True
    tblack = 0
    twhite = 0
    if s[th][tw] == "#":
        tblack += 1
    else:
        twhite += 1 
    for x,y in ([0,1],[0,-1],[1,0],[-1,0]):
        nth = th + x
        ntw = tw + y
        if nth >= 0 and nth < h and ntw >= 0 and ntw < w:
            if not flag[nth][ntw] and s[th][tw] != s[nth][ntw]:
                ttb,ttw = dfs(nth,ntw)
                tblack += ttb
                twhite += ttw
    return [tblack,twhite]
                
def main():
    global flag,h,w,s
    res = 0
    for i in range(h):
        for j in range(w):
            if not flag[i][j]:
                black,white = dfs(i,j)
                res += black * white 

    return res
print(main())

Submission status: Time Limit Exceeded

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

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

def dfs(th,tw):
    global flag,h,w
    flag[th][tw] = True
    tblack = 0
    twhite = 0
    if s[th][tw] == "#":
        tblack += 1
    else:
        twhite += 1 
    for x,y in ([0,1],[0,-1],[1,0],[-1,0]):
        nth = th + x
        ntw = tw + y
        if nth >= 0 and nth < h and ntw >= 0 and ntw < w:
            if not flag[nth][ntw] and s[th][tw] != s[nth][ntw]:
                ttb,ttw = dfs(nth,ntw)
                tblack += ttb
                twhite += ttw
    return [tblack,twhite]
                
res = 0
for i in range(h):
    for j in range(w):
        if not flag[i][j]:
            black,white = dfs(i,j)
            res += black * white 

print(res)

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 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 all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

def main():
    h,w=map(int,input().split())
    s=[input() for _ in range(h)]

    u=UnionFind(h*w)

    for i in range(h):
        for j in range(w):
            if j !=0:
                if s[i][j-1] != s[i][j]:
                    u.union(i*w+j-1,i*w+j)
            if i !=0:
                if s[i-1][j] != s[i][j]:
                    u.union((i-1)*w+j,i*w+j)
    res = 0
    gd=u.all_group_members()
    ns = "".join(s)
    for ld in gd.values():
        black = 0
        white = 0
        for sd in ld:
            if ns[sd]=="#":
                black += 1
            else:
                white += 1
        res += black * white

    print(res)

main()

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 main():
    h,w=map(int,input().split())
    s=[input() for _ in range(h)]

    u=UnionFind(h*w)

    for i in range(h):
        for j in range(w):
            if j !=0:
                if s[i][j-1] != s[i][j]:
                    u.union(i*w+j-1,i*w+j)
            if i !=0:
                if s[i-1][j] != s[i][j]:
                    u.union((i-1)*w+j,i*w+j)
    res = 0
    gd=u.all_group_members()
    ns = "".join(s)
    for ld in gd.values():
        black = 0
        white = 0
        for sd in ld:
            if ns[sd]=="#":
                black += 1
            else:
                white += 1
        res += black * white

    print(res)

main()

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 main():
    h,w=map(int,input().split())
    s=[input() for _ in range(h)]

    u=UnionFind(h*w)

    for i in range(h):
        for j in range(w):
            if j !=0:
                if s[i][j-1] != s[i][j]:
                    u.union(i*w+j-1,i*w+j)
            if i !=0:
                if s[i-1][j] != s[i][j]:
                    u.union((i-1)*w+j,i*w+j)
    res = 0
    gd=u.all_group_members()
    for ld in gd.values():
        black = 0
        white = 0
        for sd in ld:
            if s[sd//w][sd%w]=="#":
                black += 1
            else:
                white += 1
        res += black * white

    print(res)

main()

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 main():
    h,w=map(int,input().split())
    s=[input() for _ in range(h)]

    u=UnionFind(h*w)

    for i in range(h):
        for j in range(w):
            if j !=0:
                if s[i][j-1] != s[i][j]:
                    u.union(i*w+j-1,i*w+j)
            if i !=0:
                if s[i-1][j] != s[i][j]:
                    u.union((i-1)*w+j,i*w+j)
    res = 0
    for i in range(h*w):
        ih=i//w
        iw=i%w
        for j in range(i,h*w):
            if s[ih][iw] != s[j//w][j%w] and u.same(i,j):
                    res += 1
    print(res)

main()