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

mat=[[x=="#" for x in input()] for _ in range(H)]
#print(mat)

answer=0
for i in range(H):
  for j in range(W):
    if not mat[i][j]:
      continue
      
    visited_set=set()
    queue=[(i,j)]
    d=0
    while queue:
      new_queue=set()
      for q in queue:
        ii,jj=q
        visited_set.add((ii,jj))
        if d%2==1:
          answer+=1
        
        if ii>0 and mat[ii][jj]!=mat[ii-1][jj] and not (ii-1,jj) in visited_set:
          new_queue.add((ii-1,jj))
        if ii<H-1 and mat[ii][jj]!=mat[ii+1][jj] and not (ii+1,jj) in visited_set:
          new_queue.add((ii+1,jj))
        if jj>0 and mat[ii][jj]!=mat[ii][jj-1] and not (ii,jj-1) in visited_set:
          new_queue.add((ii,jj-1))
        if jj<W-1 and mat[ii][jj]!=mat[ii][jj+1] and not (ii,jj+1) in visited_set:
          new_queue.add((ii,jj+1))
          
      queue=list(new_queue)
      d+=1

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
H,W =list(map(int, input().split()))
S = [list(input()) for i in range(H)]
sys.setrecursionlimit(1000000)

black_visited_flag = [[False] * W for _ in range(H)] 

other_color = {".": "#", "#":'.'}

def dfs(i,j, color):
    num = 0
    black_num = 0
    #import IPython;IPython.embed()
    if i != 0:
        if S[i-1][j] == other_color[color] and not visit_flag[i-1][j]:
            visit_flag[i-1][j] = True
            _num, _black_num = dfs(i-1, j, other_color[color])
            num += _num
            black_num += _black_num
            if other_color[color] == "#":
                black_num += 1
                black_visited_flag[i-1][j] = True
            else:
                num += 1
    if i != H-1:
        if S[i+1][j] == other_color[color] and not visit_flag[i+1][j]:
            visit_flag[i+1][j] = True
            _num, _black_num = dfs(i+1, j, other_color[color])
            num += _num
            black_num += _black_num
            if other_color[color] == "#":
                black_num += 1
                black_visited_flag[i+1][j] = True
            else:
                num += 1
    if j != 0:
        if S[i][j-1] == other_color[color] and not visit_flag[i][j-1]:
            visit_flag[i][j-1] = True
            _num, _black_num = dfs(i, j -1, other_color[color])
            num += _num
            black_num += _black_num
            if other_color[color] == "#":
                black_num += 1
                black_visited_flag[i][j-1] = True
            else:
                num += 1
    if j != W-1:
        if S[i][j+1] == other_color[color] and not visit_flag[i][j+1]:
            visit_flag[i][j+1] = True
            _num, _black_num = dfs(i, j+1, other_color[color])
            num += _num
            black_num += _black_num
            if other_color[color] == "#":
                black_num += 1
                black_visited_flag[i][j+1] = True
            else:
                num += 1
    return num, black_num



ans = 0
for i, row in enumerate(S):
    for j, val in enumerate(row):
        if black_visited_flag[i][j] or S[i][j] == ".":
            continue
        visit_flag = [[False] * W for _ in range(H)] 
        num, black_num = dfs(i,j, "#")
        ans += (num * black_num)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W=map(int,input().split())
table=[list(input()) for _ in range(H)]
dp=[[-1 for _ in range(W)] for _ in range(H)]
d=deque()
col=0
wlist=[0]*(H*W)
blist=[0]*(H*W)
for i in range(H):
    for j in range(W):
        if dp[i][j]==-1:
            col = i*W+j
            d.append([i,j])
        while len(d)>0:
            v=d.popleft()
            x=v[0]
            y=v[1]
            dp[x][y]=col
            if x!=0:
                if (table[x][y]!=table[x-1][y])and(dp[x-1][y]==-1):
                    d.append([x-1,y])
            if x!=H-1:
                if (table[x][y]!=table[x+1][y])and(dp[x+1][y]==-1):
                    d.append([x + 1, y])
            if y!=0:
                if (table[x][y]!=table[x][y-1])and(dp[x][y-1]==-1):
                    d.append([x, y-1])
            if y!=W-1:
                if (table[x][y]!=table[x][y+1])and(dp[x][y+1]==-1):
                    d.append([x, y+1])
            #print(dp)
            #print(d)
            #input()
for i in range(H):
    for j in range(W):
        if table[i][j]=="#":
            blist[dp[i][j]]+=1
        else:
            wlist[dp[i][j]] += 1
#print(wlist,blist)
cnt=0
for i in range(H*W):
    cnt=cnt+blist[i]*wlist[i]
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# "#"と"."だけで行き来できるエリアを"島"とする
# 島にある"#"から"."には必ず行けるので、
# "#"の数 * "."がその島の場合の数。これをすべて足し合わせる

# visitedになっていない点をすべて捜査する。
# 進めなかった（"#"もしくは"."が連続した）マスはvisitedにしない。

H,W = map(int,input().split())
grid = [None] * H
for i in range(H):
  grid[i] = input()
  
visited = [[False] * W for i in range(H)]

def get_next_unvisited(checked_y):
  for i in range(checked_y,H):
    for j in range(W):
      if not visited[i][j]:
        return i,j
  return -1,-1 # 候補なし
  
from collections import deque
ans = 0
cases = ((0,1),(0,-1),(1,0),(-1,0))
checked_y = 0
while True:
  y,x = get_next_unvisited(checked_y)
  if y == -1 and x == -1:
    print(ans)
    exit(0)
  checked_y = y
  # y,x,親,親マスの文字
  q = deque([[y,x,-1,-1,"N"]])
  black = 0
  white = 0
  
  while q:
    y,x,parent_y,parent_x,parent = q.pop()
    if visited[y][x]:
      continue
    point = grid[y][x]
    if point == parent:
      continue
    visited[y][x] = True
    if point == "#":
      black += 1
    if point == ".":
      white += 1
    for c in cases:
      if y + c[0] == parent_y and x + c[1] == parent_x:
        continue
      if 0 <= y + c[0] < H and 0 <= x + c[1] < W:
        q.append([y + c[0],x + c[1],y,x, point])
  ans += black * white

Submission status: Time Limit Exceeded

Solution code:
# "#"と"."だけで行き来できるエリアを"島"とする
# 島にある"#"から"."には必ず行けるので、
# "#"の数 * "."がその島の場合の数。これをすべて足し合わせる

# visitedになっていない点をすべて捜査する。
# 進めなかった（"#"もしくは"."が連続した）マスはvisitedにしない。

H,W = map(int,input().split())
grid = [None] * H
for i in range(H):
  grid[i] = input()
  
visited = [[False] * W for i in range(H)]

def get_next_unvisited(checked_y):
  for i in range(checked_y,H):
    for j in range(W):
      if not visited[i][j]:
        return i,j
  return -1,-1 # 候補なし
  
from collections import deque
ans = 0
cases = ((0,1),(0,-1),(1,0),(-1,0))
checked_y = 0
while True:
  y,x = get_next_unvisited(checked_y)
  if y == -1 and x == -1:
    print(ans)
    exit(0)
  checked_y = y
  # y,x,親,親マスの文字
  q = deque([[y,x,-1,-1,"N"]])
  black = 0
  white = 0
  
  while q:
    y,x,parent_y,parent_x,parent = q.popleft()
    if visited[y][x]:
      continue
    point = grid[y][x]
    if point == parent:
      continue
    visited[y][x] = True
    if point == "#":
      black += 1
    if point == ".":
      white += 1
    for c in cases:
      if y + c[0] == parent_y and x + c[1] == parent_x:
        continue
      if 0 <= y + c[0] < H and 0 <= x + c[1] < W:
        q.append([y + c[0],x + c[1],y,x, point])
  ans += black * white

Submission status: Time Limit Exceeded

Solution code:
# "#"と"."だけで行き来できるエリアを"島"とする
# 島にある"#"から"."には必ず行けるので、
# "#"の数 * "."がその島の場合の数。これをすべて足し合わせる

# visitedになっていない点をすべて捜査する。
# 進めなかった（"#"もしくは"."が連続した）マスはvisitedにしない。

H,W = map(int,input().split())
grid = [None] * H
for i in range(H):
  grid[i] = input()
  
visited = [[False] * W for i in range(H)]

def get_next_unvisited():
  for i in range(H):
    for j in range(W):
      if not visited[i][j]:
        return i,j
  return -1,-1 # 候補なし
  
from collections import deque
ans = 0
cases = ((0,1),(0,-1),(1,0),(-1,0))
while True:
  y,x = get_next_unvisited()
  if y == -1 and x == -1:
    print(ans)
    exit(0)
  # y,x,直前のマス
  q = deque([[y,x,"N"]])
  black = 0
  white = 0
  
  while q:
    y,x,parent = q.popleft()
    if visited[y][x]:
      continue
    point = grid[y][x]
    if point == parent:
      continue
    visited[y][x] = True
    if point == "#":
      black += 1
    if point == ".":
      white += 1
    for c in cases:
      if 0 <= y + c[0] < H and 0 <= x + c[1] < W:
        q.append([y + c[0],x + c[1], point])
  ans += black * white

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
h,w=[int(j) for j in input().split()]
s=[list(input())for i in range(h)]
ans=0
def f(i,j,se):
    se.add((i,j))
    res=0
    b=True
    for x,y in [(1,0),(-1,0),(0,1),(0,-1)]:
        p,q=i+x,j+y
        if 0<=p<h and 0<=q<w:
            if s[p][q]!=s[i][j] and (p,q) not in se:
                b=False
                res+=f(p,q,se)
    if b:
        if s[i][j]==".":
            return 1
        else:
            return 0
    else:
        if s[i][j]==".":
            return res+1
        else:
            return res

for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            ans+=f(i,j,set())

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**7)

h,w = map(int,input().split())
si = [input() for i in range(h)]

check = [-1]*(h*w)

#print(check,check==-1)
#exit()

vx = [0,1,0,-1]
vy = [1,0,-1,0]

def dfs(num,clr):
    #print(min(check))
    #if min(check) > -1:
    #    return
    
    y = num//w
    x = num%w
    for j in range(4):
        ny = y + vy[j]
        nx = x + vx[j]
        if ny >= 0 and ny < h and nx >= 0 and nx < w:
            new_num = ny*w+nx
            if check[new_num] != -1:
                continue
            #print(new_num,num,clr,si[ny][nx])
            if clr == '#':
                #print(ny,nx)
                if si[ny][nx] == '.':
                    check[new_num] = check[num]
                    dfs(new_num,'.')
            else:
                    
                if si[ny][nx] == '#':
                    check[new_num] = check[num]
                    dfs(new_num,'#')
            #print(check)

for i in range(h*w):
    #print(i)
    y = i//w
    x = i%w
    if si[y][x] == '#':
        if check[i] != -1:
            continue
        check[i] = i
        dfs(i,'#')
        #print(check)
        #exit()

ans = 0

li = [0]*(h*w+1)

for i in range(h):
    for j in range(w):
        if si[i][j] == '.':
            li[check[i*w+j]] += 1

#print(li)

for i in range(h):
    for j in range(w):
        if si[i][j] == '#':
            ans += li[check[i*w+j]]
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w=map(int,input().split())
s=[]
for _ in range(h):
    s.append(input())
ans=0
for x in range(h):
    for y in range(w):
        if s[x][y]=='.':
            continue
        path = deque([[x,y]])
        sc=[[0 for i in range(w)] for j in range(h)]
        sc[x][y]=1
        while len(path)>0:
            p = path.popleft()
            i,j=p[0],p[1]
            tc = '.' if s[i][j] == '#' else '#'
            point = 1 if s[i][j] == '#' else 0
            if i > 0 and s[i-1][j]==tc and sc[i-1][j]==0:
                sc[i-1][j]=1
                path.append([i-1,j])
                ans += point
            if j > 0 and s[i][j-1]==tc and sc[i][j-1]==0:
                sc[i][j-1]=1
                path.append([i,j-1])
                ans += point
            if i < h-1 and s[i+1][j]==tc and sc[i+1][j]==0:
                sc[i+1][j]=1
                path.append([i+1,j])
                ans += point
            if j < w-1 and s[i][j+1]==tc and sc[i][j+1]==0:
                sc[i][j+1]=1
                path.append([i,j+1])
                ans += point
#print(sc)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
h,w = map(int,input().split())
s = [list(input()) for _ in range(h)]
visited = [[False]*w for _ in range(h)]

def dfs(y,x):
    visited[y][x] = True
    blk, wht = 0,0
    for dy,dx in zip((-1,1,0,0),(0,0,-1,1)):
        ny,nx = y+dy, x+dx
        if (not (0<=ny<h)) or (not (0<=nx<w)) or visited[ny][nx]:
            continue
        if s[y][x]!=s[ny][nx]:
            nb,nw = dfs(ny,nx)
            blk += nb
            wht += nw
    if s[y][x]=='#':
        blk += 1
    else:
        wht += 1
    return blk, wht

ans = 0
for i in range(h):
    for j in range(w):
        if not visited[i][j]:
            blk, wht = dfs(i,j)
            ans += blk*wht
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = [0]*(H+2)
S[0] = '*'*(W+2)
S[H+1] = '*'*(W+2)
for h in range(1,H+1):
  S[h] = '*' + input() + '*'

import sys
sys.setrecursionlimit(10**8)

bw = ['#','.']

visited = [[False]*(W+2) for h in range(H+2)]
ans = 0
dh = [0,1,0,-1]
dw = [1,0,-1,0]

def dfs(h,w,c):
  #print(h,w,c, bw_count)
  for i in range(4):
    h0 = h+dh[i]
    w0 = w+dw[i]
    if S[h0][w0]==bw[c^1] and visited[h0][w0]==False:
      visited[h0][w0]=True
      bw_count[c^1]+=1
      dfs(h0,w0,c^1)
  
for h in range(H+2):
  for w in range(W+2):
    if S[h][w]=='#' and visited[h][w]==False:
      bw_count = [1,0]
      visited[h][w]=True
      dfs(h,w,0)
      ans += bw_count[0]*bw_count[1]

print(ans)   

#print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
class UnionFind:
    def __init__(self, n):
        class KeyDict(dict):
            # 辞書にないときの対応
            def __missing__(self,key):
                self[key] = key
                return key
        self.parent = KeyDict()
        self.rank = defaultdict(int)
        self.weight = defaultdict(int)

    # 根を探す
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            # 経路圧縮
            # 自分自身じゃない場合は、上にさかのぼって検索(再帰的に)
            y = self.find(self.parent[x])           
            self.weight[x] += self.weight[self.parent[x]]   #圧縮時にweightを更新(和)
            self.parent[x] = y      #親の置き換え(圧縮)
            return self.parent[x]

    # 結合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
        
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

    ### 重み付き
    def weighted_union(self, x, y, w):
        # print("unite",x,y,w,self.weight)
        px = self.find(x)
        py = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        # if px == py: return 0
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
            self.weight[px] = - w - self.weight[x] + self.weight[y]
        else:
            self.parent[py] = px
            self.weight[py] =  w + self.weight[x] - self.weight[y]
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return 0

    # 判定
    def judge(self, x, y):
        return self.find(x) == self.find(y)


H,W = map(int, input().split())
fields = [list(input()) for i in range(H)]
uf = UnionFind(H*W)
for i in range(H):
    for j in range(W):
        if i-1 >= 0 and fields[i][j] != fields[i-1][j]:
            uf.union(i*W+j,(i-1)*W+j)
        if j-1 >= 0 and fields[i][j] != fields[i][j-1]:
            uf.union(i*W+j,i*W+j-1)
        if i+1 < H and fields[i][j] != fields[i+1][j]:
            uf.union(i*W+j,(i+1)*W+j)
        if j+1 < W and fields[i][j] != fields[i][j+1]:
            uf.union(i*W+j,i*W+j+1)


cnt_w = defaultdict(int)
cnt_b = defaultdict(int)
ps = set()
for i in range(H):
    for j in range(W):
        p = uf.find(i*W+j)
        ps.add(p)
        if fields[i][j] == ".":
            cnt_w[p] += 1
        else:
            cnt_b[p] += 1
ans = 0
for p in ps:
    ans += cnt_w[p] * cnt_b[p]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
S = []
for _ in range(h):
    s = str(input())
    S.append(s)

dq = deque([])
if S[0][0] == '.':
    dq.append([0,0,'.'])
else:
    dq.append([0,0,'#'])

Visited = [[False for _ in range(w)] for _ in range(h)]
Visited[0][0] = True

ans = 0
black = 0
white = 0
while dq:
    now = dq.popleft()

    y = now[0]
    x = now[1]
    color = now[2]

    if color == '.':
        white += 1
    else:
        black += 1

    Nexts = [[y,x-1], [y,x+1], [y-1,x], [y+1,x]]
    # print(x)
    # print(y)
    # print('-'*30)
    for nex in Nexts:
        if nex[0] >= h or nex[0] < 0 or nex[1] >= w or nex[1] < 0:
            continue
        if Visited[nex[0]][nex[1]] == True:
            continue

        if color == '.' and S[nex[0]][nex[1]] == '.':
            continue
        elif color == '#' and S[nex[0]][nex[1]] == '#':
            continue
        elif color == '.' and S[nex[0]][nex[1]] == '#':
            dq.append([nex[0], nex[1], '#'])
            Visited[nex[0]][nex[1]] = True
        else:
            dq.append([nex[0], nex[1], '.'])
            Visited[nex[0]][nex[1]] = True


    if len(dq) == 0:
        ans += black * white
        # print(ans)
        # print(Visited)
        # print(black)
        # print(white)
        black = 0
        white = 0

        for i in range(h):
            for j in range(w):
                if Visited[i][j] == False:
                    c = S[i][j]
                    dq.append([i,j,c])
                    Visited[i][j] = True
                    break
            else:
                continue
            break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from collections import deque
    H, W = (int(i) for i in input().split())
    c = [input() for i in range(H)]
    seen = [[False]*W for _ in range(H)]
    que = deque()
    for h in range(H):
        for w in range(W):
            if c[h][w] == "#":
                que.append((h, w))

    def bfs(sy, sx):
        # dist = [[False]*W for i in range(H)]  # 逆走禁止
        que = deque()
        que.append((sy, sx))
        d = ((1, 0), (0, 1), (-1, 0), (0, -1))
        flag = True  # Trueなら黒マス
        bla = 0
        whi = 0
        while que:
            uh, uw = que.popleft()
            if c[uh][uw] == "#":
                flag = True
                if not(seen[uh][uw]):
                    bla += 1
                    seen[uh][uw] = True
            else:
                flag = False
                if not(seen[uh][uw]):
                    whi += 1
                    seen[uh][uw] = True
            for dy, dx in d:
                next_h = uh + dy
                next_w = uw + dx
                if not(0 <= next_h < H and 0 <= next_w < W):
                    continue
                # if dist[next_h][next_w]:
                #     continue
                if seen[next_h][next_w]:
                    continue
                if flag and c[next_h][next_w] == '#':
                    continue
                if not(flag) and c[next_h][next_w] == '.':
                    continue
                # dist[next_h][next_w] = True
                que.append((next_h, next_w))
        # print(*seen, sep="\n")
        # print(whi, bla)
        return whi*bla

    ans = 0
    for q in que:
        if seen[q[0]][q[1]]:
            continue
        ans += bfs(q[0], q[1])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from collections import deque
    H, W = (int(i) for i in input().split())
    c = [input() for i in range(H)]
    seen = [[False]*W for _ in range(H)]
    que = deque()
    for h in range(H):
        for w in range(W):
            if c[h][w] == "#":
                que.append((h, w))

    def bfs(sy, sx):
        if seen[sy][sx]:
            return 0
        dist = [[False]*W for i in range(H)]  # 逆走禁止
        que = deque()
        que.append((sy, sx))
        d = ((1, 0), (0, 1), (-1, 0), (0, -1))
        flag = True  # Trueなら黒マス
        bla = 0
        whi = 0
        while que:
            uh, uw = que.popleft()
            if c[uh][uw] == "#":
                flag = True
                if not(seen[uh][uw]):
                    bla += 1
                    seen[uh][uw] = True
            else:
                flag = False
                if not(seen[uh][uw]):
                    whi += 1
                    seen[uh][uw] = True
            for dy, dx in d:
                next_h = uh + dy
                next_w = uw + dx
                if not(0 <= next_h < H and 0 <= next_w < W):
                    continue
                if dist[next_h][next_w]:
                    continue
                if flag and c[next_h][next_w] == '#':
                    continue
                if not(flag) and c[next_h][next_w] == '.':
                    continue
                dist[next_h][next_w] = True
                que.append((next_h, next_w))
        # print(*seen, sep="\n")
        # print(whi, bla)
        return whi*bla

    ans = 0
    for q in que:
        ans += bfs(q[0], q[1])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    H, W = (int(i) for i in input().split())
    c = [input() for i in range(H)]
    seen = [[False]*W for _ in range(H)]
    que = deque()
    for h in range(H):
        for w in range(W):
            if c[h][w] == "#":
                que.append((h, w))

    def bfs(sy, sx):
        if seen[sy][sx]:
            return 0
        dist = [[False]*W for i in range(H)]  # 逆走禁止
        que = deque()
        que.append((sy, sx))
        d = ((1, 0), (0, 1), (-1, 0), (0, -1))
        flag = True  # Trueなら黒マス
        bla = 0
        whi = 0
        while que:
            uh, uw = que.popleft()
            if c[uh][uw] == "#":
                flag = True
                if not(seen[uh][uw]):
                    bla += 1
                    seen[uh][uw] = True
            else:
                flag = False
                if not(seen[uh][uw]):
                    whi += 1
                    seen[uh][uw] = True
            for dy, dx in d:
                next_h = uh + dy
                next_w = uw + dx
                if not(0 <= next_h < H and 0 <= next_w < W):
                    continue
                if dist[next_h][next_w]:
                    continue
                if flag and c[next_h][next_w] == '#':
                    continue
                if not(flag) and c[next_h][next_w] == '.':
                    continue
                dist[next_h][next_w] = True
                que.append((next_h, next_w))
        # print(*seen, sep="\n")
        # print(whi, bla)
        return whi*bla

    ans = 0
    for q in que:
        ans += bfs(q[0], q[1])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue
def main():
    h, w = map(int, input().split())
    s = [input().rstrip() for _ in range(h)]
    g = [[0 for j in range(w)] for i in range(h)]
    num = 1
    for i in range(h):
        for j in range(w):
            if g[i][j] != 0:
                continue
            q = queue.Queue()
            q.put([i, j])
            g[i][j] = num
            while not q.empty():
                y, x = q.get()
                if 0 < y and g[y-1][x] == 0 and s[y][x] != s[y-1][x]:
                    g[y-1][x] = num
                    q.put([y-1, x])
                if y < h-1 and g[y+1][x] == 0 and s[y][x] != s[y+1][x]:
                    g[y+1][x] = num
                    q.put([y+1, x])
                if 0 < x and g[y][x-1] == 0 and s[y][x] != s[y][x-1]:
                    g[y][x-1] = num
                    q.put([y, x-1])
                if x < w-1 and g[y][x+1] == 0 and s[y][x] != s[y][x+1]:
                    g[y][x+1] = num
                    q.put([y, x+1])
            num += 1
    blk, wht = [0]*(num+1), [0]*(num+1)
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                blk[g[i][j]] += 1
            else:
                wht[g[i][j]] += 1
    ans = 0
    for i in range(num+1):
        ans += blk[i] * wht[i]
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
black = 0
white = 0
#x,y渡すと、（ｈ、ｗ）に入ってるかどうか判定
def check(s,t):
    if (0 <=  s <= h - 1) and (0 <= t <= w - 1):
        return True
    else:
        return False
def bfs(que):
    finished = set()
    while que:
        x , y, color = que.popleft()
        if x+y*w not in finished:
            finished.add(x+y*w)
            for i in range(-1,2,1):
                for j in range(-1,2,1):
                    if abs(i) + abs(j) < 2 and check(y+j,x+i):
                        if (x+i)+(y+j)*w not in finished:
                            que.append([x+i,y+j,grid[y+j][x+i]])
                        if color != grid[y+j][x+i]:
                            adjacent_list[x+w*y].append((x + i)+w*(y + j))
def dfs(node):
    global white
    global black
    finished.add(node)
    y,x = divmod(node,w)
    if grid[y][x] == '#':
        black += 1
    else:
        white += 1
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i)
from collections import deque
h,w = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
ans = 0
adjacent_list = [[] for i in range(h*w)]
que = deque()
que.append([0,0,grid[0][0]])
bfs(que)
#再び初期化
finished = set()
for i in range(h*w):
    #頂点iからdfsをする。黒と白をカウントしておいて最後にかける
    black = 0
    white = 0
    if i not in finished:
        dfs(i)
        ans += black * white
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
black = 0
white = 0
#x,y渡すと、（ｈ、ｗ）に入ってるかどうか判定
def check(s,t):
    if (0 <=  s <= h - 1) and (0 <= t <= w - 1):
        return True
    else:
        return False
def bfs(que):
    finished = set()
    while que:
        x , y, color = que.popleft()
        if (x,y) not in finished:
            finished.add((x,y))
            for i in range(-1,2,1):
                for j in range(-1,2,1):
                    if abs(i) + abs(j) < 2 and check(y+j,x+i):
                        if (y+j,x+i) not in finished:
                            que.append([x+i,y+j,grid[y+j][x+i]])
                        if color != grid[y+j][x+i]:
                            adjacent_list[x+w*y].append((x + i)+w*(y + j))
def dfs(node):
    global white
    global black
    finished.add(node)
    y,x = divmod(node,w)
    if grid[y][x] == '#':
        black += 1
    else:
        white += 1
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i)
from collections import deque
h,w = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
ans = 0
adjacent_list = [[] for i in range(h*w)]
que = deque()
que.append([0,0,grid[0][0]])
bfs(que)
#再び初期化
finished = set()
for i in range(h*w):
    #頂点iからdfsをする。黒と白をカウントしておいて最後にかける
    black = 0
    white = 0
    if i not in finished:
        dfs(i)
        ans += black * white
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**5)
black = 0
white = 0
#x,y渡すと、（ｈ、ｗ）に入ってるかどうか判定
def check(s,t):
    if (0 <=  s <= h - 1) and (0 <= t <= w - 1):
        return True
    else:
        return False
def bfs(que):
    finished = set()
    while que:
        x , y, color = que.popleft()
        if (x,y) not in finished:
            finished.add((x,y))
            for i in range(-1,2,1):
                for j in range(-1,2,1):
                    if abs(i) + abs(j) < 2 and check(y+j,x+i):
                        que.append([x+i,y+j,grid[y+j][x+i]])
                        if color != grid[y+j][x+i]:
                            adjacent_list[x+w*y].append((x + i)+w*(y + j))
def dfs(node):
    global white
    global black
    finished.add(node)
    y,x = divmod(node,w)
    if grid[y][x] == '#':
        black += 1
    else:
        white += 1
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i)
from collections import deque
h,w = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
ans = 0
adjacent_list = [[] for i in range(h*w)]
que = deque()
que.append([0,0,grid[0][0]])
bfs(que)
#再び初期化
finished = set()
for i in range(h*w):
    #頂点iからdfsをする。黒と白をカウントしておいて最後にかける
    black = 0
    white = 0
    if i not in finished:
        dfs(i)
        ans += black * white
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**5)
black = 0
white = 0
#x,y渡すと、（ｈ、ｗ）に入ってるかどうか判定
def check(s,t):
    if (0 <=  s <= h - 1) and (0 <= t <= w - 1):
        return True
    else:
        return False

def bfs(que):
    finished = set()
    while que:
        x , y, color = que.popleft()
        if (x,y) not in finished:
            finished.add((x,y))
            for i in range(-1,2,1):
                for j in range(-1,2,1):
                    if abs(i) + abs(j) < 2 and check(y+j,x+i):
                        que.append([x+i,y+j,grid[y+j][x+i]])
                        if color != grid[y+j][x+i]:
                            adjacent_list[x+w*y].append((x + i)+w*(y + j))
def dfs(node):
    global white
    global black
    finished.add(node)
    y,x = divmod(node,w)
    if grid[y][x] == '#':
        black += 1
    else:
        white += 1
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i)
from collections import deque
h,w = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
ans = 0
adjacent_list = [[] for i in range(h*w)]
que = deque()
que.append([0,0,grid[0][0]])
bfs(que)
#再び初期化
finished = set()
for i in range(h*w):
    #頂点iからdfsをする。黒と白をカウントしておいて最後にかける
    black = 0
    white = 0
    dfs(i)
    ans += black * white
print(ans)