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:
H, W = map(int, input().split())

S = []

for i in range(H):
    tmp = input()
    S.append(tmp)
    
B = []
ope = [-1, 1]

for i in range(H):
    for j in range(W):
        for k in ope:
            for l in range(1):
                s_h = i+k
                s_w = j+l
                if s_h>=0 and s_h<=H-1 and s_w>=0 and s_w<=W-1:
                    if S[i][j]=='#' and S[s_h][s_w]=='.':
                        B.append([[i, j], [s_h, s_w]])
        for k in range(1):
            for l in ope:
                s_h = i+k
                s_w = j+l
                if s_h>=0 and s_h<=H-1 and s_w>=0 and s_w<=W-1:
                    if S[i][j]=='#' and S[s_h][s_w]=='.':
                        B.append([[i, j], [s_h, s_w]])

if len(B)>0:
    Al = [[B[len(B)-1][0], B[len(B)-1][1]]]
else:
    Al = []
    
for i in range(len(B)-2, -1, -1):
    f = 1
    for j in range(len(Al)):
        for k in range(len(Al[j])):
            if Al[j][k]==B[i][0]:
                Al[j].append(B[i][1])
                f = -1
                break
            elif Al[j][k]==B[i][1]:
                Al[j].append(B[i][0])
                f = -1
                break
        if f<0:
            break
    else:
        Al.append([B[i][0], B[i][1]])
        
ans = 0
        
for i in range(len(Al)):
    tmp = list(map(list, set(map(tuple, Al[i]))))
    
    k = 0
    for j in range(len(tmp)):
        if S[tmp[j][0]][tmp[j][1]]=='#':
            k=k+1
    ans = ans + (len(tmp)-k)*k
    
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]

    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
            
            cnt += b_cnt*w_cnt
            
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#encoding:utf-8

import numpy as np

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

S_ = np.array(S)

memory = {}

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import 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
for i in range(h):
    for k in range(w):
        ntmp=[(i,k)]
        used=[]
        next=0
        if arr[i,k]==1:
            white=[]
            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
                #print(len(ntmp))
            count+=len(set(white))
            #print(len(set(white)))

print(count)

Submission status: Time Limit Exceeded

Solution code:
#encoding:utf-8

import numpy as np

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

S_ = np.array(S)

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

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

Submission status: Time Limit Exceeded

Solution code:
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)])
        popl = stk.popleft
        append = stk.append
        add = visited.add
        while stk: # なくなるまで
            y,x = popl()

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

Submission status: Time Limit Exceeded

Solution code:
def c_alternating_path(H, W, Grid):
    from collections import deque
    ans = 0
    already_checked = [[False] * W for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if already_checked[h][w]:
                continue
            if Grid[h][w] == '#':
                reached_black = 0
                tmp = 0
                is_visit = [[False] * W for _ in range(H)]
                q = deque([(h, w)])
                while q:
                    row, col = q.pop()
                    if is_visit[row][col]:
                        continue
                    if (not already_checked[row][col]) and Grid[row][col] == '#':
                        already_checked[row][col] = True
                        reached_black += 1
                    is_visit[row][col] = True
                    if Grid[row][col] == '.':
                        tmp += 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))
                ans += tmp * reached_black
    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:
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
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            ans += dfs((i, j, "#"))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

mat = []
for _ in range(H):
    S = list(str(input()))
    mat.append(S)

mat = np.array(mat)
g_num = 0
visited = np.zeros((H, W))
result = [[0, 0] for _ in range(H * W)]

for i in range(H):
    for j in range(W):
        if visited[i, j] != 1:

            visited[i, j] = 1
            if mat[i, j] == '.':
                result[g_num][0] += 1
            else:
                result[g_num][1] += 1
            li = [(i, j)]

            while len(li) > 0:
                # up
                if li[-1][0] != 0:
                    if visited[li[-1][0] - 1, li[-1][1]] == 0 \
                            and mat[li[-1][0], li[-1][1]] != mat[li[-1][0] - 1, li[-1][1]]:
                        visited[li[-1][0] - 1, li[-1][1]] = 1
                        if mat[li[-1][0] - 1, li[-1][1]] == '.':
                            result[g_num][0] += 1
                        else:
                            result[g_num][1] += 1
                        li.append((li[-1][0] - 1, li[-1][1]))
                        continue
                # left
                if li[-1][1] != 0:
                    if visited[li[-1][0], li[-1][1] - 1] == 0 \
                            and mat[li[-1][0], li[-1][1]] != mat[li[-1][0], li[-1][1] - 1]:
                        visited[li[-1][0], li[-1][1] - 1] = 1
                        if mat[li[-1][0], li[-1][1] - 1] == '.':
                            result[g_num][0] += 1
                        else:
                            result[g_num][1] += 1
                        li.append((li[-1][0], li[-1][1] - 1))
                        continue
                # up
                if li[-1][0] != H - 1:
                    if visited[li[-1][0] + 1, li[-1][1]] == 0 \
                            and mat[li[-1][0], li[-1][1]] != mat[li[-1][0] + 1, li[-1][1]]:
                        visited[li[-1][0] + 1, li[-1][1]] = 1
                        if mat[li[-1][0] + 1, li[-1][1]] == '.':
                            result[g_num][0] += 1
                        else:
                            result[g_num][1] += 1

                        li.append((li[-1][0] + 1, li[-1][1]))
                        continue
                # left
                if li[-1][1] != W - 1:
                    if visited[li[-1][0], li[-1][1] + 1] == 0 \
                            and mat[li[-1][0], li[-1][1]] != mat[li[-1][0], li[-1][1] + 1]:
                        visited[li[-1][0], li[-1][1] + 1] = 1
                        if mat[li[-1][0], li[-1][1] + 1] == '.':
                            result[g_num][0] += 1
                        else:
                            result[g_num][1] += 1
                        li.append((li[-1][0], li[-1][1] + 1))
                        continue
                # nothing to do
                li.pop(-1)
            g_num += 1

ans = 0
for wb in result:
    ans += wb[0] * wb[1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve(H, W, S):
  routes = []
  for index in range(H):
    row = S[index]

    start = row.find('#.', 0)
    while start > -1:
      routes.append(((index, start), (index, start + 1)))
      start = row.find('#.', start + 1)

    start = row.find('.#', 0)
    while start > -1:
      routes.append(((index, start + 1), (index, start)))
      start = row.find('.#', start + 1)

  for line in range(W):
    for row in range(H - 1):
      if S[row][line] == '#':
        if S[row + 1][line] == '#': continue
        routes.append(((row, line), (row + 1, line)))
      else:
        if S[row + 1][line] == '.': continue
        routes.append(((row + 1, line), (row, line)))


  # S = [''.join(list(x)) for x in zip(*S)]

  # for index, row in enumerate(S):
  #   start = row.find('#.', 0)
  #   while start > -1:
  #     routes.append(((start, index), (start + 1, index)))
  #     start = row.find('#.', start + 1)

  #   start = row.find('.#', 0)
  #   while start > -1:
  #     routes.append(((start + 1, index), (start, index)))
  #     start = row.find('.#', start + 1)

  for route in routes:
    start, end = route
    cList1 = filter(lambda r: r[0] != start and r[1] == end, routes)
    for candidate in cList1:
      cStart, cEnd = candidate
      cList2 = filter(lambda r: r[0] == cStart and r[1] != cEnd, routes)
      for dest in cList2:
        newRoute = (start, dest[1])
        if newRoute not in routes:
          routes.append(newRoute)

  return len(routes)


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

print(solve(H, W, S))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

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

class travel:
    def __init__(self, m):
        self.ma=m
        self.ans=0
        self.dp=[[False]*W for _ in range(H)]
    def go(self, x, y, m):
        dxy=[(-1,0),(1,0),(0,-1),(0,1)]
        mark=['.','#']
        for dx,dy in dxy:
            x2=x+dx
            y2=y+dy
            if 0<= x2 < H and 0<= y2 < W:
                if self.ma[x2][y2]==mark[m] and self.dp[x2][y2]==False:
                    if m: self.ans+=1
                    self.dp[x2][y2]=True
                    self.go(x2,y2,int(not m))
    def __call__(self):
        for i in range(H):
           for j in range(W):
               if m[i][j]=='.':
                   self.dp=[[False]*W for _ in range(H)]
                   self.go(i,j,1)
        return self.ans
        
print(travel(m)())

Submission status: Time Limit Exceeded

Solution code:
class UnionFind(object):
 
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]
 
    def find(self, x):
        if self.table[x] < 0:
            return x
        self.table[x] = self.find(self.table[x])
        return self.table[x]
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 == s2:
            return False
        if self.table[s1] > self.table[s2]:
            s1, s2 = s2, s1
        self.table[s1] += self.table[s2]
        self.table[s2] = s1
        return True

H, W = list(map(int, input().split()))
S = list(input() for _ in range(H))
uf = UnionFind(H*W)

def get(h, w):
    return h * W + w

for h in range(H):
    for w in range(W):        
        for dh, dw in zip((0, 1), (1, 0)):
            if (h + dh) >= H or (w + dw) >= W:
                continue
            if S[h][w] != S[h+dh][w+dw]:
                uf.union(get(h, w), get(h+dh, w+dw))


from itertools import product

C1 = [(h, w) for h, w in product(range(H), range(W)) if S[h][w] == "."]
C2 = [(h, w) for h, w in product(range(H), range(W)) if S[h][w] == "#"]

ans = 0
for h1, w1 in C1:
    for h2, w2 in C2:
        if uf.same(get(h1, w1), get(h2, w2)):
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

mat = []
for _ in range(H):
    S = list(str(input()))
    mat.append(S)

mat = np.array(mat)
g_num = 0
group = np.zeros((H, W))
visited = np.zeros((H, W))
result = [[0, 0] for _ in range(H * W)]

for i in range(H):
    for j in range(W):
        if visited[i, j] != 1:

            visited[i, j] = 1
            if mat[i, j] == '.':
                result[g_num][0] += 1
            else:
                result[g_num][1] += 1
            li = [(i, j)]

            while len(li) > 0:
                # up
                if li[-1][0] != 0:
                    if visited[li[-1][0] - 1, li[-1][1]] == 0 \
                            and mat[li[-1][0], li[-1][1]] != mat[li[-1][0] - 1, li[-1][1]]:
                        visited[li[-1][0] - 1, li[-1][1]] = 1
                        if mat[li[-1][0] - 1, li[-1][1]] == '.':
                            result[g_num][0] += 1
                        else:
                            result[g_num][1] += 1
                        li.append((li[-1][0] - 1, li[-1][1]))
                        continue
                # left
                if li[-1][1] != 0:
                    if visited[li[-1][0], li[-1][1] - 1] == 0 \
                            and mat[li[-1][0], li[-1][1]] != mat[li[-1][0], li[-1][1] - 1]:
                        visited[li[-1][0], li[-1][1] - 1] = 1
                        if mat[li[-1][0], li[-1][1] - 1] == '.':
                            result[g_num][0] += 1
                        else:
                            result[g_num][1] += 1
                        li.append((li[-1][0], li[-1][1] - 1))
                        continue
                # up
                if li[-1][0] != H - 1:
                    if visited[li[-1][0] + 1, li[-1][1]] == 0 \
                            and mat[li[-1][0], li[-1][1]] != mat[li[-1][0] + 1, li[-1][1]]:
                        visited[li[-1][0] + 1, li[-1][1]] = 1
                        if mat[li[-1][0] + 1, li[-1][1]] == '.':
                            result[g_num][0] += 1
                        else:
                            result[g_num][1] += 1

                        li.append((li[-1][0] + 1, li[-1][1]))
                        continue
                # left
                if li[-1][1] != W - 1:
                    if visited[li[-1][0], li[-1][1] + 1] == 0 \
                            and mat[li[-1][0], li[-1][1]] != mat[li[-1][0], li[-1][1] + 1]:
                        visited[li[-1][0], li[-1][1] + 1] = 1
                        if mat[li[-1][0], li[-1][1] + 1] == '.':
                            result[g_num][0] += 1
                        else:
                            result[g_num][1] += 1
                        li.append((li[-1][0], li[-1][1] + 1))
                        continue
                # nothing to do
                li.pop(-1)
            g_num += 1

ans = 0
for wb in result:
    ans += wb[0] * wb[1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n):
        self.v = [-1 for _ in range(n)]  # 根(負): 連結頂点数 * (-1) / 子(正): 根の頂点番号(0-indexed)

    def find(self, x):  # xを含む木における根の頂点番号を返す
        if self.v[x] < 0:  # (負)は根
            return x
        else:  # 根の頂点番号
            self.v[x] = self.find(self.v[x])  # uniteでは, 旧根に属する頂点の根が旧根のままなので更新
            return self.v[x]

    def unite(self, x, y):  # 違う根に属していたらrankが低くなるように連結
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if -self.v[x] < -self.v[y]:  # size比較, 　(-1) * (連結頂点数 * (-1)), (正)同士の大小比較
            x, y = y, x  # 連結頂点数が少ない方をyにすると, findでの更新回数が減る？
        self.v[x] += self.v[y]  # 連結頂点数の和を取る, 連結頂点数 * (-1)
        self.v[y] = x  # 連結頂点数が少ないy(引数yの根の頂点番号)の根をx(引数xの根の頂点番号)にする

    def root(self, x):
        return self.v[x] < 0  # (負)は根

    def same(self, x, y):
        return self.find(x) == self.find(y)  # 同じ根に属するか

    def size(self, x):
        return -self.v[self.find(x)]  # 連結頂点数を返す


dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]

H, W = map(int, input().split())
s = [input() for _ in range(H)]
uf = UnionFind(2 * H * W)  # 全頂点 * 2
for r in range(H):
    for c in range(W):
        if s[r][c] == '#':
            for i in range(4):
                nr = r + dr[i]
                nc = c + dc[i]
                if 0 <= nr < H and 0 <= nc < W:
                    if s[nr][nc] == '.':
                        uf.unite(r * W + c, H * W + (nr * W + nc))  # #: *1, .: * 2
        else:
            for i in range(4):
                nr = r + dr[i]
                nc = c + dc[i]
                if 0 <= nr < H and 0 <= nc < W:
                    if s[nr][nc] == '#':
                        uf.unite(H * W + (r * W + c), nr * W + nc)  # #: *1, .: * 2

ans = 0
for r in range(H):
    for c in range(W):
        if uf.root(r * W + c):
            # print(r, c, '#')
            sz = uf.size(r * W + c)
            # print(' ', r * W + c, sz, '#')
            if sz > 1:
                xx = 0
                yy = 0
                for r2 in range(H):
                    for c2 in range(W):
                        if uf.find(H * W + r2 * W + c2) == r * W + c:
                            xx += 1
                yy = sz - xx
                # print(xx * yy)
                ans += xx * yy

        if uf.root(H * W + (r * W + c)):
            # print(r, c, '.')
            sz = uf.size(H * W + (r * W + c))
            # print(' ', r * W + c, sz, '.')
            if sz > 1:
                xx = 0
                yy = 0
                for r2 in range(H):
                    for c2 in range(W):
                        if uf.find(r2 * W + c2) == H * W + (r * W + c):
                            xx += 1
                yy = sz - xx
                # print(xx * yy)
                ans += xx * yy

print(ans)
# print(uf.v)

Submission status: Time Limit Exceeded

Solution code:
def solve(S):
  routes = []
  for index, row in enumerate(S):
    start = row.find('#.', 0)
    while start > -1:
      routes.append(((index, start), (index, start + 1)))
      start = row.find('#.', start + 1)

    start = row.find('.#', 0)
    while start > -1:
      routes.append(((index, start + 1), (index, start)))
      start = row.find('.#', start + 1)

  S = [''.join(list(x)) for x in zip(*S)]

  for index, row in enumerate(S):
    start = row.find('#.', 0)
    while start > -1:
      routes.append(((start, index), (start + 1, index)))
      start = row.find('#.', start + 1)

    start = row.find('.#', 0)
    while start > -1:
      routes.append(((start + 1, index), (start, index)))
      start = row.find('.#', start + 1)

  # for route in routes:
  #   print(route)

  for route in routes:
    start, end = route
    cList1 = list(filter(lambda r: r[0] != start and r[1] == end, routes))
    for candidate in cList1:
      cStart, cEnd = candidate
      cList2 = list(filter(lambda r: r[0] == cStart and r[1] != cEnd, routes))
      for dest in cList2:
        newRoute = (start, dest[1])
        if newRoute not in routes:
          routes.append(newRoute)

  return len(routes)


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

print(solve(S))

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

import numpy as np


def solve():
    H, W = map(int, input().split())
    C = np.zeros((H, W))
    for i, _ in enumerate(range(H)):
        for j, c in enumerate(input()):
            if c == '#':
                C[i, j] = 1

    area = np.zeros((H, W))
    now = 1
    for i in range(H):
        for j in range(W):
            if i != 0 and j != 0 and C[i, j] != C[i - 1, j] and C[i, j] != C[i, j - 1] and area[i - 1, j] != area[i, j - 1]:
                area[area == area[i, j - 1]] = area[i - 1, j]
                area[i, j] = area[i - 1, j]
            if j != 0 and C[i, j - 1] != C[i, j]:
                area[i, j] = area[i, j - 1]
            elif i != 0 and C[i - 1, j] != C[i, j]:
                area[i, j] = area[i - 1, j]
            else:
                area[i, j] = now
                now += 1

    cnt = dict()
    for i in range(H):
        for j in range(W):
            wh, bl = cnt.get(area[i, j], (0, 0))
            if C[i, j] == 0:
                cnt[area[i, j]] = (wh + 1, bl)
            else:
                cnt[area[i, j]] = (wh, bl + 1)

    print(sum(map(lambda x: x[0] * x[1], cnt.values())))


if __name__ == '__main__':
    solve()