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

L=[]
l=["*" for i in range(W+2)]
L.append(l)
for i in range(H):
    s=input()
    s="*"+s+"*"
    s=list(s)
    L.append(s)
L.append(l)

#print(L)
Li=[]
for i in range(1,H+1):
    for j in range(1,W+1):
        if L[i][j]=="#":
            Li.append([i,j])
#print(Li)
x=[1,-1,0,0]
y=[0,0,1,-1]
ans=0
for i in range(len(Li)):
    A=[[0 for i in range(W+2)]for j in range(H+2)]
    Arr=deque()
    Arr.append([Li[i][0],Li[i][1],0])
    #print(Arr)
    A[Arr[0][0]][Arr[0][1]]=1
    for j in range(W*H*2):
        if len(Arr)==0:
            break
        else:
            #print(Arr,ans)
            
            if (Arr[0][2])%2==0:
                for k in range(4):
                    if L[Arr[0][0]+x[k]][Arr[0][1]+y[k]]=="." and A[Arr[0][0]+x[k]][Arr[0][1]+y[k]]==0:
                        Arr.append([Arr[0][0]+x[k],Arr[0][1]+y[k],Arr[0][2]+1])
                        A[Arr[0][0]+x[k]][Arr[0][1]+y[k]]=1
                        ans+=1
                del Arr[0]
            else:
                for k in range(4):
                    if L[Arr[0][0]+x[k]][Arr[0][1]+y[k]]=="#" and A[Arr[0][0]+x[k]][Arr[0][1]+y[k]]==0:
                        Arr.append([Arr[0][0]+x[k],Arr[0][1]+y[k],Arr[0][2]+1])
                        A[Arr[0][0]+x[k]][Arr[0][1]+y[k]]=1
                del Arr[0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# H,W = 3,3
# s = [".#.", "..#", "#.."]

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

ans = 0
kaburi = 0
for i in range(H):
    for j in range(W):
        if s[i][j]==".": continue
        stk = deque([(i,j)]) # stktack
        visited = set([(i,j)])
        while stk: # なくなるまで
            y,x = stk.popleft()

            for dy,dx in ([1,0],[0,1],[-1,0],[0,-1]):
                if 0 <= y+dy < H and 0 <= x+dx < W:
                    if ((s[y][x]=="." and s[y+dy][x+dx] == "#")
                     or (s[y][x]=="#" and s[y+dy][x+dx] == ".") ):
                        if (y+dy,x+dx) in visited: continue
                        stk.append([y+dy,x+dx])
                        visited.add((y+dy,x+dx))
                        # print(i,j, y+dy,x+dx, ans)
                        if s[y+dy][x+dx]=="#": kaburi += 1
                        ans += 1
print(ans-kaburi)

Submission status: Time Limit Exceeded

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

BW={}
WB={}
    
for i in range(H*W):
    if S[i]=="#":
        BW[i]=[]
    else:
        WB[i]=[]

for b in BW:
    if b%W==0:
        if b+1 in WB:
            BW[b].append(b+1)
            WB[b+1].append(b)
        if b+H in WB:
            BW[b].append(b+H)
            WB[b+H].append(b)
        if b-H in WB:
            BW[b].append(b-H)
            WB[b-H].append(b)
    if b%W==W-1:
        if b-1 in WB:
            BW[b].append(b-1)
            WB[b-1].append(b)
        if b+H in WB:
            BW[b].append(b+H)
            WB[b+H].append(b)
        if b-H in WB:
            BW[b].append(b-H)
            WB[b-H].append(b)
    else:
        if b-1 in WB:
            BW[b].append(b-1)
            WB[b-1].append(b)
        if b+1 in WB:
            BW[b].append(b+1)
            WB[b+1].append(b)
        if b+H in WB:
            BW[b].append(b+H)
            WB[b+H].append(b)
        if b-H in WB:
            BW[b].append(b-H)
            WB[b-H].append(b)            
     
B_ed=[]
W_ed=[]
Ans=0
import heapq as hq

for b in BW:
    if b in B_ed:
        continue
    ing=[]
    hq.heappush(ing,b)
    cluster={"B":0,"W":0}
    while len(ing)>0:
        node=hq.heappop(ing)
        if node in BW:
            cluster["B"]+=1
            for nnode in BW[node]:
                if nnode not in W_ed and nnode not in ing:
                    hq.heappush(ing,nnode)
            B_ed.append(node)
        else:
            cluster["W"]+=1
            for nnode in WB[node]:
                if nnode not in B_ed and nnode not in ing:
                    hq.heappush(ing,nnode)
            W_ed.append(node)
    Ans+=cluster["B"]*cluster["W"]

print Ans

Submission status: Time Limit Exceeded

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

s = [['=' for _ in range(w + 2)]] + s + [['=' for _ in range(w + 2)]]

# for i in range(h+2): print(s[i])

t = [["="] + ["*" for _ in range(w)] + ["="] for _ in range(h)]

t = [['=' for _ in range(w + 2)]] + t + [['=' for _ in range(w + 2)]]

# for i in range(h): print(t[i])

ans = 0
while 1:
    start_x = h
    start_y = w
    check = 0
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            if t[i][j] == '*':
                start_x = i
                start_y = j
                check = 1
                break
        if check == 1:
            break
    # print(start_x, start_y)
    if start_x == h and start_y == w:
        break

    temp = [[start_x, start_y]]
    m = [["*" for _ in range(w + 2)] for _ in range(h + 2)]
    m[start_x][start_y] = s[start_x][start_y]
    t[start_x][start_y] = s[start_x][start_y]
    if s[start_x][start_y] == '#':
        check = 0
    else:
        check = 1

    while 1:
        # print(temp)
        next = []
        if check == 0:
            color = '.'
            check = 1
        else:
            color = '#'
            check = 0
        for x, y in temp:
            if m[x + 1][y] == '*' and s[x + 1][y] == color:
                m[x + 1][y] = color
                t[x + 1][y] = color
                next.append([x + 1, y])
            if m[x - 1][y] == '*' and s[x - 1][y] == color:
                m[x - 1][y] = color
                t[x - 1][y] = color
                next.append([x - 1, y])
            if m[x][y + 1] == '*' and s[x][y + 1] == color:
                m[x][y + 1] = color
                t[x][y + 1] = color
                next.append([x, y + 1])
            if m[x][y - 1] == '*' and s[x][y - 1] == color:
                m[x][y - 1] = color
                t[x][y - 1] = color
                next.append([x, y - 1])
        if len(next) == 0:
            break
        temp = [] + next

    black = 0
    for i in range(1, h + 1):
        black += m[i].count('#')
    white = 0
    for i in range(1, h + 1):
        white += m[i].count('.')
    ans += black * white

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())

L=[]
l=["*" for i in range(W+2)]
L.append(l)
for i in range(H):
    s=input()
    s="*"+s+"*"
    s=list(s)
    L.append(s)
L.append(l)

#print(L)
Li=[]
for i in range(1,H+1):
    for j in range(1,W+1):
        if L[i][j]=="#":
            Li.append([i,j])
#print(Li)
x=[1,-1,0,0]
y=[0,0,1,-1]
ans=0
for i in range(len(Li)):
    A=[[0 for i in range(W+2)]for j in range(H+2)]
    Arr=[[Li[i][0],Li[i][1],0]]
    #print(Arr)
    A[Arr[0][0]][Arr[0][1]]=1
    for j in range(W*H*2):
        if Arr==[]:
            break
        else:
            #print(Arr,ans)
            
            if (Arr[0][2])%2==0:
                for k in range(4):
                    if L[Arr[0][0]+x[k]][Arr[0][1]+y[k]]=="." and A[Arr[0][0]+x[k]][Arr[0][1]+y[k]]==0:
                        Arr.append([Arr[0][0]+x[k],Arr[0][1]+y[k],Arr[0][2]+1])
                        A[Arr[0][0]+x[k]][Arr[0][1]+y[k]]=1
                        ans+=1
                del Arr[0]
            else:
                for k in range(4):
                    if L[Arr[0][0]+x[k]][Arr[0][1]+y[k]]=="#" and A[Arr[0][0]+x[k]][Arr[0][1]+y[k]]==0:
                        Arr.append([Arr[0][0]+x[k],Arr[0][1]+y[k],Arr[0][2]+1])
                        A[Arr[0][0]+x[k]][Arr[0][1]+y[k]]=1
                del Arr[0]
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] == "#" and 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:
                    if 0 <= now[0] + s[0] < H and 0 <= now[1]+s[1] < W:
                        if S[now[0]][now[1]] == "#":
                            if S[now[0]+s[0]][now[1]+s[1]] == "." and not Visited[now[0]+s[0]][now[1]+s[1]]:
                                Visited[now[0]+s[0]][now[1]+s[1]] = True
                                Count += 1
                                Q.put((now[0]+s[0], now[1]+s[1]))
                        else:
                            if S[now[0]+s[0]][now[1]+s[1]] == "#" and not Visited[now[0]+s[0]][now[1]+s[1]]:
                                Visited[now[0]+s[0]][now[1]+s[1]] = True
                                BlackVis[now[0]+s[0]][now[1]+s[1]] = True
                                Mult += 1
                                Q.put((now[0]+s[0], now[1]+s[1]))
            Total += Count * Mult 
print(Total)

Submission status: Time Limit Exceeded

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

from itertools import product

P={}
for i,j in product(range(H),range(W)):
    s=S[i][j]
    path=[]
    for p in [-1,1]:
        if 0<=i+p<H:
            if S[i+p][j]!=s:
                path.append((i+p,j))
        if 0<=j+p<W:
            if S[i][j+p]!=s:
                path.append((i,j+p))
    P[(i,j)]=path
ans=0
for i,j in product(range(H),range(W)):
    path=[(i,j)]
    if S[i][j]=='#':
        que=P[(i,j)]
        path+=que
        ans+=len(que)
    else:
        que=[]
    while len(que)>0:
        tmp=[]
        for q in que:
            for p in P[q]:
                if p not in path:
                    path.append(p)
                    tmp.append(p)
                    if S[p[0]][p[1]]=='.':
                        ans+=1
        que=tmp

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
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 = []
    que.append((h,w))
    while len(que) > 0:
        xh,xw = que.pop(0)
        # 左
        if xw - 1 >= 0:
            if Sn[xh][xw] != Sn[xh][xw-1] and map[xh][xw-1] == 0:
                que.append((xh, xw-1))
                map[xh][xw-1] = Sn[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))
                map[xh-1][xw] = Sn[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))
                map[xh][xw+1] = Sn[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))
                map[xh+1][xw] = Sn[xh+1][xw]

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

cnt = 0
for i in range(H):
    for j in range(W):
        if Sn[i][j] == "#":
            cnt += func(i,j)

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def c_alternating_path(H, W, Grid):
    from collections import deque
    ans = 0
    for h in range(H):
        for w in range(W):
            if Grid[h][w] == '#':
                is_visit = [[False] * W for _ in range(H)]
                q = deque([(h, w)])
                while q:
                    row, col = q.pop()
                    if is_visit[row][col]:
                        continue
                    is_visit[row][col] = True
                    if Grid[row][col] == '.':
                        ans += 1
                    for dr, dc in zip((1, 0, -1, 0), (0, 1, 0, -1)):
                        nr, nc = row + dr, col + dc
                        if (0 <= nr < H and 0 <= nc < W
                                and Grid[row][col] != Grid[nr][nc]
                                and not is_visit[nr][nc]):
                            q.appendleft((nr, nc))
    return ans

H, W = [int(i) for i in input().split()]
Grid = [input() for _ in range(H)]
print(c_alternating_path(H, W, Grid))

Submission status: Time Limit Exceeded

Solution code:
import sys 

sys.setrecursionlimit(100000000)

def dfs(row, column, black):
    global S, H, W, X, Y, visited, ans
    if black:
        for dx, dy in zip(X, Y):
            n_row = row + dx
            n_column = column + dy
            if 0 <= n_row < H and 0 <= n_column < W:
                if visited[n_row][n_column] == False and S[n_row][n_column] == '.':
                    visited[n_row][n_column] = True
                    ans += 1
                    dfs(n_row, n_column, False)
    
    else:
        for dx, dy in zip(X, Y):
            n_row = row + dx
            n_column = column + dy
            if 0 <= n_row < H and 0 <= n_column < W:
                if visited[n_row][n_column] == False and S[n_row][n_column] == '#':
                    visited[n_row][n_column] = True
                    dfs(n_row, n_column, True)






if __name__ == "__main__":
    H, W = map(int, input().split())

    S = [None] * H
    X = [0, 0, 1, -1]
    Y = [1, -1, 0, 0]
    for i in range(H):
        S[i] = list(input())
    black_row = []
    black_column = []
    for row in range(H):
        for column in range(W):
            if S[row][column] == "#":
                black_row.append(row)
                black_column.append(column)
    ans = 0
    for row, column in zip(black_row, black_column):
        visited = [[False] * W for i in range(H)]
        dfs(row, column, True)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

def 解():
    input = sys.stdin.readline
    H,W = [int(_) for _ in input().split()]
    aM = [""]*H
    for i in range(H):
        aM[i] = input().rstrip()

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

    def bfsM(i,j):
        aS = [(i,j)]
        dsV = set()
        iC = 0
        while aS:
            th,tw = aS[0]
            del aS[0]
            if aM[th][tw] == ".":
                iC += 1
                for dh,dw in adxy:
                    nh,nw=dh+th,dw+tw
                    nP = (nh,nw)
                    if 0 <= nh < H and 0 <= nw < W:
                        if aM[nh][nw] == "#" and nP not in dsV:
                            aS.append(nP)
                            dsV.add(nP)
            else:
                for dh,dw in adxy:
                    nh,nw=dh+th,dw+tw
                    nP = (nh,nw)
                    if 0 <= nh < H and 0 <= nw < W:
                        if aM[nh][nw] == "." and nP not in dsV:
                            aS.append(nP)
                            dsV.add(nP)
        return iC

    iAns = 0
    for i in range(H):
        for j in range(W):
            if aM[i][j] == "#":
                iAns += bfsM(i,j)
    print(iAns)
解()

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] == "#" and 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()
                color = S[now[0]][now[1]]
                for s in Search:
                    if 0 <= now[0] + s[0] < H and 0 <= now[1]+s[1] < W:
                        if color == "#":
                            if S[now[0]+s[0]][now[1]+s[1]] == "." and not Visited[now[0]+s[0]][now[1]+s[1]]:
                                Visited[now[0]+s[0]][now[1]+s[1]] = True
                                Count += 1
                                Q.put((now[0]+s[0], now[1]+s[1]))
                        else:
                            if S[now[0]+s[0]][now[1]+s[1]] == "#" and not Visited[now[0]+s[0]][now[1]+s[1]]:
                                Visited[now[0]+s[0]][now[1]+s[1]] = True
                                BlackVis[now[0]+s[0]][now[1]+s[1]] = True
                                Mult += 1
                                Q.put((now[0]+s[0], now[1]+s[1]))
            Total += Count * Mult 
print(Total)

Submission status: Time Limit Exceeded

Solution code:
H, W=map(int, input().split())
S=[list(input()) for _ in range(H)]
S0=[[-1 for _ in range(W)] for _ in range(H)]
# print(S)
# print(S0)

num=1
S0[0][0]=0

for i in range(H):
	for j in range(W):
		if i==0 and j==0:
			continue
		if i>0 and j>0:
			if S[i-1][j]!=S[i][j]:
				S0[i][j]=S0[i-1][j]
			elif S[i][j-1]!=S[i][j]:
				S0[i][j]=S0[i][j-1]

			if S[i-1][j]==S[i][j] and S[i][j-1]==S[i][j]:
				S0[i][j]=num
				num+=1
		if i==0:
			if S[i][j-1]!=S[i][j]:
				S0[i][j]=S0[i][j-1]
			if S[i][j-1]==S[i][j]:
				S0[i][j]=num
				num+=1
		if j==0:
			if S[i-1][j]!=S[i][j]:
				S0[i][j]=S0[i-1][j]
			if S[i-1][j]==S[i][j]:
				S0[i][j]=num
				num+=1
# print(S0)
ans=0
for k in range(num):
	b=0
	w=0
	for i in range(H):
		for j in range(W):
				if S0[i][j]==k:
					if S[i][j]=='#':
						b+=1
					else:
						w+=1
	ans+=b*w
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
for h in range(H):
    for w in range(W):
        if S[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))
            Count = 0
            while not Q.empty():
                now = Q.get()
                color = S[now[0]][now[1]]
                for s in Search:
                    if 0 <= now[0] + s[0] < H and 0 <= now[1]+s[1] < W:
                        if color == "#":
                            if S[now[0]+s[0]][now[1]+s[1]] == "." and not Visited[now[0]+s[0]][now[1]+s[1]]:
                                Visited[now[0]+s[0]][now[1]+s[1]] = True
                                Count += 1
                                Q.put((now[0]+s[0], now[1]+s[1]))
                        else:
                            if S[now[0]+s[0]][now[1]+s[1]] == "#" and not Visited[now[0]+s[0]][now[1]+s[1]]:
                                Visited[now[0]+s[0]][now[1]+s[1]] = True
                                Q.put((now[0]+s[0], now[1]+s[1]))
            Total += Count
print(Total)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 9)

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

Visited = [[0] * W for i in range(H)]
direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]


def dfs(ny, nx, color):
    for dy, dx in direction:
        if not ((0 <= ny + dy < H) and (0 <= nx + dx < W)):
            continue

        if G[ny + dy][nx + dx] == G[ny][nx]:
            continue

        if Visited[ny + dy][nx + dx] != 0:
            continue

        if G[ny + dy][nx + dx] == '#':
            Visited[ny + dy][nx + dx] = color
        else:
            Visited[ny + dy][nx + dx] = -color

        dfs(ny + dy, nx + dx, color)


Color = 1
for y in range(H):
    for x in range(W):
        if Visited[y][x] == 0:
            if G[y][x] == '#':
                Visited[y][x] = Color
            else:
                Visited[y][x] = -Color
            dfs(y, x, Color)
            Color += 1

D = defaultdict(int)
for i in range(1, Color + 1):
    D[i] = 0
    D[-i] = 0

for row in Visited:
    for data in row:
        D[data] += 1

ans = 0
for key in D.keys():
    ans += D[key] * D[-key]

print(ans // 2)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())

X = [[0] * W for i in range(H)]
G = [[0,0] for i in range(W*H)] 
L = [[-1] * W for i in range(H)] # Group ID

for i in range(H):
    s = input()
    for j in range(W):
        if (i+j) % 2 == 0:
            if s[j] == "#":
                X[i][j] = 1
        else:
            if s[j] != "#":
                X[i][j] = 1
            
g = -1
for i in range(H):
    for j in range(W):
        if L[i][j] < 0:
            g += 1
            L[i][j] = g
            GGG = [[i,j]]
            post = [[i,j]]
            G[g][(i+j)%2] += 1
            while post:
                pre = post
                post = []
                for ggg in pre:
                    i0, j0 = ggg
                    if i0>0 and L[i0-1][j0] < 0 and X[i0][j0] == X[i0-1][j0]:
                        if [i0-1,j0] not in GGG:
                            post.append([i0-1,j0])
                            GGG.append([i0-1,j0])
                            L[i0-1][j0] = g
                            G[g][(i0+j0+1)%2] += 1
                    if i0<H-1 and L[i0+1][j0] < 0 and X[i0][j0] == X[i0+1][j0]:
                        if [i0+1,j0] not in GGG:
                            post.append([i0+1,j0])
                            GGG.append([i0+1,j0])
                            L[i0+1][j0] = g
                            G[g][(i0+j0+1)%2] += 1
                    if j0>0 and L[i0][j0-1] < 0 and X[i0][j0] == X[i0][j0-1]:
                        if [i0,j0-1] not in GGG:
                            post.append([i0,j0-1])
                            GGG.append([i0,j0-1])
                            L[i0][j0-1] = g
                            G[g][(i0+j0+1)%2] += 1
                    if j0<W-1 and L[i0][j0+1] < 0 and X[i0][j0] == X[i0][j0+1]:
                        if [i0,j0+1] not in GGG:
                            post.append([i0,j0+1])
                            GGG.append([i0,j0+1])
                            L[i0][j0+1] = g
                            G[g][(i0+j0+1)%2] += 1
                        
            # print(GGG)
# print(G)
ans = 0
for t in G:
    aa, bb = t
    ans += aa * bb
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

import sys
from collections import Counter, defaultdict, deque

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()


H, W = LI()
B = [[1 if s == '#' else 0 for s in S()] for _ in range(H)]


dy = (0, -1, 0, 1)
dx = (1, 0, -1, 0)
def BFS(i, j):
    ans = 0
    queue = deque([(i, j)])
    visited = set()
    while queue:
        y, x = queue.pop()
        color = B[y][x]
        if color == 0 and (y, x) not in visited:
            # print(y, x)
            ans += 1
        visited.add((y, x))
        for k in range(4):
            ny = y + dy[k]
            nx = x + dx[k]
            if (ny, nx) in visited:
                continue

            if ny < 0 or ny >= H or nx < 0 or nx >= W:
                continue

            if B[ny][nx] == color:
                continue

            queue.append((ny, nx))

    return ans


ans = 0
for h in range(H):
    for w in range(W):
        if B[h][w] == 1:
            ans += BFS(h, w)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, S):
    g = defaultdict(dict)
    for i, r in enumerate(S):
        for j, c in enumerate(r):
            if i > 0 and S[i-1][j] != c:
                g[(i, j)][(i-1, j)] = 1
                g[(i-1, j)][(i, j)] = 1
            if i < H-1 and S[i+1][j] != c:
                g[(i, j)][(i+1, j)] = 1
                g[(i+1, j)][(i, j)] = 1
            if j > 0 and S[i][j-1] != c:
                g[(i, j)][(i, j-1)] = 1
                g[(i, j-1)][(i, j)] = 1
            if j < W-1 and S[i][j+1] != c:
                g[(i, j)][(i, j+1)] = 1
                g[(i, j+1)][(i, j)] = 1
    
    ans = 0
    for k in g:
        i, j = k
        if S[i][j] != '#':
            continue
        s = [k]
        done = set([k])
        while s:
            # print(s)
            k = s.pop()
            for n in g[k]:
                if n not in done:
                    s.append(n)
                    done.add(n)
            i, j = k
            if S[i][j] == '.':
                ans += 1
            

    return ans


def main():
    H, W = read_int_n()
    S = []
    for _ in range(H):
        S.append(read_str())
    # S = []
    # H = 400
    # W = 400
    # for _ in range(H):
    #     S.append(random.choices('#.', k=W))
    print(slv(H, W, S))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 9)

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

Visited = [[0] * W for i in range(H)]
direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]


def dfs(ny, nx, color):
    for dy, dx in direction:
        if not ((0 <= ny + dy < H) and (0 <= nx + dx < W)):
            continue

        if G[ny + dy][nx + dx] == G[ny][nx]:
            continue

        if Visited[ny + dy][nx + dx] != 0:
            continue

        if G[ny + dy][nx + dx] == '#':
            Visited[ny + dy][nx + dx] = color
        else:
            Visited[ny + dy][nx + dx] = -color

        dfs(ny + dy, nx + dx, color)


Color = 1
for y in range(H):
    for x in range(W):
        if Visited[y][x] == 0:
            if G[y][x] == '#':
                Visited[y][x] = Color
            else:
                Visited[y][x] = -Color
            dfs(y, x, Color)
            Color += 1


D = defaultdict(int)
for row in Visited:
    for data in row:
        D[data] += 1

ans = 0
for key in D.keys():
    if -key in D.keys():
        ans += D[key] * D[-key]

print(ans // 2)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

def main():
    h, w = map(int, input().split())
    mp = ["X" * (w + 2)] + ["X" + input() + "X" for _ in range(h)] + ["X" * (w + 2)]
    checked = [[False] * (w + 2) for _ in range(h + 2)]
    vec = ((1, 0), (0, -1), (-1, 0), (0, 1))


    def search(x, y):
        checked[y][x] = True
        if mp[y][x] == "#":
            b_cnt = 1
            w_cnt = 0
            another = "."
        else:
            b_cnt = 0
            w_cnt = 1
            another = "#"
        for dx, dy in vec:
            nx, ny = x + dx, y + dy
            if not checked[ny][nx] and mp[ny][nx] == another:
                w_add, b_add = search(nx, ny)
                w_cnt += w_add
                b_cnt += b_add
        return w_cnt, b_cnt

    ans = 0
    for y in range(1, h + 1):
        for x in range(1, w + 1):
            if not checked[y][x]:
                w_cnt, b_cnt = search(x, y)
                ans += w_cnt * b_cnt

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
s = ["X" * (W+2)] + ["X" + input() + "X" for _ in range(H)] + ["X" * (W+2)]

DH = [1, 0, -1, 0]
DW = [0, 1, 0, -1]

ans = 0
def bfs(start):
	global ans
	que = deque([start])
	visited = [[False for _ in [0]*(W+2)] for _ in [0]*(H+2)]
	visited[start[0]][start[1]] = True
	#cur = s[start[0]][start[1]]
	while que:
		label = que.pop()
		h, w = label[0], label[1]
		if s[start[0]][start[1]] != s[h][w] and W*start[0]+start[1] < W*h+w:
			ans += 1
		for dh, dw in zip(DH, DW):
			if s[h][w] == ".":
				if s[h+dh][w+dw] == "#" and visited[h+dh][w+dw] == False:
					que.appendleft([h+dh, w+dw])
					visited[h+dh][w+dw] = True
			elif s[h][w] == "#":
				if s[h+dh][w+dw] == "." and visited[h+dh][w+dw] == False:
					que.appendleft([h+dh, w+dw])
					visited[h+dh][w+dw] = True


	del que, visited
	return

for i in range(1, H+1):
	for j in range(1, W+1):
		bfs([i, j])

print(ans)