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

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, node):
        self.parent = [-1 for _ in range(node)]
        self.node = node

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

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

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return
        if self.parent[root_x] > self.parent[root_y]:
            root_x, root_y = root_y, root_x
        self.parent[root_x] += self.parent[root_y]
        self.parent[root_y] = root_x

    def get_size(self, x):
        return -self.parent[self.find(x)]

    def get_root(self):
        return [i for i, root in enumerate(self.parent) if root < 0]

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

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


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

    def grid_num(i, j):
        return w * (i - 1) + j - 1

    for i in range(1, h + 1):
        for j in range(1, w + 1):
            for di, dj in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
                ni = i + di
                nj = j + dj
                if grid[ni][nj] == "*":
                    continue
                elif grid[i][j] != grid[ni][nj]:
                    uf.union(grid_num(i, j), grid_num(ni, nj))
            if grid[i][j] == "#":
                all_black.append([i, j])
    ans = 0
    root = []
    member = uf.all_group_members()
    member_set = {}
    for r, m in member.items():
        member_set[r] = set(m)
        root.append(r)
    black = {r: 0 for r in root}
    for i, j in all_black:
        if grid[i][j] == "#":
            now = grid_num(i, j)
            for r in root:
                if now in member_set[r]:
                    black[r] += 1
                    break
    for r in root:
        ans += black[r] * (len(member[r]) - black[r])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, node):
        self.parent = [-1 for _ in range(node)]
        self.node = node

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

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

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return
        if self.parent[root_x] > self.parent[root_y]:
            root_x, root_y = root_y, root_x
        self.parent[root_x] += self.parent[root_y]
        self.parent[root_y] = root_x

    def get_size(self, x):
        return -self.parent[self.find(x)]

    def get_root(self):
        return [i for i, root in enumerate(self.parent) if root < 0]

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

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


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

    def grid_num(i, j):
        return w * (i - 1) + j - 1

    for i in range(1, h + 1):
        for j in range(1, w + 1):
            for di, dj in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
                ni = i + di
                nj = j + dj
                if grid[ni][nj] == "*":
                    continue
                elif grid[i][j] != grid[ni][nj]:
                    uf.union(grid_num(i, j), grid_num(ni, nj))
    ans = 0
    root = uf.get_root()
    member = uf.all_group_members()
    member_set = {}
    for r, m in member.items():
        member_set[r] = set(m)
    black = {r: 0 for r in root}
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            if grid[i][j] == "#":
                now = grid_num(i, j)
                for r in root:
                    if now in member_set[r]:
                        black[r] += 1
                        break
    for r in root:
        ans += black[r] * (len(member[r]) - black[r])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, node):
        self.parent = [-1 for _ in range(node)]
        self.node = node

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

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

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return
        if self.parent[root_x] > self.parent[root_y]:
            root_x, root_y = root_y, root_x
        self.parent[root_x] += self.parent[root_y]
        self.parent[root_y] = root_x

    def get_size(self, x):
        return -self.parent[self.find(x)]

    def get_root(self):
        return [i for i, root in enumerate(self.parent) if root < 0]

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

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


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

    def grid_num(i, j):
        return w * (i - 1) + j - 1

    for i in range(1, h + 1):
        for j in range(1, w + 1):
            for di, dj in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
                ni = i + di
                nj = j + dj
                if grid[ni][nj] == "*":
                    continue
                elif grid[i][j] != grid[ni][nj]:
                    uf.union(grid_num(i, j), grid_num(ni, nj))
    ans = 0
    root = uf.get_root()
    member = uf.all_group_members()
    black = {r: 0 for r in root}
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            if grid[i][j] == "#":
                for r in root:
                    if uf.is_same(grid_num(i, j), r):
                        black[r] += 1
                        break
    for r in root:
        ans += black[r] * (len(member[r]) - black[r])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

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

# 約数生成
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


def main():

    inf = 10 ** 18
    mod = 10 ** 9 + 7

    h,w = lr()
    s = [sr() for i in range(h)]
    uf = UnionFind(h*w)
    for i in range(h):
        for j in range(w):
            for y,x in [[1,0],[0,1]]:
                nh,nw = i+y,j+x
                if 0 <= nh < h and 0 <= nw < w:
                    if s[i][j] != s[nh][nw]:
                        uf.union(i*w+j, nh*w+nw)
    ans = 0
    for _,v in uf.all_group_members().items():
        b = 0
        c = 0
        for tmp in v:
            y = tmp // w
            x = tmp % w
            if s[y][x] == '.':
                c += 1
            else:
                b += 1
        ans += b * c
        
        
    print(ans)
    
    
    return None

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

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

# 約数生成
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


inf = 10 ** 18
mod = 10 ** 9 + 7

h,w = lr()
s = [sr() for i in range(h)]
uf = UnionFind(h*w)
for i in range(h):
    for j in range(w):
        for y,x in [[1,0],[0,1]]:
            nh,nw = i+y,j+x
            if 0 <= nh < h and 0 <= nw < w:
                if s[i][j] != s[nh][nw]:
                    uf.union(i*w+j, nh*w+nw)
ans = 0
for _,v in uf.all_group_members().items():
    b = 0
    c = 0
    for tmp in v:
        y = tmp // w
        x = tmp % w
        if s[y][x] == '.':
            c += 1
        else:
            b += 1
    ans += b * c
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

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

# 要素が整数じゃなければ、以下の継承したやつを使う
class UnionFindLabel(UnionFind):
    def __init__(self, labels):
        assert len(labels) == len(set(labels))

        self.n = len(labels)
        self.parents = [-1] * self.n
        self.d = {x: i for i, x in enumerate(labels)}
        self.d_inv = {i: x for i, x in enumerate(labels)}

    def find_label(self, x):
        return self.d_inv[super().find(self.d[x])]

    def union(self, x, y):
        super().union(self.d[x], self.d[y])

    def size(self, x):
        return super().size(self.d[x])

    def same(self, x, y):
        return super().same(self.d[x], self.d[y])

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

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

# 約数生成
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


inf = 10 ** 18
mod = 10 ** 9 + 7

h,w = lr()
s = [sr() for i in range(h)]
labels = [(i,j) for j in range(w) for i in range(h)]
uf = UnionFindLabel(labels)
for i in range(h):
    for j in range(w):
        for y,x in [[1,0],[-1,0],[0,1],[0,-1]]:
            nh,nw = i+y,j+x
            if 0 <= nh < h and 0 <= nw < w:
                if s[i][j] != s[nh][nw]:
                    uf.union((i,j), (nh,nw))
ans = 0
for t in uf.roots():
    b = 0
    c = 0
    for tmp in uf.members(t):
        if s[tmp[0]][tmp[1]] == '.':
            c += 1
        else:
            b += 1
    ans+=b*c
print(ans)

Submission status: Time Limit Exceeded

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

g = [[] for _ in range(h*w)]
for y in range(h):
    for x in range(w):
        idx1 = y*w+x
        for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
            ny, nx = y+dy, x+dx
            if 0 <= ny < h and 0 <= nx < w:
                idx2 = ny*w+nx
                if S[y][x] != S[ny][nx]:
                    g[idx1].append(idx2)

ans = 0
for i in range(h*w):
    s = []
    s.append(i)
    visit = [-1]*(h*w)
    visit[i] = 0
    while s:
        v = s.pop()
        for  u in g[v]:
            if visit[u] == -1:
                visit[u] = visit[v]+1
                if visit[u]%2 == 1:
                    ans += 1
                s.append(u)
print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0
  for i in range(h):
    for j in range(w):
      if field[i][j]=='#':
        q=collections.deque()
        visited=[[False]*w for _ in range(h)]
        q.append((i,j))
        while q:
          y,x=q.popleft()
          if visited[y][x]:
            continue
          visited[y][x]=True
          for dy,dx in dd:
            ny=y+dy
            nx=x+dx
            if 0<=ny<h and 0<=nx<w:
              if field[y][x]==field[ny][nx]:
                continue
              if visited[ny][nx]:
                continue
              if field[ny][nx]=='.':
                ans+=1
              q.append((ny,nx))
    # print(ans)
  return ans

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0
  for i in range(h):
    for j in range(w):

      if field[i][j]=='#':
        q=collections.deque()
        visited=[[False]*w for _ in range(h)]
        q.append((i,j))
        while q:
          y,x=q.popleft()
          if visited[y][x]:
            continue
          visited[y][x]=True
          for dy,dx in dd:
            ny=y+dy
            nx=x+dx

            if 0<=ny<h and 0<=nx<w:
              if visited[ny][nx]:
                continue
              if field[ny][nx]=='#':
                continue
              visited[ny][nx]=True #忘れがち
              # print(i,j,ny,nx)
              ans+=1
              for ddy,ddx in dd:
                nny=ny+ddy
                nnx=nx+ddx
                if 0<=nny<h and 0<=nnx<w:
                  if visited[nny][nnx]:
                    continue
                  if field[nny][nnx]=='.':
                    continue
                  q.append((nny,nnx))

      # print(ans)
  return ans

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0
  for i in range(h):
    for j in range(w):

      if field[i][j]=='#':
        q=collections.deque()
        visited=[[False]*w for _ in range(h)]
        q.append((i,j))
        while q:
          y,x=q.popleft()
          visited[y][x]=True
          for dy,dx in dd:
            ny=y+dy
            nx=x+dx

            if 0<=ny<h and 0<=nx<w:
              if visited[ny][nx]:
                continue
              if field[ny][nx]=='#':
                continue
              visited[ny][nx]=True #忘れがち
              # print(i,j,ny,nx)
              ans+=1
              for ddy,ddx in dd:
                nny=ny+ddy
                nnx=nx+ddx
                if 0<=nny<h and 0<=nnx<w:
                  if visited[nny][nnx]:
                    continue
                  if field[nny][nnx]=='.':
                    continue
                  q.append((nny,nnx))

      # print(ans)
  return ans

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0
  for i in range(h):
    for j in range(w):

      q=collections.deque()
      if field[i][j]=='#':
        visited=[[False]*w for _ in range(h)]
        q.append((i,j))
        while q:
          y,x=q.popleft()
          visited[y][x]=True
          for dy,dx in dd:
            ny=y+dy
            nx=x+dx

            if 0<=ny<h and 0<=nx<w:
              if visited[ny][nx]:
                continue
              if field[ny][nx]=='#':
                continue
              visited[ny][nx]=True #忘れがち
              # print(i,j,ny,nx)
              ans+=1
              for ddy,ddx in dd:
                nny=ny+ddy
                nnx=nx+ddx
                if 0<=nny<h and 0<=nnx<w:
                  if visited[nny][nnx]:
                    continue
                  if field[nny][nnx]=='.':
                    continue
                  q.append((nny,nnx))

      # print(ans)
  return ans

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(100000)


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

def rec(h,w):
    seen[h][w]=1
    step=[[0,1],[0,-1],[1,0],[-1,0]]
    ret=0
    for dh,dw in step:
        nh=h+dh
        nw=w+dw
        if 0<=nh<H and 0<=nw<W:
            if seen[nh][nw]==0 and S[nh][nw]==".":
                ret+=1
                seen[nh][nw]=1
                for ddh,ddw in step:
                    if 0<=nh + ddh<H and 0<=nw + ddw < W:
                        if seen[nh+ddh][nw+ddw]==0 and S[nh+ddh][nw+ddw]=="#":
                            ret+=rec(nh+ddh,nw+ddw)
    return ret


ans=0
for h in range(H):
    for w in range(W):
        seen=[[0]*W for _ in range(H)]
        if S[h][w]=="#":
            ans+=rec(h,w)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w = map(int,input().split())
s = [0]*(h+2)
s[0] = [0]*(w+2)
s[-1] = [0]*(w+2)

for i in range(1,h+1):
    s[i] = [0] + list(input()) + [0]

ans = 0
for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j] != "#":
            pass
        else:
            q = deque([])
            q.append([i,j,1])
            reach =  [[0 for j in range(w+2)] for i in range(h+2)]
            reach[i][j] = 1
            while q:
                [x,y,state] = q.popleft()
                if reach[x-1][y] == 0:
                    if state == 1 and s[x-1][y] == ".":
                        q.append([x-1,y,0])
                        reach[x-1][y] = 1
                        ans += 1
                    elif state == 0 and s[x-1][y] == "#":
                        q.append([x-1,y,1])
                        reach[x-1][y] = 1
                
                if reach[x+1][y] == 0:
                    if state == 1 and s[x+1][y] == ".":
                        q.append([x+1,y,0])
                        reach[x+1][y] = 1
                        ans += 1
                    elif state == 0 and s[x+1][y] == "#":
                        q.append([x+1,y,1])
                        reach[x+1][y] = 1
                
                if reach[x][y-1] == 0:
                    if state == 1 and s[x][y-1] == ".":
                        q.append([x,y-1,0])
                        reach[x][y-1] = 1
                        ans += 1
                    elif state == 0 and s[x][y-1] == "#":
                        q.append([x,y-1,1])
                        reach[x][y-1] = 1
                
                if reach[x][y+1] == 0:
                    if state == 1 and s[x][y+1] == ".":
                        q.append([x,y+1,0])
                        reach[x][y+1] = 1
                        ans += 1
                    elif state == 0 and s[x][y+1] == "#":
                        q.append([x,y+1,1])
                        reach[x][y+1] = 1
print(ans)