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:
from collections import deque

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

res = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            stack = deque([])
            flag = [[False for _ in range(W)] for _ in range(H)]
            stack.append([i, j])
            flag[i][j] = True
            start = S[i][j]
            while len(stack) > 0:
                y, x = stack.popleft()
                for nx, ny in ([1, 0], [0, 1], [-1, 0], [0, -1]):
                    if 0<= x + nx < W and 0 <= y + ny < H:
                        if S[y][x] != S[y+ny][x+nx] and flag[y+ny][x+nx] == False:
                            stack.append([y+ny, x+nx])
                            flag[y+ny][x+nx] = True
                            if S[y+ny][x+nx] != start:
                                res += 1
            
                
            
            
print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

res = 0
for i in range(H):
    for j in range(W):
        stack = deque([])
        flag = [[False for _ in range(W)] for _ in range(H)]
        stack.append([i, j])
        flag[i][j] = True
        start = S[i][j]
        while len(stack) > 0:
            y, x = stack.popleft()
            for nx, ny in ([1, 0], [0, 1], [-1, 0], [0, -1]):
                if 0<= x + nx < W and 0 <= y + ny < H:
                    if S[y][x] != S[y+ny][x+nx] and flag[y+ny][x+nx] == False:
                        stack.append([y+ny, x+nx])
                        flag[y+ny][x+nx] = True
                        if S[y+ny][x+nx] != start:
                            res += 1
            
                
            
            
print(res//2)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

res = 0
for i in range(H):
    for j in range(W):
        stack = deque([])
        flag = [[False for _ in range(W)] for _ in range(H)]
        stack.append([i, j])
        flag[i][j] = True
        start = S[i][j]
        while len(stack) > 0:
            y, x = stack.popleft()
            for nx, ny in ([1, 0], [0, 1], [-1, 0], [0, -1]):
                if 0<= x + nx < W and 0 <= y + ny < H:
                    if S[y][x] != S[y+ny][x+nx] and flag[y+ny][x+nx] == False:
                        stack.append([y+ny, x+nx])
                        flag[y+ny][x+nx] = True
                        if S[y+ny][x+nx] != start:
                            res += 1
            
                
            
            
print(res//2)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
s=[input() for _ in range(h)]
dy=[0,0,1,-1]
dx=[1,-1,0,0]
import sys
sys.setrecursionlimit(200000)
def dfs(y,x):
    global check
    global was
    was[y][x]=1
    if s[y][x]=="#":
        check[0]+=1
    else:
        check[1]+=1
    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if nx >= 0 and ny >= 0 and nx < w and ny < h and s[ny][nx] != s[y][x] and not was[ny][nx]:
            dfs(ny,nx) 
ans=0
was=[[0 for _ in range(w)] for _ in range(h)]
for i in range(w):
    for j in range(h):
        if not was[j][i]:
            check=[0,0]
            dfs(j,i)
            ans+=check[0]*check[1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int, input().split())
s = []
for i in range(h):
    s.append(input())
import sys
sys.setrecursionlimit(200000)
dy = [0,0,1,-1]
dx = [1,-1,0,0]
def dfs(y,x):
    global check
    global was
    was[y][x] = 1
    if s[y][x] == "#":
        check[0] += 1
    else:
        check[1] += 1
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if nx >= 0 and ny >= 0 and nx < w and ny < h and s[ny][nx] != s[y][x] and not was[ny][nx]:
            dfs(ny,nx)
ans = 0
was = [[0 for i in range(w)] for j in range(h)]
for i in range(w):
    for j in range(h):
        if not was[j][i]:
            check = [0,0]
            dfs(j,i)
            ans += check[0] * check[1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
s=[input() for _ in range(h)]
dy=[0,0,1,-1]
dx=[1,-1,0,0]
import sys
sys.setrecursionlimit(100000)
def dfs(y,x):
    global check
    global was
    was[y][x]=1
    if s[y][x]=="#":
        check[0]+=1
    else:
        check[1]+=1
    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if nx >= 0 and ny >= 0 and nx < w and ny < h and s[ny][nx] != s[y][x] and not was[ny][nx]:
            dfs(ny,nx) 
ans=0
was=[[0 for _ in range(w)] for _ in range(h)]
for i in range(w):
    for j in range(h):
        if not was[j][i]:
            check=[0,0]
            dfs(j,i)
            ans+=check[0]*check[1]
print(ans)

Submission status: Time Limit Exceeded

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

from collections import deque

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

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

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

ans = set()
for b in blacks:
    q = deque()
    v = [[False] * W for _ in range(H)]
    q.append(b)
    v[b[0]][b[1]] = True
    while q:
        y, x = q.popleft()
        for n in neig:
            ny, nx = y + n[0], x + n[1]
            if 0 <= ny < H and 0 <= nx < W:
                if S[y][x] == '#' and S[ny][nx] == '.' and not v[ny][nx]:
                    q.append((ny, nx))
                    v[ny][nx] = True
                    ans.add((b, (ny, nx)))
                elif S[y][x] == '.' and S[ny][nx] == '#' and not v[ny][nx]:
                    q.append((ny, nx))
                    v[ny][nx] = True

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

explored = [[False for i in range(W)] for j in range(H)]
dxy = [(-1,0),(1,0),(0,-1),(0,1)]
ans = 0

for h in range(H) :
    for w in range(W) :
        if not explored[h][w] :
            q = deque([(h,w)])
            black = 0
            white = 0
            
            while q :
                y,x = q.popleft()
                explored[y][x] = True
                
                if MAP[y][x] == "#" :
                    black += 1
                else :
                    white += 1
                
                for dy,dx in dxy :
                    ny = y+dy
                    nx = x+dx
                    
                    if (ny < 0) or (ny >= H) or (nx < 0) or (nx >= W) :
                        continue
                    if explored[ny][nx] :
                        continue
                    if MAP[ny][nx] == MAP[y][x] :
                        continue
                    if (ny,nx) in q :
                        continue
                    q.append((ny,nx))
                    
            ans += black*white

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue

BLACK = '#'
WHITE = '.'
vec_x = [1, 0, -1, 0]
vec_y = [0, 1, 0, -1]
vec_num = len(vec_x)

def solve():
    count = 0
    for i in range(H):
        for j in range(W):
            if used[i][j]:
                continue
            b = 0
            w = 0
            que = queue.Queue()
            used[i][j] = True
            que.put((i, j))

            while not que.empty():
                next_i, next_j = que.get()

                #黒か白かをカウント
                if(S[next_i][next_j] == BLACK):
                    b += 1
                else:
                    w += 1

                #隣接するマスの色が現在のマスと違うならキューに追加
                for d in range(vec_num):
                    d_i = next_i + vec_y[d]
                    d_j = next_j + vec_x[d]
                    if not check(next_i, next_j, d_i, d_j) or used[d_i][d_j]:
                        continue
                    que.put((d_i, d_j))
                    used[d_i][d_j] = True
            count += b * w
    return count

def check(i, j, d_i, d_j):
    if not isIn(d_i, d_j):
        return False
    if S[i][j] == S[d_i][d_j]:
        return False
    return True

def isIn(i, j):
    return 0 <= i < H and 0 <= j < W



if __name__ == "__main__":
    H, W = map(int, input().split())
    S = [[]] * H
    used = [[]] * H
    for h in range(H):
        S[h] = list(input())
        used[h] = [False] * W
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import Queue

def io_generator():
	while True:
		yield raw_input()

#++++++

def dataIo(io):
	# スペース区切りの整数の入力
	h,w = map(int, io.next().split())
	d=[[toBin(c) for c in list(io.next())] for _ in range(h)]
	
	return h,w,d

def toBin(a_char):
	return 1 if a_char=='#' else 0

def mkb(n):
	return [0 for _ in range(n)]

def main(io):
	h,w,d=dataIo(io)
	
	arrived = lambda : [mkb(w) for _ in range(h)]
	ret=0
	#print arrived
	#print d
	preComputed=arrived()
	a=arrived()
		
	for x in range(h):
		for y in range(w):
			if d[x][y]==1:
				continue
				
			if preComputed[x][y]>0:
				continue
			
			a[x][y]=1
			temp_ret=0
			temp_sharp=1
			
			openlist=Queue.Queue()
			openlist.put((0,x+1,y+0))
			openlist.put((0,x+0,y+1))
			openlist.put((0,x-1,y-0))
			openlist.put((0,x-0,y-1))
			while not openlist.empty():
				pre, xi, yi = openlist.get()
				preState=1 if pre==0 else 0
				#範囲外なら評価しない。
				if xi < 0 or yi < 0 or xi >= h or yi >= w:
					continue
				else:
					vv=d[xi][yi]
				
				#交互でなければ評価しない
				if vv!=preState:
					continue
									
				#到達済みなら評価しない
				if a[xi][yi]==1:
					continue
				a[xi][yi]=1

				#0ならretに1追加
				if vv==1:
					temp_ret+=1
				else:
					temp_sharp+=1
					preComputed[xi][yi]=1
				
				#移動可能な場所を追加
				openlist.put((preState,xi+1,yi+0))
				openlist.put((preState,xi+0,yi+1))
				openlist.put((preState,xi-1,yi-0))
				openlist.put((preState,xi-0,yi-1))
				
			#結果を記載
			ret+=temp_ret*temp_sharp
				
	return ret

#+++++
if __name__ == "__main__":
	io=io_generator()
	print main(io)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import Queue

def io_generator():
	while True:
		yield raw_input()

#++++++

def dataIo(io):
	# スペース区切りの整数の入力
	h,w = map(int, io.next().split())
	d=[[toBin(c) for c in list(io.next())] for _ in range(h)]
	
	return h,w,d

def toBin(a_char):
	return 1 if a_char=='#' else 0

def mkb(n):
	return [0 for _ in range(n)]

def main(io):
	h,w,d=dataIo(io)
	
	arrived = lambda : [mkb(w) for _ in range(h)]
	ret=0
	#print arrived
	#print d
	preComputed=arrived()
	for x in range(h):
		for y in range(w):
			if d[x][y]==1:
				continue
				
			aa= preComputed[x][y]
			if aa>0:
				continue
			
			a=arrived()
			a[x][y]=1
			temp_ret=0
			temp_sharp=1
			
			openlist=Queue.Queue()
			openlist.put((0,x+1,y+0))
			openlist.put((0,x+0,y+1))
			openlist.put((0,x-1,y-0))
			openlist.put((0,x-0,y-1))
			while not openlist.empty():
				pre, xi, yi = openlist.get()
				preState=1 if pre==0 else 0
				#範囲外なら評価しない。
				if xi < 0 or yi < 0 or xi >= h or yi >= w:
					continue
				else:
					vv=d[xi][yi]
					
				#到達済みなら評価しない
				if a[xi][yi]==1:
					continue
				a[xi][yi]=1
				
				#交互でなければ評価しない
				if vv!=preState:
					continue
				
				#0ならretに1追加
				if vv==1:
					temp_ret+=1
				else:
					temp_sharp+=1
				preComputed[xi][yi]=1
				
				#移動可能な場所を追加
				openlist.put((preState,xi+1,yi+0))
				openlist.put((preState,xi+0,yi+1))
				openlist.put((preState,xi-1,yi-0))
				openlist.put((preState,xi-0,yi-1))
				
			#結果を記載
			ret+=temp_ret*temp_sharp
				
	return ret

#+++++
if __name__ == "__main__":
	io=io_generator()
	print main(io)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import Queue

def io_generator():
	while True:
		yield raw_input()

#++++++

def dataIo(io):
	# スペース区切りの整数の入力
	h,w = map(int, io.next().split())
	d=[[toBin(c) for c in list(io.next())] for _ in range(h)]
	
	return h,w,d

def toBin(a_char):
	return 1 if a_char=='#' else 0

def mkb(n):
	return [0 for _ in range(n)]

def main(io):
	h,w,d=dataIo(io)
	
	arrived = lambda : [mkb(w) for _ in range(h)]
	ret=0
	#print arrived
	#print d
	preComputed=arrived()
	for x in range(h):
		for y in range(w):
			if d[x][y]==1:
				continue
				
			aa= preComputed[x][y]
			if aa>0:
				continue
			
			a=arrived()
			a[x][y]=1
			temp_ret=0
			temp_sharp=1
			
			openlist=Queue.Queue()
			openlist.put((0,x+1,y+0))
			openlist.put((0,x+0,y+1))
			openlist.put((0,x-1,y-0))
			openlist.put((0,x-0,y-1))
			while not openlist.empty():
				pre, xi, yi = openlist.get()
				preState=1 if pre==0 else 0
				#範囲外なら評価しない。
				if xi < 0 or yi < 0 or xi >= h or yi >= w:
					continue
				else:
					vv=d[xi][yi]
					
				#到達済みなら評価しない
				if a[xi][yi]==1:
					continue
				a[xi][yi]=1
				
				#交互でなければ評価しない
				if vv!=preState:
					continue
				
				#0ならretに1追加
				if vv==1:
					temp_ret+=1
				else:
					temp_sharp+=1
					preComputed[xi][yi]=1
				
				#移動可能な場所を追加
				openlist.put((preState,xi+1,yi+0))
				openlist.put((preState,xi+0,yi+1))
				openlist.put((preState,xi-1,yi-0))
				openlist.put((preState,xi-0,yi-1))
				
			#結果を記載
			ret+=temp_ret*temp_sharp
				
	return ret

#+++++
if __name__ == "__main__":
	io=io_generator()
	print main(io)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import Queue

def io_generator():
	while True:
		yield raw_input()

#++++++

def dataIo(io):
	# スペース区切りの整数の入力
	h,w = map(int, io.next().split())
	d=[[toBin(c) for c in list(io.next())] for _ in range(h)]
	
	return h,w,d

def toBin(a_char):
	return 1 if a_char=='#' else 0

def mkb(n):
	return [0 for _ in range(n)]

def main(io):
	h,w,d=dataIo(io)
	
	arrived = lambda : [mkb(w) for _ in range(h)]
	ret=0
	#print arrived
	#print d
	preComputed=arrived()
	for x in range(h):
		for y in range(w):
			a=arrived()
			a[x][y]=1
			temp_ret=0
			temp_sharp=1
			if d[x][y]==1:
				continue
				
			aa= preComputed[x][y]
			if aa>0:
				continue
			
			openlist=Queue.Queue()
			openlist.put((0,x+1,y+0))
			openlist.put((0,x+0,y+1))
			openlist.put((0,x-1,y-0))
			openlist.put((0,x-0,y-1))
			while not openlist.empty():
				pre, xi, yi = openlist.get()
				preState=1 if pre==0 else 0
				#範囲外なら評価しない。
				if xi < 0 or yi < 0 or xi >= h or yi >= w:
					continue
				else:
					vv=d[xi][yi]
					
				#到達済みなら評価しない
				if a[xi][yi]==1:
					continue
				a[xi][yi]=1
				
				#交互でなければ評価しない
				if vv!=preState:
					continue
				
				#0ならretに1追加
				if vv==1:
					temp_ret+=1
				else:
					temp_sharp+=1
					preComputed[xi][yi]=1
				
				#移動可能な場所を追加
				openlist.put((preState,xi+1,yi+0))
				openlist.put((preState,xi+0,yi+1))
				openlist.put((preState,xi-1,yi-0))
				openlist.put((preState,xi-0,yi-1))
				
			#結果を記載
			ret+=temp_ret*temp_sharp
				
	return ret

#+++++
if __name__ == "__main__":
	io=io_generator()
	print main(io)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import Queue

def io_generator():
	while True:
		yield raw_input()

#++++++

def dataIo(io):
	# スペース区切りの整数の入力
	h,w = map(int, io.next().split())
	d=[[toBin(c) for c in list(io.next())] for _ in range(h)]
	
	return h,w,d

def toBin(a_char):
	return 1 if a_char=='#' else 0

def mkb(n):
	return [0 for _ in range(n)]

def main(io):
	h,w,d=dataIo(io)
	
	arrived = lambda : [mkb(w) for _ in range(h)]
	ret=0
	#print arrived
	#print d
	preComputed=arrived()
	for x in range(h):
		for y in range(w):
			a=arrived()
			temp_ret=0
			if d[x][y]==1:
				continue
				
			aa= preComputed[x][y]
			if aa>0 and False:
				ret += aa
				continue
			
			openlist=Queue.Queue()
			openlist.put((0,x+1,y+0))
			openlist.put((0,x+0,y+1))
			openlist.put((0,x-1,y-0))
			openlist.put((0,x-0,y-1))
			while not openlist.empty():
				pre, xi, yi = openlist.get()
				preState=1 if pre==0 else 0
				#範囲外なら評価しない。
				if xi < 0 or yi < 0 or xi >= h or yi >= w:
					continue
				else:
					vv=d[xi][yi]
					
				#到達済みなら評価しない
				if a[xi][yi]==1:
					continue
				a[xi][yi]=1
				
				
				
				#交互でなければ評価しない
				if vv!=preState:
					continue
				
				#0ならretに1追加
				if vv==1:
					ret+=1
					temp_ret+=1
				
				#移動可能な場所を追加
				openlist.put((preState,xi+1,yi+0))
				openlist.put((preState,xi+0,yi+1))
				openlist.put((preState,xi-1,yi-0))
				openlist.put((preState,xi-0,yi-1))
				
			#結果を記載
			pass
				
	return ret

#+++++
if __name__ == "__main__":
	io=io_generator()
	print main(io)

Submission status: Time Limit Exceeded

Solution code:
import collections
import numpy as np
import sys

def search(i, j, S, Q):
    nxt = collections.deque([[i, j]])
    black = 0
    white = 0
    if (S[i][j] == "#"): black += 1
    if (S[i][j] == "."): white += 1
    Q[i][j] = True
    
    while nxt:
        i, j = nxt.popleft()

        if (j + 1 < S.shape[1]):
            if (S[i][j] != S[i][j + 1] and Q[i][j + 1] == False):
                Q[i][j + 1] = True
                nxt.append([i, j + 1])
                if (S[i][j + 1] == "#"):
                    black += 1
                else:
                    white += 1
        if (i + 1 < S.shape[0]):
            if (S[i][j] != S[i + 1][j] and Q[i + 1][j] == False):
                Q[i + 1][j] = True
                nxt.append([i + 1, j])
                if (S[i + 1][j] == "#"):
                    black += 1
                else:
                    white += 1
        if (j - 1 >= 0 and S[i][j] != S[i][j - 1] and Q[i][j - 1] == False):
            Q[i][j - 1] = True
            nxt.append([i, j - 1])
            if (S[i][j - 1] == "#"):
                black += 1
            else:
                white += 1
        if (i - 1 >= 0 and S[i][j] != S[i - 1][j] and Q[i - 1][j] == False):
            Q[i - 1][j] = True
            nxt.append([i - 1, j])
            if (S[i - 1][j] == "#"):
                black += 1
            else:
                white += 1

    #    print(S)
    #    print(Q)
    return black * white

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


def main(S):
    H, W = S.shape
    # print(S)
    Q = np.full([H, W], False)
    #     print(Q)

    answer = 0
    for i in range(H):
        for j in range(W):
            if (Q[i][j] == False):
                answer += search(i, j, S, Q)
    return answer

print(main(parse(sys.stdin)))

Submission status: Time Limit Exceeded

Solution code:
import collections
import numpy as np
import sys
import io


def search(i, j, S, Q):
    nxt = collections.deque([[i, j]])
    if(S[i][j]=="#"):
        black=1
        white=0
    else:
        white=1
        black=0
    Q[i][j] = True

    while nxt:
        i, j = nxt.popleft()
        if (j + 1 < S.shape[1]):
            if (Q[i][j + 1] == False and S[i][j] != S[i][j + 1]):
                Q[i][j + 1] = True
                nxt.append([i, j + 1])
                if (S[i][j + 1] == "#"):
                    black += 1
                else:
                    white += 1
        if (i + 1 < S.shape[0]):
            if (Q[i + 1][j] == False and S[i][j] != S[i + 1][j]):
                Q[i + 1][j] = True
                nxt.append([i + 1, j])
                if (S[i + 1][j] == "#"):
                    black += 1
                else:
                    white += 1
        if (Q[i][j - 1] == False and j - 1 >= 0 and S[i][j] != S[i][j - 1]):
            Q[i][j - 1] = True
            nxt.append([i, j - 1])
            if (S[i][j - 1] == "#"):
                black += 1
            else:
                white += 1
        if (Q[i - 1][j] == False and i - 1 >= 0 and S[i][j] != S[i - 1][j]):
            Q[i - 1][j] = True
            nxt.append([i - 1, j])
            if (S[i - 1][j] == "#"):
                black += 1
            else:
                white += 1

    #    print(S)
    #    print(Q)
    return black * white

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


def main(S):
    H, W = S.shape
    # print(S)
    Q = np.full([H, W], False)
    #     print(Q)

    answer = 0
    for i in range(H):
        for j in range(W):
            if (Q[i][j] == False):
                answer += search(i, j, S, Q)
    return answer

print(main(parse(sys.stdin)))

Submission status: Time Limit Exceeded

Solution code:
import collections
import numpy as np
import sys
import io


def search(i, j, S, Q):
    nxt = collections.deque([[i, j]])
    black = 0
    white = 0
    if (S[i][j] == "#"): black += 1
    if (S[i][j] == "."): white += 1

    while nxt:
        i, j = nxt.popleft()
        Q[i][j] = True

        if (j + 1 < S.shape[1]):
            if (S[i][j] != S[i][j + 1] and Q[i][j + 1] == False):
                Q[i][j + 1] = True
                nxt.append([i, j + 1])
                if (S[i][j + 1] == "#"):
                    black += 1
                else:
                    white += 1
        if (i + 1 < S.shape[0]):
            if (S[i][j] != S[i + 1][j] and Q[i + 1][j] == False):
                Q[i + 1][j] = True
                nxt.append([i + 1, j])
                if (S[i + 1][j] == "#"):
                    black += 1
                else:
                    white += 1
        if (j - 1 >= 0 and S[i][j] != S[i][j - 1] and Q[i][j - 1] == False):
            Q[i][j - 1] = True
            nxt.append([i, j - 1])
            if (S[i][j - 1] == "#"):
                black += 1
            else:
                white += 1
        if (i - 1 >= 0 and S[i][j] != S[i - 1][j] and Q[i - 1][j] == False):
            Q[i - 1][j] = True
            nxt.append([i - 1, j])
            if (S[i - 1][j] == "#"):
                black += 1
            else:
                white += 1

    #    print(S)
    #    print(Q)
    return black * white

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


def main(S):
    H, W = S.shape
    # print(S)
    Q = np.full([H, W], False)
    #     print(Q)

    answer = 0
    for i in range(H):
        for j in range(W):
            if (Q[i][j] == False):
                answer += search(i, j, S, Q)
    return answer

print(main(parse(sys.stdin)))

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
C = [input() for i in range(H)]

import sys
sys.setrecursionlimit(500000)

def search(x, y, z):
    if y >= H or x >= W or x < 0 or y <  0:
        return
    elif C[y][x] == z:
        return
    elif itta[y][x] != 0:
        return
    else:
        itta[y][x] = 0.00000001 # appendすると遅くなる
        prez = C[y][x]
        if C[y][x] == '.':
            itta[y][x] = 1
    
    search(x+1, y, prez)
    search(x-1, y, prez)
    search(x, y+1, prez)
    search(x, y-1, prez) 

ans = 0
# #を探しに行く
for y in range(H):
    for x in range(W):
        if C[y][x] != '#':
            pass
        else:
            itta = [[0] * W for i in range(H)]
            search(x, y, '.')
            ans += int(sum(map(sum, itta))) 
            # 入れ子リスト（２次元配列）の合計値
            # https://maku77.github.io/python/numstr/sum.html

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
C = [input() for i in range(H)]

import sys
sys.setrecursionlimit(500000)

def search(x, y, z):
    if y >= H or x >= W or x < 0 or y <  0:
        return
    elif C[y][x] == z:
        return
    elif itta[y][x] != 0:
        return
    else:
        itta[y][x] = 0.00000001 # appendすると遅くなる
        prez = C[y][x]
        if C[y][x] == '.':
            itta[y][x] = 1
    
    search(x+1, y, prez)
    search(x-1, y, prez)
    search(x, y+1, prez)
    search(x, y-1, prez) 

ans = 0
# #を探しに行く
for y in range(H):
    for x in range(W):
        if C[y][x] != '#':
            pass
        else:
            itta = [[0] * W for i in range(H)]
            search(x, y, '.')
            ans += int(sum(map(sum, itta))) 
            # 入れ子リスト（２次元配列）の合計値
            # https://maku77.github.io/python/numstr/sum.html

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
C = [input() for i in range(H)]

import sys
sys.setrecursionlimit(500000)

def search(x, y, z):
    if y >= H or x >= W or x < 0 or y <  0:
        return
    elif C[y][x] == z:
        return
    elif itta[y][x] != 0:
        return
    else:
        itta[y][x] = 0.0000000000000000001 # appendすると遅くなる
        prez = C[y][x]
        if C[y][x] == '.':
            itta[y][x] = 1
    
    search(x+1, y, prez)
    search(x-1, y, prez)
    search(x, y+1, prez)
    search(x, y-1, prez) 

ans = 0
# #を探しに行く
for y in range(H):
    for x in range(W):
        if C[y][x] != '#':
            pass
        else:
            itta = [[0] * W for i in range(H)]
            search(x, y, '.')
            ans += int(sum(map(sum, itta))) 
            # 入れ子リスト（２次元配列）の合計値
            # https://maku77.github.io/python/numstr/sum.html

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
C = [input() for i in range(H)]

import sys
sys.setrecursionlimit(500000)


def search(x, y, z):
    if y >= H or x >= W or x < 0 or y <  0:
        return
    elif C[y][x] == z:
        return
    elif itta[y][x] == 1:
        return
    else:
        itta[y][x] = 1 # appendすると遅くなる
        prez = C[y][x]
        if C[y][x] == '.':
            itta_white[y][x] = 1
    
    search(x+1, y, prez)
    search(x-1, y, prez)
    search(x, y+1, prez)
    search(x, y-1, prez) 

ans = 0
# #を探しに行く
for y in range(H):
    for x in range(W):
        if C[y][x] != '#':
            pass
        else:
            itta = [[0] * W for i in range(H)]
            itta_white = [[0] * W for i in range(H)]
            search(x, y, '.')
            ans += sum(map(sum, itta_white)) 
            # 入れ子リスト（２次元配列）の合計値
            # https://maku77.github.io/python/numstr/sum.html

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
C = [input() for i in range(H)]

import sys
sys.setrecursionlimit(500000)


def search(x, y, z):
    if y >= H or x >= W or x < 0 or y <  0:
        return
    elif C[y][x] == z:
        return
    elif itta[y][x] == 1:
        return
    else:
        itta[y][x] = 1 # appendすると遅くなる
        prez = C[y][x]
        if C[y][x] == '.':
            itta_white[y][x] = 1
    
    search(x+1, y, prez)
    search(x-1, y, prez)
    search(x, y+1, prez)
    search(x, y-1, prez) 
ans = 0
# #を探しに行く
for y in range(H):
    for x in range(W):
        if C[y][x] != '#':
            pass
        else:
            itta = [[0] * W for i in range(H)]
            itta_white = [[0] * W for i in range(H)]
            search(x, y, '.')
            ans += sum(map(sum, itta_white)) 
            # 入れ子リスト（２次元配列）の合計値
            # https://maku77.github.io/python/numstr/sum.html

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy3

import collections
import itertools


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


class UnitDict(dict):

    def __init__(self, iterable=None, wrapper=lambda x: x):
        super().__init__(self)
        self.wrapper = wrapper
        if iterable is not None:
            self.update(iterable)

    def __missing__(self, key):
        self[key] = self.wrapper(key)
        return self[key]


class DisjointSetDataStructure(object):

    def __init__(self, nodes=None):
        self.par = UnitDict(wrapper=lambda x: x)
        self.rank = collections.defaultdict(int)
        self.groups = UnitDict(wrapper=lambda x: {x})
        if nodes is not None:
            for node in nodes:
                _, _, _ = self.par[node], self.rank[node], self.groups[node]
        
    def root(self, node):
        if self.par[node] == node:
            return node
        else:
            r = self.root(self.par[node])
            self.par[node] = r
            return r
    
    def in_the_same_set(self, node1, node2):
        return self.root(node1) == self.root(node2)
    
    def elements_of_group(self, node):
        return self.groups[self.root(node)]
 
    def unite(self, node1, node2):
        x = self.root(node1)
        y = self.root(node2)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            self.par[y] = x
            self.groups[x].update(self.groups[y])
            self.groups[y].clear()
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


def solve(h, w, stage):
    dds = DisjointSetDataStructure()
    for r0, c0 in itertools.product(range(h), range(w)):
        cell0 = stage[r0][c0]
        for dr, dc in DELTAS:
            r, c = r0 + dr, c0 + dc
            if 0 <= r < h and 0 <= c < w and cell0 != stage[r][c]:
                dds.unite((r0, c0), (r, c))
    res = 0
    for nodes in dds.groups.values():
        num_total = len(nodes)
        num_black = sum(stage[r][c] for r, c in nodes)
        res += num_black * (num_total - num_black)
    return res


def main():
    h, w = (int(z) for z in input().split())
    stage = [[c == "#" for c in input()] for _ in range(h)]
    res = solve(h, w, stage)
    print(res)


if __name__ == "__main__":
    main()