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:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

# AISing Programming Contest 2019：C - Alternating Path
C = '#.'
CR = {'#':0, '.':1}

H, W = [int(i) for i in raw_input().strip().split(' ')]
S = []
for _ in range(H):
    # S.append(raw_input().strip())
    S.append([CR[c] for c in raw_input().strip()])


def find(h, w, sumi):
    while True:
        if sumi[h][w] == False:
            return (h, w)
        w += 1
        if w >= W:
            w = 0
            h += 1
            if h >= H:
                return None
    return None


'''
def chain((h, w), t, c, sumi):
    if 0 <= h < H and 0 <= w < W:
        pass
    else:
        return c
    if sumi[h][w]:
        return c
    if S[h][w] == t:
        sumi[h][w] = True
        c[t] += 1
        for ptr in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
            c = chain((h+ptr[0], w+ptr[1]), 1-t, c, sumi)
        return c
    return c
'''


def find_chain((hh, ww), t, sumi):
    dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    chain_sumi = [[False for _ in range(W)] for _ in range(H)]
    h, w = hh, ww
    sumi[h][w] = True
    chain_sumi[h][w] = True
    c = [0, 0]
    c[t] = 1
    d = 0
    stack = []
    while True:
        while True:
            if d >= 4:
                break
            hd = h + dd[d][0]
            wd = w + dd[d][1]
            d += 1
            if 0 <= hd < H and 0 <= wd < W:
                if not chain_sumi[hd][wd]:
                    td = S[hd][wd]
                    if td == t-((hh+ww+hd+wd)&1):
                        sumi[hd][wd] = True
                        chain_sumi[hd][wd] = True
                        c[td] += 1
                        stack.append([h, w, d])
                        h , w, d = hd, wd, 0
        if len(stack) == 0:
            break
        h, w, d = stack.pop()
    # print 'sumi :', sumi
    # print 'chain_sumi :', chain_sumi
    return c


def main():
    sumi = [[False for _ in range(W)] for _ in range(H)]
    h, w = 0, 0
    n = 0
    while True:
        # print 'sumi:', sumi
        result = find(h, w, sumi)
        if not result:
            break
        h, w = result[0], result[1]
        # print 'found:', h, w
        c = find_chain((h, w), S[h][w], sumi)
        # print c
        n += c[0] * c[1]
    print n


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

# AISing Programming Contest 2019：C - Alternating Path

H, W = [int(i) for i in raw_input().strip().split(' ')]
S = []
for _ in range(H):
    S.append(raw_input().strip())
C = '#.'
CR = {'#':0, '.':1}


def find(h, w, sumi):
    while True:
        if sumi[h][w] == False:
            return (h, w)
        w += 1
        if w >= W:
            w = 0
            h += 1
            if h >= H:
                return None
    return None


'''
def chain((h, w), t, c, sumi):
    if 0 <= h < H and 0 <= w < W:
        pass
    else:
        return c
    if sumi[h][w]:
        return c
    if S[h][w] == C[t]:
        sumi[h][w] = True
        c[t] += 1
        for ptr in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
            c = chain((h+ptr[0], w+ptr[1]), 1-t, c, sumi)
        return c
    return c
'''


def find_chain((hh, ww), t, sumi):
    dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    chain_sumi = [[False for _ in range(W)] for _ in range(H)]
    h, w = hh, ww
    sumi[h][w] = True
    chain_sumi[h][w] = True
    c = [0, 0]
    c[t] = 1
    d = 0
    stack = []
    while True:
        while True:
            if d >= 4:
                break
            hd = h + dd[d][0]
            wd = w + dd[d][1]
            d += 1
            if 0 <= hd < H and 0 <= wd < W:
                if not chain_sumi[hd][wd]:
                    td = CR[S[hd][wd]]
                    if td == t-((hh+ww+hd+wd)&1):
                        sumi[hd][wd] = True
                        chain_sumi[hd][wd] = True
                        c[td] += 1
                        stack.append([h, w, d])
                        h , w, d = hd, wd, 0
        if len(stack) == 0:
            break
        h, w, d = stack.pop()
    # print 'sumi :', sumi
    # print 'chain_sumi :', chain_sumi
    return c


def main():
    sumi = [[False for _ in range(W)] for _ in range(H)]
    h, w = 0, 0
    n = 0
    while True:
        # print 'sumi:', sumi
        result = find(h, w, sumi)
        if not result:
            break
        h, w = result[0], result[1]
        # print 'found:', h, w
        c = find_chain((h, w), CR[S[h][w]], sumi)
        # print c
        n += c[0] * c[1]
    print n


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue
H, W = map(int, input().split())
S = [list(map(int, input().replace(".", "0").replace("#","1"))) for h in range(H)]

Search = [(-1, 0), (0, -1), (1, 0), (0, 1)]
Total = 0
Visited = [[False for w in range(W)] for h in range(H)]
for h in range(H):
    for w in range(W):
        if not Visited[h][w]:
            Visited[h][w] = True
            Color = ([1, 0] if S[h][w] == 0 else [0, 1])
            Q = queue.Queue()
            Q.put((h, w, S[h][w]))
            while not Q.empty():
                nh, nw, nc = Q.get()
                for s in Search:
                    nexth, nextw = nh + s[0], nw + s[1]
                    if 0 <= nexth < H and 0 <= nextw < W:
                        if not Visited[nexth][nextw] and S[nexth][nextw] != nc:
                            nextc = S[nexth][nextw]
                            Visited[nexth][nextw] = True
                            Q.put((nexth, nextw, nextc))
                            Color[nextc] += 1
            Total += Color[0] * Color[1]

print(Total)

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
Visited = [[False for w in range(W)] for h in range(H)]
for h in range(H):
    for w in range(W):
        if not Visited[h][w]:
            Visited[h][w] = True
            if S[h][w] == ".": Black, White = 0, 1
            else: Black, White = 1, 0
            Q = queue.Queue()
            Q.put((h, w))
            while not Q.empty():
                now = Q.get()
                nh, nw = now[0], now[1]
                for s in Search:
                    nexth, nextw = nh + s[0], nw + s[1]
                    if 0 <= nexth < H and 0 <= nextw < W:
                        if not Visited[nexth][nextw] and S[nexth][nextw] != S[nh][nw]:
                            Visited[nexth][nextw] = True
                            Q.put((nexth, nextw))
                            if S[nexth][nextw] == ".": White += 1
                            else: Black += 1
            Total += Black * White

print(Total)

Submission status: Time Limit Exceeded

Solution code:
#encoding:utf-8

import numpy as np
import sys
sys.setrecursionlimit(1000000)

H, W = map(int, input().split())
S = []
for i in range(H):
    s = list(input())
    S.append(s)

S_ = np.array(S)

def count_answer(x,y,num_b,num_w):
    # print(used)

    if S_[x][y] == "#":
        num_b += 1
    else:
        num_w += 1
    used[x][y] = 1
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    # print("x,y:",x,y)
    for i in range(4):
        next_x = x + dx[i]
        next_y = y + dy[i]
        # print(next_x,next_y)
        if next_x == -1 or next_y == -1 or next_x >= H or next_y >= W:
            pass
        elif used[next_x,next_y] == 1:
            pass
        elif S_[next_x][next_y] != S_[x][y]:
            num_b,num_w = count_answer(next_x,next_y,num_b,num_w)
    return num_b,num_w

answer = 0
used = np.zeros((H,W))
for i in range(H):
    for j in range(W):
        if used[i][j] == 1:
            continue
        num_b = 0
        num_w = 0
        if S_[i,j] == "#":
            num_b,num_w  = count_answer(i,j,num_b,num_w)
            answer += num_b*num_w
print(answer)

Submission status: Time Limit Exceeded

Solution code:
#encoding:utf-8

import numpy as np
import sys
sys.setrecursionlimit(1000000)

H, W = map(int, input().split())
S = []
for i in range(H):
    s = list(input())
    S.append(s)

S_ = np.array(S)

def count_answer(x,y,num_b,num_w):
    # print(used)
    # global num_b,num_w
    if S_[x][y] == "#":
        num_b += 1
    else:
        num_w += 1
    used[x][y] = 1
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    # print("x,y:",x,y)
    for i in range(4):
        next_x = x + dx[i]
        next_y = y + dy[i]
        # print(next_x,next_y)
        if next_x == -1 or next_y == -1 or next_x >= H or next_y >= W:
            pass
        elif used[next_x,next_y] == 1:
            pass
        elif S_[next_x][next_y] != S_[x][y]:
            num_b,num_w = count_answer(next_x,next_y,num_b,num_w)
    return num_b,num_w

answer = 0
used = np.zeros((H,W))
for i in range(H):
    for j in range(W):
        if used[i][j] == 1:
            continue
        num_b = 0
        num_w = 0
        if S_[i,j] == "#":
            num_b,num_w  = count_answer(i,j,num_b,num_w)
            answer += num_b*num_w
print(answer)

Submission status: Time Limit Exceeded

Solution code:
#encoding:utf-8

import numpy as np
import sys
sys.setrecursionlimit(1000000)

H, W = map(int, input().split())
S = []
for i in range(H):
    s = list(input())
    S.append(s)

S_ = np.array(S)

def count_answer(x,y,num_b,num_w):
    # print(used)
    # global num_b,num_w
    count = 0
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    # print("x,y:",x,y)
    for i in range(4):
        next_x = x + dx[i]
        next_y = y + dy[i]
        # print(next_x,next_y)

        if next_x == -1 or next_y == -1:
            pass
        elif next_x >= H or next_y >= W:
            pass
        elif used[next_x][next_y] == 1:
            pass
        elif S_[next_x][next_y] != S_[x][y]:
            used[next_x][next_y] = 1
            if S_[next_x][next_y] == "#":
                num_b += 1
            else:
                num_w += 1
            num_b,num_w = count_answer(next_x,next_y,num_b,num_w)
    return num_b,num_w

answer = 0
used = np.zeros((H,W))
for i in range(H):
    for j in range(W):
        if used[i][j] == 1:
            pass
        elif S_[i,j] == "#":
            num_b = 0
            num_w = 0
            num_b,num_w  = count_answer(i,j,num_b,num_w)
            answer += num_b*num_w
print(answer)

Submission status: Time Limit Exceeded

Solution code:
#encoding:utf-8

import numpy as np
import sys
sys.setrecursionlimit(1000000)

H, W = map(int, input().split())
S = []
for i in range(H):
    s = list(input())
    S.append(s)

S_ = np.array(S)

def count_answer(x,y,num_b,num_w):
    # print(used)
    # global num_b,num_w
    count = 0
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    # print("x,y:",x,y)
    for i in range(4):
        next_x = x + dx[i]
        next_y = y + dy[i]
        # print(next_x,next_y)
        if next_x == -1 or next_y == -1:
            pass
        elif next_x >= H or next_y >= W:
            pass
        elif used[next_x][next_y] == 1:
            pass
        elif S_[next_x][next_y] != S_[x][y]:
            used[next_x][next_y] = 1
            if S_[next_x][next_y] == "#":
                num_b += 1
            else:
                num_w += 1
            num_b,num_w = count_answer(next_x,next_y,num_b,num_w)
    return num_b,num_w

answer = 0
used = np.zeros((H,W))
for i in range(H):
    for j in range(W):
        if used[i][j] == 1:
            pass
        elif S_[i,j] == "#":
            num_b = 0
            num_w = 0
            num_b,num_w  = count_answer(i,j,num_b,num_w)
            answer += num_b*num_w
print(answer)

Submission status: Time Limit Exceeded

Solution code:
#encoding:utf-8

import numpy as np
import sys
sys.setrecursionlimit(1000000)

H, W = map(int, input().split())
S = []
for i in range(H):
    s = list(input())
    S.append(s)

S_ = np.array(S)

memory = {}

def count_answer(x,y):
    count = 0
    actions = {0:[-1,0],1:[0,1],2:[1,0],3:[0,-1]}
    # print("x,y:",x,y)
    for action0 in range(4):
        next_x = x + actions[action0][0]
        next_y = y + actions[action0][1]
        # print(next_x,next_y)
        if next_x == -1 or next_y == -1:
            pass
        elif next_x >= H or next_y >= W:
            pass
        elif [next_x,next_y] in reach_position:
            pass
        elif S_[next_x,next_y] == ".":
            reach_position.append([next_x,next_y])
            for action in range(4):
                next_next_x = next_x +actions[action][0]
                next_next_y = next_y +actions[action][1]
                # print(next_next_x,next_next_y)
                if next_next_x == -1 or next_next_y == -1:
                    pass
                elif next_next_x >= H or next_next_y >= W:
                    pass
                elif S_[next_next_x,next_next_y] == "#":

                    memory_key = str(next_next_x)+str(next_next_y)
                    if memory_key in memory.keys():
                        tem_poss = memory[memory_key]
                    else:
                        tem_poss = count_answer(next_next_x,next_next_y)
                    for tem_pos in tem_poss:
                        if tem_pos in reach_position:
                            pass
                        else:
                            reach_position.append(tem_pos)
                    # reach_position = reach_position and tem_poss
    memory[str(x)+str(y)] = reach_position
    # memory[[x,y]] = reach_position
    return reach_position

answer = 0
for i in range(H):
    for j in range(W):
        if S_[i,j] == "#":
            reach_position = []
            reach_position = count_answer(i,j)
            answer += len(reach_position)
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import queue
from heapq import heappush, heappop

class Graph:

    INF = float('inf')
    
    def __init__(self,v_num,is_directed = False):
        self.is_directed = is_directed
        self.v_num = v_num
        self.E = []
        self.v_s_list = [[] for i in range(self.v_num)]
        
    def appendEdge(self,v1,v2,weight=1):
        if max(v1,v2,self.v_num-1)>=self.v_num or min(v1,v2)<0:
            print("ERROR: The vertex ID is wrong.")
            return False

        self.E.append([v1,v2,weight])
        
        if self.is_directed:
            self.v_s_list[v1].append([v2,weight])
        else:
            self.v_s_list[v1].append([v2,weight])
            self.v_s_list[v2].append([v1,weight])
        
        
    def BFS(self,v,usage="SSSP"):
        is_processed = [False for i in range(self.v_num)]
        distance_list = [Graph.INF for i in range(self.v_num)]
        Q = queue.Queue()
        Q.put(v)
        is_processed[v]=True
        distance_list[v] = 0
        while not Q.empty():
            v1 = Q.get()
            for v2 in self.v_s_list[v1]:
                if not is_processed[v2[0]]:
                    is_processed[v2[0]] = True
                    distance_list[v2[0]] = min(distance_list[v1]+1,distance_list[v2[0]])
                    Q.put(v2[0])
        if usage=="SSSP":
            return distance_list
        elif usage=="ConnectedComponent":
            cc_list = []
            for i in range(self.v_num):
                if is_processed[i]:
                    cc_list.append(i)
            return cc_list

    def getSSSPwithBFS(self,v):
        return self.BFS(v,"SSSP")
        
    def getConnectedComponent(self,v):
        return self.BFS(v,"ConnectedComponent")
        
    def getSSSPwithBellmanFord(self,v):
        distance_list = [Graph.INF for i in range(self.v_num)]
        distance_list[v] = 0
        pre_list = [None for i in range(self.v_num)]

        for i in range(self.v_num-1):
            for e in self.E:
                v1 = e[0]
                v2 = e[1]
                d = e[2]
                if distance_list[v2] > distance_list[v1] + d:
                    distance_list[v2] = distance_list[v1] + d
                    pre_list[v2] = v1
                    
        negative_loop_list = [False for i in range(self.v_num)]
        
        for i in range(self.v_num):
            for e in self.E:
                v1 = e[0]
                v2 = e[1]
                d = e[2]
                if d + distance_list[v1] < distance_list[v2]:
                    distance_list[v2] = d + distance_list[v1]
                    pre_list[v2] = v1
                    negative_loop_list[v2] = True
        
        return distance_list, pre_list, negative_loop_list

    def getSSSPwithDijkstra(self,v):
        distance_list = [Graph.INF for i in range(self.v_num)]
        distance_list[v] = 0
        pre_list = [None for i in range(self.v_num)]
        
        PQ = []
        for i in range(self.v_num):
            heappush(PQ,(distance_list[i],i))
        while len(PQ)>0:
            d,v1 = heappop(PQ)
            for v2 in self.v_s_list[v1]:
                if distance_list[v2[0]] > d + v2[1]:
                    distance_list[v2[0]] = d + v2[1]
                    pre_list[v2[0]] = v1
                    heappush(PQ,(distance_list[v2[0]],v2[0]))
        return distance_list,pre_list

H,W = list(map(int,input().split()))
S = []
for i in range(H):
    S.append(input())
G = Graph(H*W)
for i in range(H):
    for j in range(W):
        if i!=0 and i!=H-1:
            if S[i][j]!=S[i+1][j]:
                G.appendEdge(i*W+j,(i+1)*W+j)
            if S[i][j]!=S[i-1][j]:
                G.appendEdge(i*W+j,(i-1)*W+j)
        elif i!=0 and i==H-1:
            if S[i][j]!=S[i-1][j]:
                G.appendEdge(i*W+j,(i-1)*W+j)
        elif i==0 and i!=H-1:
            if S[i][j]!=S[i+1][j]:
                G.appendEdge(i*W+j,(i+1)*W+j)

        if j!=0 and j!=W-1:
            if S[i][j]!=S[i][j+1]:
                G.appendEdge(i*W+j,i*W+j+1)
            if S[i][j]!=S[i][j-1]:
                G.appendEdge(i*W+j,i*W+j-1)
        elif j!=0 and j==W-1:
            if S[i][j]!=S[i][j-1]:
                G.appendEdge(i*W+j,i*W+j-1)
        elif j==0 and j!=W-1:
            if S[i][j]!=S[i][j+1]:
                G.appendEdge(i*W+j,i*W+j+1)
res=0
C_list = [True for i in range(H*W)]
for i in range(H*W):
    if C_list[i]:
        con_list = G.getConnectedComponent(i)
        black_count=0
        white_count=0
        for c in con_list:
            if S[c//W][c%W]=="#":
                black_count+=1
            else:
                white_count+=1
            C_list[c]=False
        res+= black_count*white_count
print(res)

Submission status: Time Limit Exceeded

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

def m():
    H, W = map(int, input().split())
    S = []
    for i in range(H):
        S.append(list(input()))

    graph = [[[]for _ in range(W)] for _ in range(H)]
    visited = [[0 for _ in range(W)] for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if S[i][j] == ".":
                continue
            if S[max(i - 1, 0)][j] == ".":
                graph[max(i - 1, 0)][j].append((i,j))
                graph[i][j].append((max(i - 1, 0),j))

            if S[min(i+1, H-1)][j] == ".":
                graph[min(i + 1, H - 1)][j].append((i,j))
                graph[i][j].append((min(i + 1, H - 1),j))

            if S[i][max(j - 1, 0)] == ".":
                graph[i][max(j - 1, 0)].append((i,j))
                graph[i][j].append((i,max(j - 1, 0)))

            if S[i][min(j+1, W-1)] == ".":
                graph[i][min(j + 1, W - 1)].append((i,j))
                graph[i][j].append((i,min(j+1, W-1)))

    bw = [0] * 2
    def dfs(g):
        for a,b in g:
            if visited[a][b] == 1:
                continue
            visited[a][b] = 1
            if S[a][b] == ".":
                bw[0] += 1
            else:
                bw[1] += 1
            dfs(graph[a][b])

    ans = 0
    for i in range(H):
        for j in range(W):
            if visited[i][j] == 1:
                continue
            bw[0], bw[1] = 0, 0
            dfs(graph[i][j])
            ans += bw[0] * bw[1]

    return ans

print(m())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque

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

def parse(inp):
    H, W = map(int, next(inp).split())
    return np.array([trans([w for w in next(inp).strip()]) for _ in range(H)])

def appender(i, j, H, W, C, S, Q):
    s = S[i, j]
    if i + 1 < H and not C[i+1, j] and np.logical_xor(s, S[i+1, j]):
        Q.append((i + 1, j))
    if i > 0 and not C[i-1, j] and np.logical_xor(s, S[i-1, j]):
        Q.append((i - 1, j))
    if j + 1 < W and not C[i, j+1] and np.logical_xor(s, S[i, j+1]):
        Q.append((i, j + 1))
    if j > 0 and not C[i, j-1] and np.logical_xor(s, S[i, j-1]):
        Q.append((i, j - 1))

def search(S, start, C):
    Q = deque([start])
    H, W = S.shape
    n0 = 0
    n1 = 0
    while Q:
        i, j = Q.popleft()
        if C[i, j]:
            continue
        else:
            C[i, j] = True
            if S[i, j] == 0:
                n0 += 1
            else:
                n1 += 1
            appender(i, j, H, W, C, S, Q)
    return n0, n1


def search_all(S):
    C = np.full_like(S, False).astype(np.bool)
    D = np.full_like(S, 0)
    ret = 0
    for i in range(S.shape[0]):
        for j in range(S.shape[1]):
            if D[i, j] == 0:
                n0, n1 = search(S, (i, j), C)
                D += C
                ret += n1 * n0
                if np.all(D):
                    return ret
                else:
                    C[:, :] = False




import sys
    
print(search_all(parse(sys.stdin)))

Submission status: Time Limit Exceeded

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

def m():
    H, W = map(int, input().split())
    S = []
    for i in range(H):
        S.append(list(input()))

    graph = [[[]for _ in range(W)] for _ in range(H)]
    visited = []
    for i in range(H):
        for j in range(W):
            if S[i][j] == ".":
                continue
            if S[max(i - 1, 0)][j] == ".":
                graph[max(i - 1, 0)][j].append((i,j))
                graph[i][j].append((max(i - 1, 0),j))

            if S[min(i+1, H-1)][j] == ".":
                graph[min(i + 1, H - 1)][j].append((i,j))
                graph[i][j].append((min(i + 1, H - 1),j))

            if S[i][max(j - 1, 0)] == ".":
                graph[i][max(j - 1, 0)].append((i,j))
                graph[i][j].append((i,max(j - 1, 0)))

            if S[i][min(j+1, W-1)] == ".":
                graph[i][min(j + 1, W - 1)].append((i,j))
                graph[i][j].append((i,min(j+1, W-1)))

    bw = [0] * 2
    def dfs(g):
        for a,b in g:
            if (a,b) in visited:
                continue
            visited.append((a,b))
            if S[a][b] == ".":
                bw[0] += 1
            else:
                bw[1] += 1
            dfs(graph[a][b])

    ans = 0
    for i in range(H):
        for j in range(W):
            if (i,j) in visited:
                continue
            bw[0], bw[1] = 0, 0
            dfs(graph[i][j])
            ans += bw[0] * bw[1]

    return ans

print(m())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque

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

def parse(inp):
    H, W = map(int, next(inp).split())
    return np.array([trans([w for w in next(inp).strip()]) for _ in range(H)])

def appender(i, j, H, W, C, S, Q):
    if i + 1 < H and not C[i+1, j] and S[i, j] != S[i+1, j]:
        Q.append((i + 1, j))
    if i > 0 and not C[i-1, j] and S[i, j] != S[i-1, j]:
        Q.append((i - 1, j))
    if j + 1 < W and not C[i, j+1] and S[i, j] != S[i, j+1]:
        Q.append((i, j + 1))
    if j > 0 and not C[i, j-1] and S[i, j] != S[i, j-1]:
        Q.append((i, j - 1))

def search(S, start, C):
    Q = deque([start])
    H, W = S.shape
    n0 = 0
    n1 = 0
    while Q:
        i, j = Q.popleft()
        if C[i, j]:
            continue
        else:
            C[i, j] = True
            if S[i, j] == 0:
                n0 += 1
            else:
                n1 += 1
            appender(i, j, H, W, C, S, Q)
    return n0, n1


def search_all(S):
    C = np.full_like(S, False).astype(np.bool)
    D = np.full_like(S, 0)
    ret = 0
    for i in range(S.shape[0]):
        for j in range(S.shape[1]):
            if D[i, j] == 0:
                n0, n1 = search(S, (i, j), C)
                D += C
                ret += n1 * n0
                if np.all(D):
                    return ret
                else:
                    C[:, :] = False



import sys
    
print(search_all(parse(sys.stdin)))

Submission status: Time Limit Exceeded

Solution code:
class DisjointSet:
    def __init__(self):
        self.rank = {}
        self.p = {}

    def makeSet(self, x):
        self.p[x] = x
        self.rank[x] = 0

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

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x, y):
        if(self.rank[x] > self.rank[y]):
            self.p[y] = x
        else:
            self.p[x] = y
            if(self.rank[x] == self.rank[y]):
                self.rank[y] += 1

    def findSet(self, x):
        if(x != self.p[x]):
            self.p[x] = self.findSet(self.p[x])
        return self.p[x]

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

ds = DisjointSet()
for i in range(H):
    for j in range(W):
        ds.makeSet((i,j))

for i in range(H):
    for j in range(W):
        if i + 1 < H and S[i][j] != S[i+1][j]:
            ds.unite((i,j), (i+1, j))
        if 0 <= i - 1 and S[i][j] != S[i-1][j]:
            ds.unite((i,j), (i-1, j))
        if j + 1 < W and S[i][j] != S[i][j+1]:
            ds.unite((i,j), (i, j+1))
        if 0 <= j - 1 and S[i][j] != S[i][j-1]:
            ds.unite((i,j), (i, j-1))

from collections import defaultdict

c1 = defaultdict(int)
c2 = defaultdict(int)

for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            c1[ds.findSet((i,j))] += 1
        else:
            c2[ds.findSet((i,j))] += 1
ans = 0
for i in c1.keys():
    ans += c1[i] * c2[i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque
import sys

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

def parse(inp):
    H, W = map(int, next(inp).split())
    return np.array([trans([w for w in next(inp).strip()]) for _ in range(H)])

def search(S, start, C):
    Q = deque([start])
    H, W = S.shape
    n0 = 0
    n1 = 0
    while Q:
        i, j = Q.popleft()
        if C[i, j] != 0:
            continue
        else:
            C[i, j] = 1
            if S[i, j] == 0:
                n0 += 1
            else:
                n1 += 1
        if i + 1 < H and C[i+1, j] == 0 and S[i, j] != S[i+1, j]:
            Q.append((i + 1, j))
        if i > 0 and C[i-1, j] == 0 and S[i, j] != S[i-1, j]:
            Q.append((i - 1, j))
        if j + 1 < W and C[i, j+1] == 0 and S[i, j] != S[i, j+1]:
            Q.append((i, j + 1))
        if j > 0 and C[i, j-1] == 0 and S[i, j] != S[i, j-1]:
            Q.append((i, j - 1))
    return n0, n1


def search_all(S):
    C = np.full_like(S, 0)
    D = np.full_like(S, 0)
    ret = 0
    for i in range(S.shape[0]):
        for j in range(S.shape[1]):
            if D[i, j] == 0:
                n0, n1 = search(S, (i, j), C)
                D += C
                ret += n1 * n0
                if np.all(D):
                    return ret
                else:
                    C[:, :] = 0

    
print(search_all(parse(sys.stdin)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque
import sys

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

def parse(inp):
    H, W = map(int, next(inp).split())
    return np.array([trans([w for w in next(inp).strip()]) for _ in range(H)])

def search(S, start):
    Q = deque([start])
    C = np.full_like(S, 0)
    H, W = S.shape
    while Q:
        i, j = Q.popleft()
        if C[i, j] != 0:
            continue
        else:
            C[i, j] = 1
        if i + 1 < H and C[i+1, j] == 0 and S[i, j] != S[i+1, j]:
            Q.append((i + 1, j))
        if i > 0 and C[i-1, j] == 0 and S[i, j] != S[i-1, j]:
            Q.append((i - 1, j))
        if j + 1 < W and C[i, j+1] == 0 and S[i, j] != S[i, j+1]:
            Q.append((i, j + 1))
        if j > 0 and C[i, j-1] == 0 and S[i, j] != S[i, j-1]:
            Q.append((i, j - 1))
    return C

def search_all(S):
    ij = (0, 0)
    D = np.full_like(S, 0)
    ret = 0
    while True:
        C = search(S, ij)
        D += C
        n = np.sum(C)
        n1 = np.sum(C * S)
        n0 = n - n1
        ret += n1 * n0
        ii, jj = np.where(D == 0)
        if len(ii) == 0:
            return ret
        else:
            ij = ii[0], jj[0]

        
    
print(search_all(parse(sys.stdin)))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = list(map(int, input().split()))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
used = [[False for i in range(W)] for j in range(H)]
S = []
for i in range(H):
        S.append(input())
b = 0
w = 0
ans = 0
for i in range(H):
    for j in range(W):
        q = deque()
        used[i][j] = True
        q.append([i, j])
        b = 0
        w = 0
        while len(q) != 0:
            tmp = q.pop()
            if S[tmp[0]][tmp[1]] == '#':
                b += 1
            else:
                w += 1
            for k in range(4):
                if tmp[0] + dx[k] > H - 1 or tmp[1] + dy[k] > W - 1 or tmp[0] + dx[k] < 0 or tmp[1] + dy[k] < 0:
                    continue
                if S[tmp[0] + dx[k]][tmp[1] + dy[k]] == S[tmp[0]][tmp[1]]:
                    continue
                if used[tmp[0] + dx[k]][tmp[1] + dy[k]]:
                    continue
                used[tmp[0] + dx[k]][tmp[1] + dy[k]] = True
                q.append([tmp[0] + dx[k], tmp[1] + dy[k]])
        ans += b * w
print(ans)