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 queue
import copy

def bfs(si, sj, gi, gj, m):
    t = copy.deepcopy(m)
    d0 = [1,0,-1,0]
    d1 = [0,-1,0,1]
    q = queue.Queue()
    q.put([si,sj])
    while not q.empty():
        cur = q.get()
        for d in range(4):
            nci, ncj = cur[0]+d0[d], cur[1]+d1[d]
            if [nci,ncj] == [gi,gj]:
                return True
            if t[nci][ncj] == '#':
                t[nci][ncj] = '*'
                q.put([nci,ncj])
    return False

h, w = map(int,input().split())
m = [['*' for i in range(w+2)]]
for i in range(h):
    s = input()
    l = ['*']
    for j in range(w):
        l.append(s[j])
    l.append('*')
    m.append(l)
m.append(['*' for i in range(w+2)])
e = copy.deepcopy(m)
for i in range(1,h+1):
    for j in range(1,w+1):
        if (i+j)%2==0:
            if m[i][j]=='.':
                e[i][j]='*'
        else:
            if m[i][j]=='#':
                e[i][j]='*'
            else:
                e[i][j]='#'
o = copy.deepcopy(m)
for i in range(1,h+1):
    for j in range(1,w+1):
        if (i+j)%2==1:
            if m[i][j]=='.':
                o[i][j]='*'
        else:
            if m[i][j]=='#':
                o[i][j]='*'
            else:
                o[i][j]='#'
s, g = [], []
for i in range(1,h+1):
    for j in range(1,w+1):
        if m[i][j]=='#':
            s.append([i,j])
        else:
            g.append([i,j])
c = 0
for i in s:
    for j in g:
        if (i[0]+i[1])%2!=(j[0]+j[1])%2:
            if (i[0]+i[1])%2==0:
                if (bfs(i[0],i[1],j[0],j[1],e)):
                    c+=1
            else:
                if (bfs(i[0],i[1],j[0],j[1],o)):
                    c+=1
print(c)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import copy
h,w=map(int, input().split(" "))
arr=np.zeros((h,w))
startlist=[]
for i in range(h):
    tmp=input()
    for num,k in enumerate(tmp):
        if k == "#":
            arr[i,num]=1
            startlist.append((i,num))


count=0
skips=[]
used=[]
for st in startlist:
    i=st[0]
    k=st[1]
#for i in range(h):
#    for k in range(w):
    if (i,k) in skips:
        continue
    ntmp=[(i,k)]
    
    next=0
    #if arr[i,k]==1:
    white=[]
    skipcount=1
    while len(ntmp)>0:
        tmp=ntmp.copy()
        ntmp=[]
        for lis in tmp:
        #lis=tmp[0]
            used.append(lis)
            
            #del tmp[0]
            if lis[0]+1<h:
                if arr[lis[0]+1,lis[1]]==next:
                    if next==0:
                        #count+=1
                        white.append((lis[0]+1,lis[1]))
                    if (lis[0]+1,lis[1]) not in used:
                        ntmp.append((lis[0]+1,lis[1]))
            
            if lis[0]-1>=0:
                if arr[lis[0]-1,lis[1]]==next:
                    if next==0:
                        #count+=1
                        white.append((lis[0]-1,lis[1]))
                    if (lis[0]-1,lis[1]) not in used:
                        ntmp.append((lis[0]-1,lis[1]))
            if lis[1]+1<w:
                if arr[lis[0],lis[1]+1]==next:
                    if next==0:
                        #count+=1
                        white.append((lis[0],lis[1]+1))
                    if (lis[0],lis[1]+1) not in used:
                        ntmp.append((lis[0],lis[1]+1))
            if lis[1]-1>=0:
                #print(arr[lis[0],lis[1]-1])
                if arr[lis[0],lis[1]-1]==next:
                    if next==0:
                        #count+=1
                        white.append((lis[0],lis[1]-1))
                    if (lis[0],lis[1]-1) not in used:
                        ntmp.append((lis[0],lis[1]-1))
    
            ntmp=list(set(ntmp))
            #print(ntmp)
            #print(white)
            #aaaaa
        if next==0:
            next=1
        else:
            next=0
            #for nt in ntmp:
            if len(ntmp)>0:
                skips.extend(ntmp)
                skipcount+=1
        #print(len(ntmp))
    count+=len(set(white))*skipcount
    #print(skips)
    #print(len(set(white)))

print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)
h, w = map(int, input().split())
s = [input() for i in range(h)]
bpos = [(i, j) for i in range(h) for j in range(w) if s[i][j] == '#']
count = 0
v = []

def dfs(hh, ww, c):
    if hh < 0 and hh >= h and ww < 0 and ww >= w and not((hh, ww) in bpos):
        return c

    if not((hh,ww) in v):
        if not((hh-1, ww) in bpos) and 0 <= hh-1 and hh-1 < h and 0 <= ww and ww < w:
            c += 1
        if not((hh+1, ww) in bpos) and 0 <= hh+1 and hh+1 < h and 0 <= ww and ww < w:
            c += 1
        if not((hh, ww-1) in bpos) and 0 <= ww-1 and ww-1 < w and 0 <= hh and hh < h:
            c += 1
        if not((hh, ww+1) in bpos) and 0 <= ww+1 and ww+1 < w and 0 <= hh and hh < h:
            c += 1

        v.append((hh,ww))

        c += dfs(hh+1, ww+1, c)
        c += dfs(hh-1, ww+1, c)
        c += dfs(hh-1, ww-1, c)
        c += dfs(hh+1, ww-1, c)

    else:
        v.append((hh,ww))

    return c

for p in bpos:
    count += dfs(p[0],p[1],0)

print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)
h, w = map(int, input().split())
MAP = [[0] * (w + 1)] + [[0] + [(1 if s == '#' else -1) for s in input()] + [0] for _ in range(h)] + [[0] * (w + 1)]
ans = 0
se = set()
def f(y, x, u):
    ret = 0
    for ny, nx in ((y - 1, x), (y, x - 1), (y, x + 1), (y + 1, x)):
        t = ny * 1000 + nx
        if MAP[ny][nx] == u and t not in se:
            if u == -1:
                ret += 1
            se.add(t)
            ret += f(ny, nx, -u)
    return ret
for i in range(1, h + 1):
    for j in range(1, w + 1):
        if MAP[i][j] == 1:
            se = set([i * 1000 + j])
            ans += f(i, j, -1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra

@np.vectorize
def trans(s):
    return 1 if s == "#" else 0

H, W = map(int, input().split())
S = np.array([trans([w for w in input()]) for _ in range(H)]).flatten()

def next_point(i, j, H, W, S):
    if S[i] != S[j]:
        if i == j + 1 and i % W != 0:
            return 2
        elif i == j - 1 and j % W != 0:
            return 2
        elif i == j + W:
            return 2
        elif i == j - W:
            return 2
        else:
            return 1
    else:
        return 0

G = np.array([[next_point(i, j, H, W, S) for j in range(len(S))] for i in range(len(S))])
connections = dijkstra(G >= 2)
c = (connections < np.inf) * G >= 1
print(int(np.sum(c) / 2))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)
h, w = map(int, input().split())
MAP = ["_" * (w + 1)] + ['_' + input() + '_' for _ in range(h)] + ["_" * (w + 1)]
ans = 0
se = set()
m = {0:'#', 1:'.'}
def f(y, x, u):
    for ny, nx in ((y - 1, x), (y, x - 1), (y, x + 1), (y + 1, x)):
        t = ny * 1000 + nx
        if MAP[ny][nx] == m[u] and t not in se:
            if u == 1:
                global ans
                ans += 1
            se.add(t)
            f(ny, nx, 1 - u)
for i in range(1, h + 1):
    for j in range(1, w + 1):
        if MAP[i][j] == '#':
            se = set([i * 1000 + j])
            f(i, j, 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
c=0
b=0
wi=0
x=[-1,0,1,0]
y=[0,-1,0,1]
buf=[]
def count(h,w,S,table,H,W,index):
    global buf,x,y,b,wi
    if index==1:
        b+=1
    else:
        wi+=1
    if index==1:
        S[h][w]='6'
    for i in range(4):
        if h+y[i]>=0 and h+y[i]<H and w+x[i]>=0 and w+x[i]<W:
            if table[h+y[i]][w+x[i]]==-1:
                if index==0 and S[h+y[i]][w+x[i]]=='#':
                    table[h+y[i]][w+x[i]]=table[h][w]+1
                    buf.append([h+y[i],w+x[i],1])
                elif index==1 and S[h+y[i]][w+x[i]]=='.':
                    table[h+y[i]][w+x[i]]=table[h][w]+1
                    buf.append([h+y[i],w+x[i],0])
    if buf:
        a=buf.pop(0)
        count(a[0],a[1],S,table,H,W,a[2])
sys.setrecursionlimit(10000000)
H,W=map(int,input().split())
T=[]
for i in range(H):
    T.append(input())
S=[['' for j in range(W)]for i in range(H)]
for h in range(H):
    for w in range(W):
        S[h][w]=T[h][w]
for h in range(H):
    for w in range(W):
        if S[h][w]=='#':
            table=[[-1 for j in range(W)] for i in range(H)]
            table[h][w]=0
            p=0
            count(h,w,S,table,H,W,1)
            
            c+=b*wi
            b=0
            wi=0
print(c)

Submission status: Time Limit Exceeded

Solution code:
import queue
import copy

def bfs(si, sj, gi, gj, m):
    t = copy.deepcopy(m)
    p = (si+sj)%2
    if (gi+gj)%2==p:
        return False
    for i in range(1,h+1):
        for j in range(1,w+1):
            if (i+j)%2==p:
                if t[i][j]!='#':
                    t[i][j]='*'
            else:
                if t[i][j]=='#':
                    t[i][j]='*'
                else:
                    t[i][j]='#'
    d0 = [1,0,-1,0]
    d1 = [0,-1,0,1]
    q = queue.Queue()
    q.put([si,sj])
    while not q.empty():
        cur = q.get()
        for d in range(4):
            nci, ncj = cur[0]+d0[d], cur[1]+d1[d]
            if [nci,ncj] == [gi,gj]:
                return True
            if t[nci][ncj] == m[si][sj]:
                t[nci][ncj] = '*'
                q.put([nci,ncj])
    return False

h, w = map(int,input().split())
m = [['*' for i in range(w+2)]]
for i in range(h):
    s = input()
    l = ['*']
    for j in range(w):
        l.append(s[j])
    l.append('*')
    m.append(l)
m.append(['*' for i in range(w+2)])
c = 0
for i in range(1,h+1):
    for j in range(1,w+1):
        if m[i][j]=='#':
            for ii in range(1,h+1):
                for jj in range(1,w+1):
                    if m[ii][jj]=='.':
                        if (bfs(i,j,ii,jj,m)):
                            c+=1
print(c)

Submission status: Time Limit Exceeded

Solution code:
def main():
    """
    1 <= H, W <= 400
    |Si| = W  (#, .)
    """
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]

    ans = f(H, W, S)
    print(ans)


def f(H, W, S):
    """
    c1 to c2:
        c1: black(#), c2: white(.)
        c1 - not c1 - c1 - c2

    上下左右に隣り合うマスへの移動を繰り返し
    a to b: N * N = 400 ^ 2 = 1.6 * 10^5
    Nb to Nw == Nw to Nb

    あるマスからどこまで進めるか（直線）
    North <-> South
    West  <-> East

    a to b: ok
    b to c: ok
    a to c: ok (3段論法)

    """
    # south, north, east, west
    d = zip([0, 0, 1, -1],
            [1, -1, 0, 0])
    d = list(d)
    to = {"#": ".", ".": "#"}

    b = []
    for _ in range(H):
        b2 = []
        for _ in range(W):
            b2.append([None] * 4)
        b.append(b2)

    blacks = {}
    for y in range(H):
        for x in range(W):
            src = S[y][x]
            if src == "#":
                blacks[(y, x)] = -1

            for i, (dx, dy) in enumerate(d):
                nx = x + dx
                ny = y + dy

                valid = 0 <= nx < W and 0 <= ny < H
                if not valid:
                    continue

                if S[ny][nx] == to[src]:
                    b[y][x][i] = (ny, nx)

    ans = 0
    # #からなので、候補
    for (y, x), n in blacks.items():
        # 黒から辿り、１ターンでー候補白を見つけ黒へたどる、次のターンの黒を見つける
        bs = [(y, x)]
        # 辿った黒白のマスをまた辿らないようにする
        used_bs = {}
        used_ws = {}
        while bs:
            by, bx = bs.pop()
            used_bs[(by, bx)] = None

            # 黒から白
            whites = []
            for pos in b[by][bx]:
                if pos and pos not in used_ws:
                    ans += 1
                    whites.append(pos)
                    used_ws[pos] = None

            # 白から黒
            for wy, wx in whites:
                for pos in b[wy][wx]:
                    if pos and pos not in used_bs:
                        bs.append(pos)

    return ans


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
H,W = map(int,input().split())
mat = []
for h in range(H):
    mat.append(list(input()))
#print (mat)
ls_set = []
for h in range(H):
    for w in range(W):
        #print (h,w)
        if w + 1 < W:
            if mat[h][w] != mat[h][w+1]:
                ls_set.append({h*W+w,h*W+w+1})
        if h + 1 < H:
            if mat[h][w] != mat[h+1][w]:
                ls_set.append({h*W+w,(h+1)*W+w})
#print (ls_set)

change = 1
while(change):
    change = 0
    for j in range(len(ls_set)-1):
        ls =  list(range(j+1,len(ls_set)))[::-1]
        for i in ls:
            #print (i)
            if not ls_set[j].isdisjoint(ls_set[i]):
                ls_set[j] = ls_set[j] | ls_set[i]
                ls_set.pop(i)
                change = 1
        #print (ls_set)
ans = 0
for s in ls_set:
    odd = 0
    even = 0
    for i in s:
        if i % 2 == 0:
            even+=1
        else:
            odd+=1
    temp = even*odd
    #print (temp)
    ans += temp
print (ans)

Submission status: Time Limit Exceeded

Solution code:
def dfs(start):
    stack = [start]
    visited = [[0 for j in range(w)] for i in range(h)]
    count = 0
    visited_b = []
    while stack:
        y,x,c = stack.pop()
        if x > 0 and visited[y][x-1] == 0:
            point = s[y][x-1]
            if point != c:
                stack.append((y, x-1, point))
                visited[y][x-1] = 1
                if point == ".":
                    count += 1
                else:
                    visited_b.append((y, x-1))
        if x < w-1 and visited[y][x+1] == 0:
            point = s[y][x+1]
            if point != c:
                stack.append((y, x+1, point))
                visited[y][x+1] = 1
                if point == ".":
                    count += 1
                else:
                    visited_b.append((y, x+1))
        if y > 0 and visited[y-1][x] == 0:
            point = s[y-1][x]
            if point != c:
                stack.append((y-1, x, point))
                visited[y-1][x] = 1
                if point == ".":
                    count += 1
                else:
                    visited_b.append((y-1, x))
        if y < h-1 and visited[y+1][x] == 0:
            point = s[y+1][x]
            if point != c:
                stack.append((y+1, x, point))
                visited[y+1][x] = 1
                if point == ".":
                    count += 1
                else:
                    visited_b.append((y+1, x))
    return count, visited_b


h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
black = [[-1 for j in range(w)] for i in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            if black[i][j] == -1:
                count, visited_b = dfs((i, j, "#"))
                for v in visited_b:
                    y, x = v
                    black[y][x] = count
            ans += max(black[i][j], 0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
H, W = list(map(int, input().split()))
Sn = [input() for _ in range(H)]

def func(h,w): # 黒のみ
    map = [[0 for _ in range(W)] for _ in range(H)]
    que = deque()
    que.append((h,w))
    while len(que) > 0:
        xh,xw = que.popleft()
        if map[xh][xw] == 0:
            map[xh][xw] = Sn[xh][xw]
        else:
            continue
        # 左
        if xw - 1 >= 0:
            if Sn[xh][xw] != Sn[xh][xw-1] and map[xh][xw-1] == 0:
                que.append((xh, xw-1))
        # 上
        if xh - 1 >= 0:
            if Sn[xh][xw] != Sn[xh-1][xw] and map[xh-1][xw] == 0:
                que.append((xh-1, xw))
        # 右
        if xw + 1 < W:
            if Sn[xh][xw] != Sn[xh][xw+1] and map[xh][xw+1] == 0:
                que.append((xh, xw+1))
        # 下
        if xh + 1 < H:
            if Sn[xh][xw] != Sn[xh+1][xw] and map[xh+1][xw] == 0:
                que.append((xh+1, xw))

    return map
    # cnt = 0
    # for i in range(H):
    #     for j in range(W):
    #         if map[i][j] == ".":
    #             cnt += 1
    # return cnt

cnt = 0
visited = [[0 for _ in range(W)] for _ in range(H)]

for i in range(H):
    for j in range(W):
        if Sn[i][j] == "#" and visited[i][j]==0:
            ret = func(i,j)
            b_cnt = 0
            w_cnt = 0
            for i2 in range(H):
                for j2 in range(W):
                    if ret[i2][j2] == "#":
                        b_cnt += 1
                        visited[i2][j2] = 1
                    elif ret[i2][j2] == ".":
                        w_cnt += 1
                        visited[i2][j2] = 1

            cnt += b_cnt*w_cnt
            
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)


class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n + 1)]
        self.rank = [0 for _ in range(n + 1)]
        self.size = [1] * (n + 1)

    def find(self, x):
        # If x is root
        if self.parent[x] == x:
            return x
        # If x is not root, search again by using x's parent
        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:
            return
        # Make an edge from the root of lower tree to the root of higher tree
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.size[y] += self.size[x]
        else:
            self.parent[y] = x
            self.size[x] += self.size[y]
            # If the height of tree the tree is the same, increase one of the heights by 1
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    def get_size(self, x):
        return self.size[self.find(x)]


H, W = map(int, input().split())
s_list = []
for i in range(H):
    s_list.append(input())
check = [[0 for _ in range(W)] for _ in range(H)]

brack_list = set()
check = [False] * (H*W+1)
union_find = UnionFind(H * W)
for i in range(H):
    for j in range(W):
        if s_list[i][j] == "#":
            brack_list.add(i * W + j)
            check[i * W + j] = True
            if i - 1 >= 0 and s_list[i - 1][j] == ".":
                union_find.union(i * W + j, (i - 1) * W + j)
            if i + 1 < H and s_list[i + 1][j] == ".":
                union_find.union(i * W + j, (i + 1) * W + j)
            if j - 1 >= 0 and s_list[i][j - 1] == ".":
                union_find.union(i * W + j, i * W + j - 1)
            if j + 1 < W and s_list[i][j + 1] == ".":
                union_find.union(i * W + j, i * W + j + 1)
count = 0

for b in brack_list:
    p = union_find.find(b)
    for i, j in enumerate(union_find.parent):
        if check[i]:
            continue
        if j == p:
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import numpy as np

def solve():
    H, W  = map(int,input().split())
    S = list()
    V1 = set()
    V2 = set()
    E =  dict()
    for i in range(H):
        s = input()
        for j, a in enumerate(s):
            if a == '#':
                V1.add((i,j))
                U = {(i-1,j),(i,j-1)}&V2
                E[(i,j)] = U
                for u in list(U):
                    E[u] |= {(i,j)}
            else:
                V2.add((i,j))
                U = {(i-1,j),(i,j-1)}&V1
                E[(i,j)] = U
                for u in list(U):
                    E[u] |= {(i,j)}

    W = set()
    res = 0
    for v in V1:
        X, Y =  {v}, set() 
        if v in W:
            continue
        while X:
            w = X.pop()
            Y.add(w)
            W.add(w)
            X |= set(E[w])-Y
        res += len(Y&set(V1))*len(Y&set(V2))
    return str(res)

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
H, W = list(map(int, input().split()))
Sn = [input() for _ in range(H)]

def func(h,w): # 黒のみ
    map = [[0 for _ in range(W)] for _ in range(H)]
    que = deque()
    que.append((h,w))
    while len(que) > 0:
        xh,xw = que.popleft()
        map[xh][xw] = Sn[xh][xw]
        # 左
        if xw - 1 >= 0:
            if Sn[xh][xw] != Sn[xh][xw-1] and map[xh][xw-1] == 0:
                que.append((xh, xw-1))
        # 上
        if xh - 1 >= 0:
            if Sn[xh][xw] != Sn[xh-1][xw] and map[xh-1][xw] == 0:
                que.append((xh-1, xw))
        # 右
        if xw + 1 < W:
            if Sn[xh][xw] != Sn[xh][xw+1] and map[xh][xw+1] == 0:
                que.append((xh, xw+1))
        # 下
        if xh + 1 < H:
            if Sn[xh][xw] != Sn[xh+1][xw] and map[xh+1][xw] == 0:
                que.append((xh+1, xw))

    return map
    # cnt = 0
    # for i in range(H):
    #     for j in range(W):
    #         if map[i][j] == ".":
    #             cnt += 1
    # return cnt

cnt = 0
visited = [[0 for _ in range(W)] for _ in range(H)]

for i in range(H):
    for j in range(W):
        if Sn[i][j] == "#" and visited[i][j]==0:
            ret = func(i,j)
            b_cnt = 0
            w_cnt = 0
            for i2 in range(H):
                for j2 in range(W):
                    if ret[i2][j2] == "#":
                        b_cnt += 1
                        visited[i2][j2] = 1
                    elif ret[i2][j2] == ".":
                        w_cnt += 1
                        visited[i2][j2] = 1

            cnt += b_cnt*w_cnt
            
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)


class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n + 1)]
        self.rank = [0 for _ in range(n + 1)]
        self.size = [1] * (n + 1)

    def find(self, x):
        # If x is root
        if self.parent[x] == x:
            return x
        # If x is not root, search again by using x's parent
        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:
            return
        # Make an edge from the root of lower tree to the root of higher tree
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.size[y] += self.size[x]
        else:
            self.parent[y] = x
            self.size[x] += self.size[y]
            # If the height of tree the tree is the same, increase one of the heights by 1
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    def get_size(self, x):
        return self.size[self.find(x)]


H, W = map(int, input().split())
s_list = []
for i in range(H):
    s_list.append(input())
check = [[0 for _ in range(W)] for _ in range(H)]

brack_list = set()
union_find = UnionFind(H * W)
for i in range(H):
    for j in range(W):
        if s_list[i][j] == "#":
            brack_list.add(i * W + j)
            if i - 1 >= 0 and s_list[i - 1][j] == ".":
                union_find.union(i * W + j, (i - 1) * W + j)
            if i + 1 < H and s_list[i + 1][j] == ".":
                union_find.union(i * W + j, (i + 1) * W + j)
            if j - 1 >= 0 and s_list[i][j - 1] == ".":
                union_find.union(i * W + j, i * W + j - 1)
            if j + 1 < W and s_list[i][j + 1] == ".":
                union_find.union(i * W + j, i * W + j + 1)
count = 0

for b in brack_list:
    p = union_find.find(b)
    for i, j in enumerate(union_find.parent):
        if i in brack_list:
            continue
        if j == p:
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H,W=map(int, raw_input().split() )
S=[ raw_input() for i in range(H) ] 


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


ret=0
q = deque([]) 


def dfs(x,y,current):
	ret=0
	V=[ [ 0 for i in range(W) ] for j in range(H) ]
	V[x][y]=1
	q.append( (x,y,current) )

	while q:
		x,y,current=q.pop()
		if S[x][y]==".":
			ret+=1

		for dx,dy in D:
			if 0<=x+dx<H and 0<=y+dy<W:
				if V[x+dx][y+dy]==0 and S[x+dx][y+dy] != current:
					if (x+dx, y+dy, S[x+dx][y+dy] ):
						V[x+dx][y+dy]=1
						q.append( (x+dx, y+dy, S[x+dx][y+dy] ) )
	return ret



ans=0
for x in range(H):
	for y in range(W):
		if S[x][y]=="#":
			ret=0
			q = deque([]) 
			V=[ [ 0 for i in range(W) ] for j in range(H) ]
			ans+=dfs(x,y, "#")

print ans

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)


class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n + 1)]
        self.rank = [0 for _ in range(n + 1)]
        self.size = [1] * (n + 1)

    def find(self, x):
        # If x is root
        if self.parent[x] == x:
            return x
        # If x is not root, search again by using x's parent
        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:
            return
        # Make an edge from the root of lower tree to the root of higher tree
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.size[y] += self.size[x]
        else:
            self.parent[y] = x
            self.size[x] += self.size[y]
            # If the height of tree the tree is the same, increase one of the heights by 1
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    def get_size(self, x):
        return self.size[self.find(x)]


H, W = map(int, input().split())
s_list = []
for i in range(H):
    s_list.append(input())
check = [[0 for _ in range(W)] for _ in range(H)]

brack_list = []
union_find = UnionFind(H * W)
for i in range(H):
    for j in range(W):
        if s_list[i][j] == "#":
            brack_list.append(i * W + j)
            if i - 1 >= 0 and s_list[i - 1][j] == ".":
                union_find.union(i * W + j, (i - 1) * W + j)
            if i + 1 < H and s_list[i + 1][j] == ".":
                union_find.union(i * W + j, (i + 1) * W + j)
            if j - 1 >= 0 and s_list[i][j - 1] == ".":
                union_find.union(i * W + j, i * W + j - 1)
            if j + 1 < W and s_list[i][j + 1] == ".":
                union_find.union(i * W + j, i * W + j + 1)
count = 0
for b in brack_list:
    p = union_find.find(b)
    for i, j in enumerate(union_find.parent):
        if i in brack_list:
            continue
        if j == p:
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue as Qe

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

D = [[-1 for j in range(W)] for i in range(H)]
S = [input() for i in range(H)]

D[0][0] = 1
q = Qe()
q.put((0,0))
White = 1 if S[0][0] == "." else 0
Black = 1 if S[0][0] == "#" else 0
ans = 0

def_h = 0
def_w = 0
while not q.empty():
    h,w = q.get()
    #print(h,w,White,Black)
    if h-1>=0 and S[h][w]!=S[h-1][w] and D[h-1][w] == -1: #up
        if S[h-1][w]=="#":
            ans += White
            Black += 1
        else:
            ans += Black
            White += 1
        D[h-1][w] = 1
        q.put((h-1,w))
    if h+1<H and S[h][w]!=S[h+1][w] and D[h+1][w] == -1: #down
        if S[h+1][w]=="#":
            ans += White
            Black += 1
        else:
            ans += Black
            White += 1
        D[h+1][w] = 1
        q.put((h+1,w))
    if w-1>=0 and S[h][w]!=S[h][w-1] and D[h][w-1] == -1: #left
        if S[h][w-1]=="#":
            ans += White
            Black += 1
        else:
            ans += Black
            White += 1
        D[h][w-1] = 1
        q.put((h,w-1))
    if w+1<W and S[h][w]!=S[h][w+1] and D[h][w+1] == -1: #right
        if S[h][w+1]=="#":
            ans += White
            Black += 1
        else:
            ans += Black
            White += 1
        D[h][w+1] = 1
        q.put((h,w+1))
    if q.empty():
        okei = False
        for i in range(def_h,H):
            for j in range(W):
                if D[i][j] == -1:
                    D[i][j] = 1
                    q.put((i,j))
                    White = 1 if S[i][j] == "." else 0
                    Black = 1 if S[i][j] == "#" else 0
                    def_h,def_w = i,j
                    okei = True
                    break
            if okei: break
                
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue
H, W = map(int, input().split())
S = [list(input()) for h in range(H)]
 
Search = [(-1, 0), (0, -1), (1, 0), (0, 1)]
Total = 0
BlackVis = [[False for w in range(W)] for h in range(H)]
for h in range(H):
    for w in range(W):
        if S[h][w] == "#":
            if not BlackVis[h][w]:
                Visited = [[False for w in range(W)] for h in range(H)]
                Visited[h][w] = True
                Q = queue.Queue()
                Q.put((h,w))
                Mult = 1
                Count = 0
                while not Q.empty():
                    now = Q.get()
                    for s in Search:
                        nh, nw = now[0] + s[0], now[1]+s[1]
                        if 0 <= nh < H and 0 <= nw < W:
                            if S[now[0]][now[1]] != S[nh][nw] and not Visited[nh][nw]:
                                Visited[nh][nw] = True
                                Q.put((nh, nw))
                                if S[nh][nw] == ".":
                                    Count += 1
                                else:
                                    BlackVis[nh][nw] = True
                                    Mult += 1
                Total += Count * Mult 
print(Total)