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

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

    cnt = 0
    for h_i in range(h):
        for w_i in range(w):
            if board[h_i][w_i] == '#':
                trajectories = deque([[(w_i, h_i)]])
                dst_white_cells =[]

                while len(trajectories) != 0:
                    now_trajectory = trajectories.popleft()
                    #print('now_trajectory', now_trajectory)
                    now_x, now_y = now_trajectory[-1]
                    now_color = '.' if len(now_trajectory) % 2 == 0 else '#'
                    #print('now_cell', now_x, now_y, 'now_color', now_color)
                    for move in [(-1,0),(0,-1),(1,0),(0,1)]: #(move_x, move_y)
                        next_x, next_y = now_x + move[0], now_y + move[1]
                        next_cell = (next_x, next_y)
                        #print('next',next_x,next_y)
                        if 0 <= next_x < w and 0 <= next_y < h:
                            next_cell_color = board[next_y][next_x]
                            if next_cell_color == now_color:
                                continue                                
                            #print(now_color, next_cell_color)
                            if next_cell in now_trajectory or next_cell in dst_white_cells:
                                #print('already')
                                continue

                            if now_color == '#' and next_cell_color == '.':
                                cnt += 1
                                dst_white_cells.append(next_cell)
                                trajectories.append(now_trajectory + [next_cell])
                            elif now_color == '.' and next_cell_color == '#':
                                trajectories.append(now_trajectory + [next_cell])
                        #else:
                        #    print('out board')
                    #print(trajectories)

                #print(len(dst_white_cells))
                #cnt += len(dst_white_cells)
                #print('whites',dst_white_cells)

        #print()
    print(cnt)
    return

main()

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
from queue import Queue

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

counter = 0

for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            Sc = deepcopy(S)
            q = Queue()
            q.put([i, j, '#'])
            Sc[i] = Sc[i][:j] + 'a' + Sc[i][j+1:]
            while not q.empty():
                x, y, m = q.get()
                if m == '#':
                    if x != 0:
                        if Sc[x-1][y] == '.':
                            q.put([x-1, y, '.'])
                            Sc[x-1] = Sc[x-1][:y] + 'a' + Sc[x-1][y+1:]
                            counter += 1
                    if x != H-1:
                        if Sc[x+1][y] == '.':
                            q.put([x+1, y, '.'])
                            Sc[x+1] = Sc[x+1][:y] + 'a' + Sc[x+1][y+1:]
                            counter += 1

                    if y != 0:
                        if Sc[x][y-1] == '.':
                            q.put([x, y-1, '.'])
                            Sc[x] = Sc[x][:y-1] + 'a' + Sc[x][y:]
                            counter += 1

                    if y != W-1:
                        if Sc[x][y+1] == '.':
                            q.put([x, y+1, '.'])
                            Sc[x] = Sc[x][:y+1] + 'a' + Sc[x][y+2:]
                            counter += 1

                else:
                    if x != 0:
                        if Sc[x-1][y] == '#':
                            q.put([x-1, y, '#'])
                            Sc[x-1] = Sc[x-1][:y] + 'a' + Sc[x-1][y+1:]
                    if x != H-1:
                        if Sc[x+1][y] == '#':
                            q.put([x+1, y, '#'])
                            Sc[x+1] = Sc[x+1][:y] + 'a' + Sc[x+1][y+1:]

                    if y != 0:
                        if Sc[x][y-1] == '#':
                            q.put([x, y-1, '#'])
                            Sc[x] = Sc[x][:y-1] + 'a' + Sc[x][y:]

                    if y != W-1:
                        if Sc[x][y+1] == '#':
                            q.put([x, y+1, '#'])
                            Sc[x] = Sc[x][:y+1] + 'a' + Sc[x][y+2:]

print(counter)

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

Submission status: Time Limit Exceeded

Solution code:
h,w=list(map(int,input().split()))

s=[]
for i in range(h):
    s.append(input())

black=[]
white=[]

for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            black.append((i,j))
        else:
            white.append((i,j))

direction=[[1,0],[0,1],[-1,0],[0,-1]]

def search(start,end,color,count):
    if count>h+w:
        return False
    if start[0]==end[0] and start[1]==end[1]:
        return True
    result=False
    if color==0:
        for d in direction:
            if (start[0]+d[0],start[1]+d[1]) in white:
                next=[0,0]
                next[0]=start[0]+d[0]
                next[1]=start[1]+d[1]
                result|=search(next,end,color^1,count+1)
        return result
    if color==1:
        for d in direction:
            if (start[0]+d[0],start[1]+d[1]) in black:
                next=[0,0]
                next[0]=start[0]+d[0]
                next[1]=start[1]+d[1]
                result|=search(next,end,color^1,count+1)
        return result

#print(black)
#print(white)
ans=0
for wh in white:
    for bl in black:
        #print(wh,bl)
        if search(wh,bl,1,0):
            #print(wh,bl)
            ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

    cnt = 0
    for h_i in range(h):
        for w_i in range(w):
            if board[h_i][w_i] == '#':
                trajectories = deque([[(w_i, h_i)]])
                dst_white_cells =[]

                while len(trajectories) != 0:
                    now_trajectory = trajectories.popleft()
                    #print('now_trajectory', now_trajectory)
                    now_x, now_y = now_trajectory[-1]
                    now_color = '.' if len(now_trajectory) % 2 == 0 else '#'
                    #print('now_cell', now_x, now_y, 'now_color', now_color)
                    for move in [(-1,0),(0,-1),(1,0),(0,1)]: #(move_x, move_y)
                        next_x, next_y = now_x + move[0], now_y + move[1]
                        next_cell = (next_x, next_y)
                        #print('next',next_x,next_y)
                        if 0 <= next_x < w and 0 <= next_y < h:
                            next_cell_color = board[next_y][next_x]
                            #print(now_color, next_cell_color)
                            if next_cell in now_trajectory or next_cell in dst_white_cells:
                                #print('already')
                                continue

                            if now_color == '#' and next_cell_color == '.':
                                cnt += 1
                                dst_white_cells.append(next_cell)
                                trajectories.append(now_trajectory + [next_cell])
                            elif now_color == '.' and next_cell_color == '#':
                                trajectories.append(now_trajectory + [next_cell])
                        #else:
                        #    print('out board')
                    #print(trajectories)

                #print(len(dst_white_cells))
                #cnt += len(dst_white_cells)
                #print('whites',dst_white_cells)

        #print()
    print(cnt)
    return

main()

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue as Qe

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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


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


ret=0
q = deque([]) 
V=[ [ 0 for i in range(W) ] for j in range(H) ]

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



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

print ans

Submission status: Time Limit Exceeded

Solution code:
dxs = [1,0,-1,0]
dys = [0,1,0,-1]




def get_ways(row,column,Ss,H,W):
    pairs = []
    done = []
    que = []
    que.append((row,column))

    while(len(que) > 0):
        current = que.pop(0)
        done.append(current)
        for i in range(0,4):
            p = (current[0] + dxs[i],current[1] + dys[i])
            if p[0] >= H or p[1] >= W or p[0] < 0 or p[1] < 0 or p in done:
                continue
            elif Ss[current[0]][current[1]] != Ss[p[0]][p[1]]:
                que.append(p)
        pairs += list(filter(lambda x: Ss[x[0]][x[1]] == '.',que))
    return pairs


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

count = 0
whole = []
for row in range(0,H):
    for column in range(0,W):
       if Ss[row][column] != "#":
            continue
       cur = (row,column)
       count += len(list( set(get_ways(row,column,Ss,H,W))))
       #whole += output
    #   for res in output:
          # is_ok = True
          # for a in whole:
          #     if a[0] == res and a[1] == cur:
          #         is_ok = False
          # if is_ok:
       #   whole.append((cur,res))


print(count)

Submission status: Time Limit Exceeded

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



def search(s, h, w, pos, count, s_pos, t_pos):
    t_pos[pos[0]][pos[1]] = 1
    if(s[pos[0]][pos[1]] != s[s_pos[0]][s_pos[1]]):
        count += 1


    flag = False

    if(pos[0] != h-1 and t_pos[pos[0]+1][pos[1]] == 0):
        if(s[pos[0]][pos[1]] != s[pos[0]+1][pos[1]]):
            count = search(s, h, w, [pos[0]+1, pos[1]], count, s_pos, t_pos)
            flag = True

    """
    if(pos[0] != 0 and t_pos[pos[0]-1][pos[1]] == 0):
        if(s[pos[0]][pos[1]] != s[pos[0]-1][pos[1]]):
            count = search(s, h, w, [pos[0]-1, pos[1]], count, s_pos, t_pos)
            flag = True
    """

    if(pos[1] != w-1 and t_pos[pos[0]][pos[1]+1] == 0):
        if(s[pos[0]][pos[1]] != s[pos[0]][pos[1]+1]):
            count = search(s, h, w, [pos[0], pos[1]+1], count, s_pos, t_pos)
            flag = True
    """
    if(pos[1] != 0 and t_pos[pos[0]][pos[1]-1] == 0):
        if(s[pos[0]][pos[1]] != s[pos[0]][pos[1]-1]):
            count = search(s, h, w, [pos[0], pos[1]-1], count, s_pos, t_pos)
            flag = True
    """
    return count


count = 0
for i in range(h):
    for j in range(w):
        pos = [i, j]
        t_pos = [w*[0] for i in range(h)]
        count = search(s, h, w, pos, count, pos, t_pos)

print(count)

Submission status: Time Limit Exceeded

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

def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]

black_list = []
white_list = []

for i in range(h):
    if '#' in s[i]:
        for j in my_index_multi(s[i], '#'):
            black_list.append((j, i))
    if '.' in s[i]:
        for j in my_index_multi(s[i], '.'):
            white_list.append((j, i))


def bfs(sx, sy, gx, gy, maze):
    queue = [(sy, sx)]
    visited = [[-1]*w for _ in range(h)]
    visited[sy][sx] = 0
    cnt = 0

    while queue:
        y, x = queue.pop()
        if x==gx and y==gy:
            cnt += 1
            continue
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            nx_y, nx_x = y+j, x+k

            if (0 <= nx_x) and (nx_x < w) and (0 <= nx_y) and (nx_y < h):
                if (maze[nx_y][nx_x] != maze[y][x]) and (visited[nx_y][nx_x] == -1):
                    visited[nx_y][nx_x] = visited[y][x] + 1
                    queue.append([nx_y, nx_x])
    return cnt


ans = 0
for sx, sy in black_list:
    for gx, gy in white_list:
        ans += bfs(sx, sy, gx, gy, maze=s)

print(ans)

Submission status: Time Limit Exceeded

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

def func(h,w): # 黒のみ
    map = [[0 for _ in range(W)] for _ in range(H)]
    que = deque()
    que.append((h,w))
    while len(que) > 0:
        xh,xw = que.popleft()
        # 左
        if 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]

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

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

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

            cnt += b_cnt*w_cnt
            
print(cnt)

Submission status: Time Limit Exceeded

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


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

print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

    cnt = 0
    for h_i in range(h):
        for w_i in range(w):
            if board[h_i][w_i] == '#':
                trajectories = deque([[(w_i, h_i)]])
                dst_white_cells =[]

                while len(trajectories) != 0:
                    now_trajectory = trajectories.popleft()
                    #print('now_trajectory', now_trajectory)
                    now_x, now_y = now_trajectory[-1]
                    now_color = '.' if len(now_trajectory) % 2 == 0 else '#'
                    #print('now_cell', now_x, now_y, 'now_color', now_color)
                    for move in [(-1,0),(0,-1),(1,0),(0,1)]: #(move_x, move_y)
                        next_x, next_y = now_x + move[0], now_y + move[1]
                        next_cell = (next_x, next_y)
                        #print('next',next_x,next_y)
                        if 0 <= next_x < w and 0 <= next_y < h:
                            next_cell_color = board[next_y][next_x]
                            #print(now_color, next_cell_color)
                            if next_cell in now_trajectory:
                                #print('already')
                                continue

                            if now_color == '#' and next_cell_color == '.' and next_cell not in dst_white_cells:
                                cnt += 1
                                dst_white_cells.append(next_cell)
                                trajectories.append(now_trajectory + [next_cell])
                            elif now_color == '.' and next_cell_color == '#':
                                trajectories.append(now_trajectory + [next_cell])
                        #else:
                        #    print('out board')
                    #print(trajectories)

                #print(len(dst_white_cells))
                #cnt += len(dst_white_cells)
                #print('whites',dst_white_cells)

        #print()
    print(cnt)
    return

main()

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = []
for i in range(H):
    S.append(input())
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '.': continue
        b = []
        for k in range(H):
            b.append([-1]*W)
        queue = [[i,j]]
        b[i][j] = 0
        while len(queue) > 0:
            y, x = map(int, queue.pop(0))
            for h, w in [[-1,0],[1,0],[0,-1],[0,1]]:
                if h == -1 and y == 0: continue
                if h == 1 and y == H - 1: continue
                if w == -1 and x == 0: continue
                if w == 1 and x == W - 1: continue
                if b[y+h][x+w] >= 0: continue
                if S[y+h][x+w] == S[y][x]:
                    b[y+h][x+w] = 0
                else:
                    b[y+h][x+w] = b[y][x] + 1
                    queue.append([y+h, x+w])
                    if S[y+h][x+w] == '.': ans += 1
print(ans)

Submission status: Time Limit Exceeded

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


h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
ans = 0
black = [[0 for j in range(w)] for i in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            if i > 0 and j > 0 and s[i-1][j-1] == "#" and black[i-1][j-1]:
                count = black[i-1][j-1]
            elif i > 0 and j < w-1 and s[i-1][j+1] == "#" and black[i-1][j+1]:
                count = black[i-1][j+1]
            else:
                count = dfs((i, j, "#"))
            black[i][j] = count
            ans += count
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy

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

counter = 0

for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            Sc = deepcopy(S)
            FIFO = [[i, j, '#']]
            Sc[i] = Sc[i][:j] + 'a' + Sc[i][j+1:]
            while FIFO:
                x, y, m = FIFO.pop(0)
                if m == '#':
                    if x != 0:
                        if Sc[x-1][y] == '.':
                            FIFO.append([x-1, y, '.'])
                            Sc[x-1] = Sc[x-1][:y] + 'a' + Sc[x-1][y+1:]
                            counter += 1
                    if x != H-1:
                        if Sc[x+1][y] == '.':
                            FIFO.append([x+1, y, '.'])
                            Sc[x+1] = Sc[x+1][:y] + 'a' + Sc[x+1][y+1:]
                            counter += 1

                    if y != 0:
                        if Sc[x][y-1] == '.':
                            FIFO.append([x, y-1, '.'])
                            Sc[x] = Sc[x][:y-1] + 'a' + Sc[x][y:]
                            counter += 1

                    if y != W-1:
                        if Sc[x][y+1] == '.':
                            FIFO.append([x, y+1, '.'])
                            Sc[x] = Sc[x][:y+1] + 'a' + Sc[x][y+2:]
                            counter += 1

                else:
                    if x != 0:
                        if Sc[x-1][y] == '#':
                            FIFO.append([x-1, y, '#'])
                            Sc[x-1] = Sc[x-1][:y] + 'a' + Sc[x-1][y+1:]
                    if x != H-1:
                        if Sc[x+1][y] == '#':
                            FIFO.append([x+1, y, '#'])
                            Sc[x+1] = Sc[x+1][:y] + 'a' + Sc[x+1][y+1:]

                    if y != 0:
                        if Sc[x][y-1] == '#':
                            FIFO.append([x, y-1, '#'])
                            Sc[x] = Sc[x][:y-1] + 'a' + Sc[x][y:]

                    if y != W-1:
                        if Sc[x][y+1] == '#':
                            FIFO.append([x, y+1, '#'])
                            Sc[x] = Sc[x][:y+1] + 'a' + Sc[x][y+2:]

print(counter)

Submission status: Time Limit Exceeded

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

S = []

for i in range(H):
    S.append(list(raw_input()))
    
result = []
base = {'black': {}, 'white': {}}

def add_base(c, m, n, k, l):
    if (m, n) in base[c]:
        base[c][(m, n)].append((k, l))
    else:
        base[c][(m, n)] = [(k, l)]

for i in range(H):
    for j in range(W):
        if 0 < j:
            if S[i][j] == '#' and S[i][j-1] == '.':
                add_base('black', i, j, i, j-1)
                result.append([(i, j), (i, j-1)])
            elif S[i][j] == '.' and S[i][j-1] == '#':
                add_base('white', i, j, i, j-1)
        if j < W-1:
            if S[i][j] == '#' and S[i][j+1] == '.':
                add_base('black', i, j, i, j+1)
                result.append([(i, j), (i, j+1)])
            elif S[i][j] == '.' and S[i][j+1] == '#':
                add_base('white', i, j, i, j+1)
        if 0 < i:
            if S[i][j] == '#' and S[i-1][j] == '.':
                add_base('black', i, j, i-1, j)
                result.append([(i, j), (i-1, j)])
            elif S[i][j] == '.' and S[i-1][j] == '#':
                add_base('white', i, j, i-1, j)
        if i < H-1:
            if S[i][j] == '#' and S[i+1][j] == '.':
                add_base('black', i, j, i+1, j)
                result.append([(i, j), (i+1, j)])
            elif S[i][j] == '.' and S[i+1][j] == '#':
                add_base('white', i, j, i+1, j)

tmp = [r for r in result]
while len(tmp) > 0:
    r = tmp.pop()
    s = r[0]
    e = r[1]
    for b in base['white'].get(e, []):
        if b == s:
            continue
        for n in base['black'].get(b, []):
            if [s, n] not in result:
                result.append([s, n])
                tmp.append([s, n])
print(len(result))

Submission status: Time Limit Exceeded

Solution code:
# http://www.geocities.jp/m_hiroi/light/pyalgo61.html
class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a


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

uf = UnionFind(H * W)
lst = []
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            th = W * i + j
            lst.append(th)
            if i != 0 and S[i - 1][j] == '.':
                uf.union(W * (i - 1) + j, th)
            if i != H - 1 and S[i + 1][j] == '.':
                uf.union(W * (i + 1) + j, th)
            if j != 0 and S[i][j - 1] == '.':
                uf.union(W * (i) + j - 1, th)
            if j != W - 1 and S[i][j + 1] == '.':
                uf.union(W * (i) + j + 1, th)

g = uf.subsetall()


result = 0
for (le, nu) in g:
    count = 0
    for li in lst:
        if le == uf.find(li):
            count += 1
    result += (nu - count) * count

print(result)