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:
import copy
from collections import deque
import numpy as np

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


moves = ((1, 0), (-1, 0), (0, 1), (0, -1))

ans = 0

for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            grid = np.full_like(s, 0).astype(int)
            q = deque([(i, j)])
            grid[i][j] = 1
            while q:
                curr = q.popleft()
                cx, cy = curr[0], curr[1]
                for (mx, my) in moves:
                    if 0 <= cx + mx < h and 0 <= cy + my < w and grid[cx + mx][cy + my] == 0:
                        if s[cx][cy] != s[cx + mx][cy + my]:
                            grid[cx + mx][cy + my] = grid[cx][cy] + 1
                            q.append((cx + mx, cy + my))
            grid = grid.flatten()
            grid[np.where(grid == 0)] = 1
            ans += (grid % 2 == 0).sum()
        else:
            continue

print(ans)

Submission status: Time Limit Exceeded

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


moves = ((1, 0), (-1, 0), (0, 1), (0, -1))

ans = 0

for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            grid = copy.deepcopy(s)
            q = deque([(i, j)])
            grid[i][j] = 1
            while q:
                curr = q.popleft()
                cx, cy = curr[0], curr[1]
                for (mx, my) in moves:
                    if 0 <= cx + mx < h and 0 <= cy + my < w and type(grid[cx + mx][cy + my]) != int:
                        if s[cx][cy] != s[cx + mx][cy + my] and grid[cx + mx][cy + my] != 0:
                            grid[cx + mx][cy + my] = grid[cx][cy] + 1
                            q.append((cx + mx, cy + my))
            grid = np.array(grid)
            grid = grid.flatten()
            grid[np.where(grid == "#")] = 1
            grid[np.where(grid == ".")] = 1
            grid[np.where(grid == "0")] = 1
            grid = grid.astype(int)
            ans += (grid % 2 == 0).sum()
        else:
            continue

print(ans)

Submission status: Time Limit Exceeded

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

def dfs(x,y):
    visited = [[0 for _ in range(W)]for _ in range(H)]
    ans = 0
    stack = [(x,y)]
    dx = [0,1]
    dy = [1,0]

    while stack:
        a,b = stack.pop()
        for i in range(2):
            nx = a+dx[i]
            ny = b+dy[i]
            if nx <= H-1 and ny <= W-1:
                if visited[nx][ny]==0:
                    if grid[nx][ny] != grid[a][b]:
                        stack.append((nx,ny))
                        visited[nx][ny] =1
                        if grid[nx][ny] != grid[x][y]:
                            ans +=1
    return ans

answer = 0
for i in range(H):
    for j in range(W):
        answer += dfs(i,j)
print(answer)

Submission status: Time Limit Exceeded

Solution code:
h, w, *s = open(0).read().split()
h = int(h)
w = int(w)

q = []
used = [False] * (h * w)

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#' and not used[i * w + j]:
            bcnt = 0
            cnt = 0

            q.append((i, j))
            used[i * w + j] = True
            cnt += 1
            bcnt += 1

            for y, x in q:
                for dy, dx in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                    ny = y + dy
                    nx = x + dx
                    if 0 <= nx < w and 0 <= ny < h and s[y][x] != s[ny][nx] and not used[ny * w + nx]:
                        q.append((ny, nx))
                        used[ny * w + nx] = True
                        cnt += 1
                        if s[ny][nx] == '#':
                            bcnt += 1
            ans += bcnt * (cnt - bcnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w = map(int, input().split())
s = [input() for i in range(h)]
root = [[0,1],[1,0],[0,-1],[-1,0]]
def bfs(x,y):
  v = [[0 for i in range(w)] for j in range(h)]
  v[x][y]=1
  cnt=0
  d = deque([[x,y]])
  while len(d):
    e,f = d.popleft()
    c = s[e][f]
    for a,b in root:
      x1 = e+a
      y1 = f+b
      if x1>=0 and x1<h and y1>=0 and y1 <w and v[x1][y1]==0:
        if c == '.' and s[x1][y1]=='#':
          v[x1][y1]=1
          d.append([x1,y1])
        if c == '#' and s[x1][y1]=='.':
          v[x1][y1]=1
          d.append([x1,y1])
          cnt+=1
  return cnt

ans=0
for i in range(h):
  for j in range(w):
    if s[i][j]=='#':
      ans+= bfs(i,j)
      
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
def input(): return sys.stdin.readline().rstrip()


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    h, w = map(int, input().split())
    s = [list(input()) for i in range(h)]
    uf = UnionFind(h*w)
    for i in range(h):
        for j in range(w):
            if i != h-1:
                if s[i][j] != s[i+1][j]:
                    uf.union((i*w)+j, (i*w)+j+w)
            if j != w-1:
                if s[i][j] != s[i][j+1]:
                    uf.union((i*w)+j, (i*w)+j+1)
    ans=0
    for item in uf.all_group_members().values():
        A=0
        B=0
        for grid in item:
            i,j=divmod(grid,w)
            if s[i][j]=='.':
                A+=1
            else:
                B+=1
        ans+=A*B
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    h, w = map(int, input().split())
    s = [list(input()) for i in range(h)]
    uf = UnionFind(h*w)
    for i in range(h):
        for j in range(w):
            if i != h-1:
                if s[i][j] != s[i+1][j]:
                    uf.union((i*w)+j, (i*w)+j+w)
            if j != w-1:
                if s[i][j] != s[i][j+1]:
                    uf.union((i*w)+j, (i*w)+j+1)
    ans=0
    for item in uf.all_group_members().values():
        A=0
        B=0
        for grid in item:
            i,j=divmod(grid,w)
            if s[i][j]=='.':
                A+=1
            else:
                B+=1
        ans+=A*B
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
        
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

#初期化
# uf = UnionFind(n)
h,w = inpl()
s = [input() for _ in range(h)]
d = [(1,0),(-1,0),(0,1),(0,-1)]
neg = [set() for _ in range(h*w)]
uf = UnionFind(h*w)
def ind(i,j): return i*w+j
for y in range(h):
    for x in range(w):
        for dy,dx in d:
            ny = y+dy
            nx = x+dx
            if 0 <= ny < h and 0 <= nx < w and s[ny][nx] != s[y][x]:
                uf.union(ind(y,x), ind(ny,nx))

res = 0
for li in uf.all_group_members().values():
    wh = bl = 0
    for va in li:
        y,x = divmod(va,w)
        if s[y][x] == '#': bl += 1
        else: wh += 1
    res += bl*wh
print(res)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1 for _ in range(n)]  # 各要素の親 自分が根の場合は -1 * (木の要素数)

    def root(self, x):  # xが属する木の根を返す
        if self.parents[x] < 0:  # 自分が根の場合
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def merge(self, x, y):  # xが属する木とyが属する木を合体する
        x_root = self.root(x)  # xの根
        y_root = self.root(y)  # yの根

        if x_root == y_root:  # 同じ木に属する
            return

        if self.parents[x_root] > self.parents[y_root]:  # x_rootの要素数 > y_rootの要素数 にする
            x_root, y_root = y_root, x_root

        self.parents[x_root] += self.parents[y_root]
        self.parents[y_root] = x_root

    def size(self, x):  # xが属する木の要素数
        return -self.parents[self.root(x)]

    def same(self, x, y):  # xとyが同じ木に属するか判定
        return self.root(x) == self.root(y)

    def roots(self):  # すべての根を求める
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):  # 木が何個あるか
        return len(self.roots())

    def members(self, x):  # xが属する木の要素を列挙
        x_root = self.root(x)
        return [i for i in range(self.n) if self.root(i) == x_root]

    def all_group_members(self):  # すべての根の要素を列挙
        return {root: self.members(root) for root in self.roots()}


def main():
    h, w = map(int, input().split())
    grid = [list(input()) for _ in range(h)]
    uf = UnionFind(h * w)

    for r in range(h):
        for c in range(w):
            for dr, dc in [[0, 1], [1, 0]]:
                nr = r + dr
                nc = c + dc
                if not (0 <= nr < h and 0 <= nc < w):
                    continue
                if grid[r][c] != grid[nr][nc]:
                    uf.merge(r * w + c, nr * w + nc)

    ans = 0
    for tree in list(uf.all_group_members().values()):
        black, white = 0, 0
        for num in tree:
            if grid[num // w][num % w] == "#":
                black += 1
            else:
                white += 1
        ans += black * white

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1 for _ in range(n)]  # 各要素の親 自分が根の場合は -1 * (木の要素数)

    def root(self, x):  # xが属する木の根を返す
        if self.parents[x] < 0:  # 自分が根の場合
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def merge(self, x, y):  # xが属する木とyが属する木を合体する
        x_root = self.root(x)  # xの根
        y_root = self.root(y)  # yの根

        if x_root == y_root:  # 同じ木に属する
            return

        if abs(self.parents[x_root]) >= abs(self.parents[y_root]):  # 要素数の比較
            self.parents[x_root] += self.parents[y_root]
            self.parents[y_root] = x_root
        else:
            self.parents[y_root] += self.parents[x_root]
            self.parents[x_root] = y_root

    def size(self, x):  # xが属する木の要素数
        return -self.parents[self.root(x)]

    def same(self, x, y):  # xとyが同じ木に属するか判定
        return self.root(x) == self.root(y)

    def roots(self):  # すべての根を求める
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):  # 木が何個あるか
        return len(self.roots())

    def members(self, x):  # xが属する木の要素を列挙
        x_root = self.root(x)
        return [i for i in range(self.n) if self.root(i) == x_root]

    def all_group_members(self):  # すべての根の要素を列挙
        return {root: self.members(root) for root in self.roots()}


def main():
    h, w = map(int, input().split())
    s_list = [list(input()) for _ in range(h)]
    num_list = [0 for _ in range(h * w)]
    for i in range(h):
        for j in range(w):
            if s_list[i][j] == "#":
                num_list[i * w + j] = "#"
            else:
                num_list[i * w + j] = "."
    uf = UnionFind(h * w)

    for r in range(h):
        for c in range(w):
            nc = c + 1
            nr = r + 1
            if s_list[r][c] == "#":
                if nc < w and s_list[r][nc] == ".":
                    uf.merge(r * w + c, r * w + nc)
                if nr < h and s_list[nr][c] == ".":
                    uf.merge(r * w + c, nr * w + c)
            else:
                if nc < w and s_list[r][nc] == "#":
                    uf.merge(r * w + c, r * w + nc)
                if nr < h and s_list[nr][c] == "#":
                    uf.merge(r * w + c, nr * w + c)

    ans = 0
    for tree in list(uf.all_group_members().values()):
        cnt1 = 0
        cnt2 = 0
        for num in tree:
            if num_list[num] == "#":
                cnt1 += 1
            else:
                cnt2 += 1
        ans += cnt1 * cnt2

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1 for _ in range(n)]  # 各要素の親 自分が根の場合は -1 * (木の要素数)

    def root(self, x):  # xが属する木の根を返す
        if self.parents[x] < 0:  # 自分が根の場合
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def merge(self, x, y):  # xが属する木とyが属する木を合体する
        x_root = self.root(x)  # xの根
        y_root = self.root(y)  # yの根

        if x_root == y_root:  # 同じ木に属する
            return

        if abs(self.parents[x_root]) >= abs(self.parents[y_root]):  # 要素数の比較
            self.parents[x_root] += self.parents[y_root]
            self.parents[y_root] = x_root
        else:
            self.parents[y_root] += self.parents[x_root]
            self.parents[x_root] = y_root

    def size(self, x):  # xが属する木の要素数
        return -self.parents[self.root(x)]

    def same(self, x, y):  # xとyが同じ木に属するか判定
        return self.root(x) == self.root(y)

    def roots(self):  # すべての根を求める
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):  # 木が何個あるか
        return len(self.roots())

    def members(self, x):  # xが属する木の要素を列挙
        x_root = self.root(x)
        return [i for i in range(self.n) if self.root(i) == x_root]

    def all_group_members(self):  # すべての根の要素を列挙
        return {root: self.members(root) for root in self.roots()}


def main():
    h, w = map(int, input().split())
    s_list = [list(input()) for _ in range(h)]
    uf = UnionFind(h * w)

    for r in range(h):
        for c in range(w):
            if s_list[r][c] == "#":
                if c + 1 < w:
                    if s_list[r][c + 1] == ".":
                        uf.merge(r * w + c, r * w + c + 1)
                if r + 1 < h:
                    if s_list[r + 1][c] == ".":
                        uf.merge(r * w + c, (r + 1) * w + c)
            elif s_list[r][c] == ".":
                if c + 1 < w:
                    if s_list[r][c + 1] == "#":
                        uf.merge(r * w + c, r * w + c + 1)
                if r + 1 < h:
                    if s_list[r + 1][c] == "#":
                        uf.merge(r * w + c, (r + 1) * w + c)

    ans = 0
    # for i in range(uf.group_count()):
    #     cnt1 = 0
    #     cnt2 = 0
    #     for num in list(uf.all_group_members().values())[i]:
    #         if s_list[num // w][num % w] == "#":
    #             cnt1 += 1
    #         else:
    #             cnt2 += 1
    #     ans += cnt1 * cnt2

    # print(ans)

    for tree in list(uf.all_group_members().values()):
        cnt1 = 0
        cnt2 = 0
        for num in tree:
            if s_list[num // w][num % w] == "#":
                cnt1 += 1
            else:
                cnt2 += 1
        ans += cnt1 * cnt2

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1 for _ in range(n)]  # 各要素の親 自分が根の場合は -1 * (木の要素数)

    def root(self, x):  # xが属する木の根を返す
        if self.parents[x] < 0:  # 自分が根の場合
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def merge(self, x, y):  # xが属する木とyが属する木を合体する
        x_root = self.root(x)  # xの根
        y_root = self.root(y)  # yの根

        if x_root == y_root:  # 同じ木に属する
            return

        if abs(self.parents[x_root]) >= abs(self.parents[y_root]):  # 要素数の比較
            self.parents[x_root] += self.parents[y_root]
            self.parents[y_root] = x_root
        else:
            self.parents[y_root] += self.parents[x_root]
            self.parents[x_root] = y_root

    def size(self, x):  # xが属する木の要素数
        return -self.parents[self.root(x)]

    def same(self, x, y):  # xとyが同じ木に属するか判定
        return self.root(x) == self.root(y)

    def roots(self):  # すべての根を求める
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):  # 木が何個あるか
        return len(self.roots())

    def members(self, x):  # xが属する木の要素を列挙
        x_root = self.root(x)
        return [i for i in range(self.n) if self.root(i) == x_root]

    def all_group_members(self):  # すべての根の要素を列挙
        return {root: self.members(root) for root in self.roots()}


def main():
    h, w = map(int, input().split())
    s_list = [list(input()) for _ in range(h)]
    num_list = [[0 for _ in range(w)] for _ in range(h)]
    for i in range(h):
        for j in range(w):
            num_list[i][j] = i * w + j

    uf = UnionFind(h * w)

    for r in range(h):
        for c in range(w):
            if s_list[r][c] == "#":
                if c + 1 < w:
                    if s_list[r][c + 1] == ".":
                        uf.merge(num_list[r][c], num_list[r][c + 1])
                if r + 1 < h:
                    if s_list[r + 1][c] == ".":
                        uf.merge(num_list[r][c], num_list[r + 1][c])
            if s_list[r][c] == ".":
                if c + 1 < w:
                    if s_list[r][c + 1] == "#":
                        uf.merge(num_list[r][c], num_list[r][c + 1])
                if r + 1 < h:
                    if s_list[r + 1][c] == "#":
                        uf.merge(num_list[r][c], num_list[r + 1][c])

    ans = 0
    for i in range(uf.group_count()):
        cnt1 = 0
        cnt2 = 0
        for num in list(uf.all_group_members().values())[i]:
            if s_list[num // w][num % w] == "#":
                cnt1 += 1
            else:
                cnt2 += 1
        ans += cnt1 * cnt2

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int,input().split())
grid = [0] * H
for i in range(H):
    grid[i] = input()
start_points = []
for y in range(H):
    for x in range(W):
        if grid[y][x] == '#':
            start_points.append([y,x])

ans = 0
for sy, sx in start_points:
    q = deque()
    q.append([sy,sx])
    done = [[0]*W for _ in range(H)]
    done[sy][sx] = 1
    while q:
        y,x = q.popleft()
        now = grid[y][x]
        for new_y, new_x in [[y+1,x],[y,x+1],[y-1,x],[y,x-1]]:
            if 0<= new_y < H and 0<= new_x < W and not done[new_y][new_x]:
                if grid[y][x] != grid[new_y][new_x]:
                    # 白ならans++
                    if grid[new_y][new_x] == '.':
                        ans+= 1
                    
                    q.append([new_y,new_x])
                    done[new_y][new_x] = 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

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

def isOK(start,goal):
    q =  collections.deque([start])
    dp = [[0]*W for _ in range(H)]
    while q:
        nowh,noww = q.popleft()
        dp[nowh][noww] = 1
        if s[nowh][noww] == '.':
            target_mark = '#'
        else:
            target_mark = '.'
            
        if nowh >0 and s[nowh-1][noww] == target_mark and dp[nowh-1][noww]==0:
            q.append((nowh-1,noww))
            if (nowh-1,noww)==goal:
                return True

        if nowh <H-1 and s[nowh+1][noww] == target_mark and dp[nowh+1][noww]==0:
            q.append((nowh+1,noww))
            if (nowh+1,noww)==goal:
                return True
            
        if noww > 0 and s[nowh][noww-1] == target_mark and dp[nowh][noww-1]==0:
            q.append((nowh,noww-1))
            if (nowh,noww-1)==goal:
                return True

        if noww < W-1 and s[nowh][noww+1] == target_mark and dp[nowh][noww+1]==0:
            q.append((nowh,noww+1))
            if (nowh,noww+1)==goal:
                return True
    return False

cnt = 0

start_candi = []
end_candi = []
for ih in range(H):
    for iw in range(W):
        if s[ih][iw] == '#':
            start_candi.append((ih,iw))
        else:
            end_candi.append((ih,iw))

for start in start_candi:
    for end in end_candi:
        flag = abs(start[0]-end[0])+abs(start[1]-end[1])
        if flag%2==1:
            cnt += isOK(start,end)
        else:
            continue

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

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

def isOK(start,goal):
    q =  collections.deque([start])
    dp = [[0]*W for _ in range(H)]
    while q:
        nowh,noww = q.popleft()
        dp[nowh][noww] = 1
        if s[nowh][noww] == '.':
            target_mark = '#'
        else:
            target_mark = '.'
            
        if nowh >0 and s[nowh-1][noww] == target_mark and dp[nowh-1][noww]==0:
            q.append((nowh-1,noww))
            if (nowh-1,noww)==goal:
                return True

        if nowh <H-1 and s[nowh+1][noww] == target_mark and dp[nowh+1][noww]==0:
            q.append((nowh+1,noww))
            if (nowh+1,noww)==goal:
                return True
            
        if noww > 0 and s[nowh][noww-1] == target_mark and dp[nowh][noww-1]==0:
            q.append((nowh,noww-1))
            if (nowh,noww-1)==goal:
                return True

        if noww < W-1 and s[nowh][noww+1] == target_mark and dp[nowh][noww+1]==0:
            q.append((nowh,noww+1))
            if (nowh,noww+1)==goal:
                return True
    return False

cnt = 0

for iw in range(W):
    for ih in range(H):
        if s[ih][iw] =='#':
            start = (ih,iw)
        else:
            continue
        for giw in range(W):
            for gih in range(H):
                flag = abs(iw-giw)+abs(ih-gih)
                if flag%2==1 and s[gih][giw] == '.':
                    goal = (gih,giw)
                    cnt += isOK(start,goal)
                else:
                    continue
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input().rstrip())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7
    
    #https://note.nkmk.me/python-union-find/
    
    class UnionFind():
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n
    
        def find(self, x):
            if self.parents[x] < 0:
                return x
            else:
                self.parents[x] = self.find(self.parents[x])
                return self.parents[x]
    
        def union(self, x, y):
            x = self.find(x)
            y = self.find(y)
    
            if x == y:
                return
    
            if self.parents[x] > self.parents[y]:
                x, y = y, x
    
            self.parents[x] += self.parents[y]
            self.parents[y] = x
    
        def size(self, x):
            return -self.parents[self.find(x)]
    
        def same(self, x, y):
            return self.find(x) == self.find(y)
    
        def members(self, x):
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]
    
        def roots(self):
            return [i for i, x in enumerate(self.parents) if x < 0]
    
        def group_count(self):
            return len(self.roots())
    
        def all_group_members(self):
            return {r: self.members(r) for r in self.roots()}
    
        def __str__(self):
            return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    
    h,w=MI()
    uf=UnionFind(h*w)
    lis=[[0]*w for i in range(h)]
    for i in range(h):
        s=SI()
        for j in range(w):
            if s[j]=="#":
                lis[i][j]=1
    step=[[0,1],[0,-1],[-1,0],[1,0]]
    for i in range(h):
        for j in range(w):
            for x,y in step:
                if not (0<=i+x<h and 0<=j+y<w):
                    continue
                if lis[i][j]!=lis[i+x][j+y]:
                    uf.union(w*i+j,w*(i+x)+(j+y))
    ans=0
    #print(ans)
    for z in uf.roots():
        s=0
        b=0
        for node in uf.members(z):
            if lis[node//w][node%w]==1:
                b+=1
            else:
                s+=1
        ans+=b*s
    print(ans)
if __name__=="__main__":
    main()