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]
                            #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:
                                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(set(dst_white_cells))
                #print('whites',dst_white_cells)

        #print()
    print(cnt)
    return

main()

Submission status: Time Limit Exceeded

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

import numpy as np

def solve():
    H, W  = map(int,input().split())
    S = list()
    for _ in range(H):
        S.append([1 if a == '#' else 0 for a in input()])
    S = np.array(S)
    h, w = np.where(S==1)
    V1 = list(zip(h,w))
    h, w = np.where(S==0)
    V2 = list(zip(h,w))
    E = {v:[w for w in V2 if np.abs(np.array(v)-np.array(w)).sum()==1] for v in V1}
    E.update({v:[w for w in V1 if np.abs(np.array(v)-np.array(w)).sum()==1] for v in V2})
    C = {v:set() for v in V1}
    W = set()
    res = 0
    for v in V1:
        X, Y =  {v}, set() 
        if v in W:
            continue
        while X:
            w = X.pop()
            Y.add(w)
            W.add(w)
            X |= set(E[w])-Y
        res += len(Y&set(V1))*len(Y&set(V2))
    return str(res)

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

Submission status: Time Limit Exceeded

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

    
ed=[]
Ans=0
for node in range(H*W):
    if node in ed:
        continue
    ing=[node]
    cluster={"#":0,".":0}
    while len(ing)>0:
        b=ing.pop()
        cluster[S[b]]+=1
        if b!=0:
            if b%W!=0 and b-1 not in ing and b-1 not in ed:
                if S[b-1]!=S[b]:
                    ing.append(b-1)
        if b!=H*W-1:
            if b+1 not in ing and b+1 not in ed and b%W!=W-1:
                if S[b+1]!=S[b]:
                    ing.append(b+1)
        if b<(H-1)*W:
            if b+W not in ing and b+W not in ed:
                if S[b+W]!=S[b]:
                    ing.append(b+W)
        if b>=W:
            if b-W not in ing and b-W not in ed:
                if S[b-W]!=S[b]:
                    ing.append(b-W)
        ed.append(b)

    Ans+=cluster["#"]*cluster["."]

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

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

    a = [0,0]
    if s[start_x][start_y] == '#':
        check = 0
    else:
        check = 1
    a[check] += 1
    s[start_x][start_y] = '*'

    temp = [[start_x, start_y]]

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

    #print(start_x, start_y, a)
    #for i in range(h + 2): print(s[i])
    ans += a[0] * a[1]

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

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 h_i in range(1):
        for w_i in range(w):
        #for w_i in range(1):
            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 == '.':
                                dst_white_cells.append((next_x, next_y))
                                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)


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

        #print()
    print(cnt)
    return

main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

black_list = []
white_list = []
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            black_list.append((j, i))
        else:
            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:
import numpy as np
import copy
h,w=map(int, input().split(" "))
arr=np.zeros((h,w))
for i in range(h):
    tmp=input()
    for num,k in enumerate(tmp):
        if k == "#":
            arr[i,num]=1

count=0
skips=[]
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:
H,W=map(int,raw_input().split())
S=[]
for i in range(H):
    S.extend(raw_input())

    
ed=[]
Ans=0
import heapq as hq
for node in range(H*W):
    if node in ed:
        continue
    ing=[]
    hq.heappush(ing,node)
    cluster={"#":0,".":0}
    while len(ing)>0:
        b=hq.heappop(ing)
        cluster[S[b]]+=1
        if b!=0:
            if b%W!=0 and b-1 not in ing and b-1 not in ed:
                if S[b-1]!=S[b]:
                    hq.heappush(ing,b-1)
        if b!=H*W-1:
            if b+1 not in ing and b+1 not in ed and b%W!=W-1:
                if S[b+1]!=S[b]:
                    hq.heappush(ing,b+1)
        if b<(H-1)*W:
            if b+W not in ing and b+W not in ed:
                if S[b+W]!=S[b]:
                    hq.heappush(ing,b+W)
        if b>=W:
            if b-W not in ing and b-W not in ed:
                if S[b-W]!=S[b]:
                    hq.heappush(ing,b-W)
        ed.append(b)

    Ans+=cluster["#"]*cluster["."]

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[0][0], FIFO[0][1], FIFO[0][2]
                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:]
                    
                del FIFO[0]

print(counter)

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 += 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)
       output = list( set(get_ways(row,column,Ss,H,W)))
       for res in output:
           if Ss[res[0]][res[1]] == '#':
               continue
           if cur == res:
               continue
           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(len(whole))

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
s_array = ["+" * (w + 2)]
for i in range(h):
    s_array.append("+" + input() + "+")
else:
    s_array.append("+" * (w + 2))
res_array = []
res = 0
moving = [[0, 1], [1, 0]]


def recursive(mark, row, point, origin_x, origin_y):
    if row == 0 and row == h and w == 0 and w == row:
        return
    for x, y in moving:
        if s_array[row][point] != s_array[row + x][point + y] and s_array[row + x][point + y] != "+":
            tmp = [[origin_x, origin_y], [row + x, point + y]]
            if tmp not in res_array and mark != s_array[row + x][point + y]:
                res_array.append(tmp)
            recursive(mark, row+x, point+y, origin_x, origin_y)
    else:
        return


for row in range(1, h + 1):
    for point in range(1, w + 1):
        recursive(s_array[row][point], row, point, row, point)

print(len(res_array))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque
h, w = map(int, input().split())
s = [input() for _ in range(h)]

segment = np.zeros((h, w), dtype = np.int32)
idx = 1
dxy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
for y in range(h):
    for x in range(w):
        if segment[y, x] == 0:
            segment[y, x] = idx
            state = s[y][x]
            que = deque([[y, x, state]])
            while len(que) > 0:
                y_cur, x_cur, state = que.popleft()
                for dx, dy in dxy:
                    y_next = y_cur + dy
                    x_next = x_cur + dx
                    state_next = '.' if state == '#' else '#'
                    if x_next < 0 or y_next < 0 or x_next >= w or y_next >= h:
                        continue
                    elif s[y_next][x_next] != state_next:
                        continue
                    elif segment[y_next, x_next] == 0:
                        segment[y_next, x_next] = idx
                        que.append((y_next, x_next, state_next))
            idx += 1

# print(segment)
idx_max = np.max(segment)
nbw = [[0, 0] for _ in range(idx_max+1)]
for y in range(h):
    for x in range(w):
        idx = segment[y, x]
        if s[y][x] == '#':
            nbw[idx][0] += 1
        else:
            nbw[idx][1] += 1
ans = 0
for nb, nw in nbw:
    ans += nb*nw
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))
    if Ss[row][column] != "#":
        return []
    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 += 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):
       cur = (row,column)
       output = list( set(get_ways(row,column,Ss,H,W)))
       for res in output:
           if Ss[res[0]][res[1]] == '#':
               continue
           if cur == res:
               continue
           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(len(whole))

Submission status: Time Limit Exceeded

Solution code:

class Node:
    def __init__(self, key, value, parent=None, left=None, right=None):
        self.key = key
        self.value = value
        self.parent = parent
        self.left = left
        self.right = right
        self.balance = 0
        
    def disp_key(self):
        s = str(self.key)
        if self.left is None:
            pass
        else:
            s = str(self.left.key) + " " + s
            
        if self.right is None:
            pass
        else:
            s = s + " " + str(self.right.key)
        print(s)
        
    def disp(self):
        if self.left:
            self.left.disp()
        print(self.key, self.value)
        if self.right:
            self.right.disp()
        
    def disp_preorder(self):
        # print(self.key, self.value, self.left.key, self.left.value, self.right.key, self.right.value)
        lr = ""
        if self.left:
            lr += str(self.left.key)
        else:
            lr += "."
        lr += "-"
        if self.right:
            lr += str(self.right.key)
        else:
            lr += "."
            
        if self.parent:
            print(self.key, self.value, lr, self.parent.key)
        else:
            print(self.key, self.value, lr)
        if self.left:
            self.left.disp_preorder()
        if self.right:
            self.right.disp_preorder()
        
    def insert(self, key, value):
        # print(self.key, "<-", key)
        if self is None:
            self = Node(key, value)
        elif key == self.key:
            # return self
            self.value = value
            pass
        elif key < self.key:
            if self.left is None:
                self.left = Node(key, value, self)
            else:
                # self.left = self.left.insert(key, value)
                self.left.insert(key, value)
        else:
            if self.right is None:
                self.right = Node(key, value, self)
            else:
                # self.right = self.right.insert(key, value)
                self.right.insert(key, value)
        
        # self.disp()
        
    def set_value(self, key, value):
        tmp = self.search_node(key)
        if tmp:
            tmp.value = value
        else:
            self.insert(key, value)
        
    def modify_value(self, key, operator):
        tmp = self.search_node(key)
        if tmp:
            tmp.value = operator(tmp.value)
            return tmp.value
        else:
            return None
        
        
    def search(self, key):
        tmp = self.search_node(key)
        if tmp:
            return tmp.value
        else:
            return None
    
    def search_node(self, key):
        if key == self.key:
            return self
        elif key < self.key:
            if self.left:
                return self.left.search_node(key)
            else:
                return None
        else:
            if self.right:
                return self.right.search_node(key)
            else:
                return None
            
    def minimum(self):
        if self.left:
            return self.left.minimum()
        else:
            return (self.key, self.value)
    
    def maximum(self):
        if self.right:
            return self.right.maximum()
        else:
            return (self.key, self.value)
        
    def delete(self, key):
        if self.key == key:
            if (self.left is None) and (self.right is None):
                print("DELETE:", self.key, self.value)
                if self.parent:
                    if self.parent.left.key == self.key:
                        self.parent.left = None
                    elif self.parent.right.key == self.key:
                        self.parent.right = None
                # self.value = None
                # self = None
            elif self.left is None:
                if self.parent.left.key == self.key:
                    self.parent.left = self.right
                elif self.parent.right.key == self.key:
                    self.parent.right = self.right
            elif self.right is None:
                if self.parent.left.key == self.key:
                    self.parent.left = self.left
                elif self.parent.right.key == self.key:
                    self.parent.right = self.left
            else:
                tmp = self.right.minimum()
                self.key, self.value = tmp
                self.right.delete(tmp[0])
        elif key < self.key:
            if self.left:
                self.left.delete(key)
        else:
            if self.right:
                self.right.delete(key)
                
    def delete_more_than(self, key):
        if self.key == key:
            self.right = None
        elif key > self.key:
            self.right.delete_more_than(key)
        else:
            self.right = None
            self.delete(self.key)
            self.left.delete_more_than(key)
    
if False:
    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
else:
    H, W = 400, 400

    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):
        if i%2 == 0:
            s = ("#.#." * W)[:W]
        else:
            s = (".#.#" * W)[:W]
        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]]
            nd = Node(i*400+j,1)
            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:
                        if not nd.search((i0-1)*400+j0):
                            post.append([i0-1,j0])
                            # GGG.append([i0-1,j0])
                            nd.insert((i0-1)*400+j0, 1)
                            L[i0-1][j0] = g
                            G[g][(i0+j0+1)%2] += 1
                        else:
                            print("AAA")
                    if i0<H-1 and L[i0+1][j0] < 0 and X[i0][j0] == X[i0+1][j0]:
                        # print([i0+1,j0], GGG)
                        # if [i0+1,j0] not in GGG:
                        if not nd.search((i0+1)*400+j0):
                            post.append([i0+1,j0])
                            # GGG.append([i0+1,j0])
                            nd.insert((i0+1)*400+j0, 1)
                            L[i0+1][j0] = g
                            G[g][(i0+j0+1)%2] += 1
                        else:
                            print("BBB")
                    if j0>0 and L[i0][j0-1] < 0 and X[i0][j0] == X[i0][j0-1]:
                        # print([i0,j0-1], GGG)
                        # if [i0,j0-1] not in GGG:
                        if not nd.search((i0)*400+j0-1):
                            post.append([i0,j0-1])
                            # GGG.append([i0,j0-1])
                            nd.insert((i0)*400+j0-1, 1)
                            L[i0][j0-1] = g
                            G[g][(i0+j0+1)%2] += 1
                        else:
                            print("AAA")
                    if j0<W-1 and L[i0][j0+1] < 0 and X[i0][j0] == X[i0][j0+1]:
                        # print([i0,j0+1], GGG)
                        # if [i0,j0+1] not in GGG:
                        if not nd.search((i0)*400+j0+1):
                            post.append([i0,j0+1])
                            # GGG.append([i0,j0+1])
                            nd.insert((i0)*400+j0+1, 1)
                            L[i0][j0+1] = g
                            G[g][(i0+j0+1)%2] += 1
                        else:
                            print("AAA")
                        
            # 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:
h,w = map(int,input().split())
s = []
for i in range(h):
    s.append(input())

k = [[0 for i in range(w)] for k in range(h)]
k[0][0] =1
m = 2

for a in range(h):
    for b in range(w):
        if (a == 0 and b>= 1):
            if s[a][b] != s[a][b-1]:
                k[a][b] = k[a][b-1]
            else:
                k[a][b] = m
                m += 1
        elif (1 <= a <= w-1 and b == 0):
            if s[a-1][b] != s[a][b]:
                k[a][b] = k[a-1][b]
            else:
                k[a][b] = m
                m += 1
        else :
            if s[a][b-1] != s[a][b]:
                k[a][b] = k[a][b-1]
            elif s[a][b] != s[a-1][b]:
                k[a][b] = k[a-1][b]
            else:
                k[a][b] = m
                m += 1

ans = 0
for i in range(m):
    gu = 0
    ki = 0
    for a in range(h):
        for b in range(w):
            if k[a][b] == i:
                if s[a][b] == ".":
                    gu += 1
                else:
                    ki += 1

    ans += gu*ki

print(ans)