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:

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())
    ls=[input() for _ in range(h)]
    s=[[] for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if ls[i][j]=="#":
                s[i].append(1)
            else:
                s[i].append(0)

    u=UnionFind(h*w)

    for i in range(h):
        for j in range(w):
            if j !=0:
                if s[i][j-1] != s[i][j]:
                    u.union(i*w+j-1,i*w+j)
                    u.find(i*w+j)
            if i !=0:
                if s[i-1][j] != s[i][j]:
                    u.union((i-1)*w+j,i*w+j)
                    u.find(i*w+j)
    res = 0
    for i in range(h*w):
        for j in range(i,h*w):
            if s[i//w][i%w] != s[j//w][j%w]:
                if u.same(i,j):
                    res += 1
    print(res)

main()

Submission status: Time Limit Exceeded

Solution code:

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())
    ls=[input() for _ in range(h)]
    s=[[] for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if ls[i][j]=="#":
                s[i].append(1)
            else:
                s[i].append(0)

    u=UnionFind(h*w)

    for i in range(h):
        for j in range(w):
            if j !=0:
                if s[i][j-1] != s[i][j]:
                    u.union(i*w+j-1,i*w+j)
            if i !=0:
                if s[i-1][j] != s[i][j]:
                    u.union((i-1)*w+j,i*w+j)
    res = 0
    for i in range(h*w):
        for j in range(i,h*w):
            if s[i//w][i%w] != s[j//w][j%w]:
                if u.same(i,j):
                    res += 1
    print(res)

main()

Submission status: Time Limit Exceeded

Solution code:

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=[input() for _ in range(h)]

    u=UnionFind(h*w)

    for i in range(h):
        for j in range(w):
            if j !=0:
                if s[i][j-1] != s[i][j]:
                    u.union(i*w+j-1,i*w+j)
            if i !=0:
                if s[i-1][j] != s[i][j]:
                    u.union((i-1)*w+j,i*w+j)
    res = 0
    for i in range(h*w):
        for j in range(i,h*w):
            if s[i//w][i%w] != s[j//w][j%w]:
                if u.same(i,j):
                    res += 1
    print(res)

main()

Submission status: Time Limit Exceeded

Solution code:

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

import sys
sys.setrecursionlimit(10**7)

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

u=UnionFind(h*w)

for i in range(h):
    for j in range(w):
        if j !=0:
            if s[i][j-1] != s[i][j]:
                u.union(i*w+j-1,i*w+j)
        if i !=0:
            if s[i-1][j] != s[i][j]:
                u.union((i-1)*w+j,i*w+j)
res = 0
for i in range(h*w):
    for j in range(i,h*w):
        if s[i//w][i%w] != s[j//w][j%w]:
            if u.same(i,j):
                res += 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

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

seen = [[False for _ in range(W)] for _ in range(H)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
numb = 0
numw = 0

def dfs(y,x):
  global numb
  global numw
  seen[y][x] = True
  if S[y][x] == '#':
    numb += 1
  if S[y][x] == '.':
    numw += 1
  for i in range(4):
    if not(0<=y+dy[i]<H) or not(0<=x+dx[i]<W):
      continue
    if seen[y+dy[i]][x+dx[i]]:
      continue
    if S[y][x] == S[y+dy[i]][x+dx[i]]:
      continue
    dfs(y+dy[i],x+dx[i])

ans = 0
for i in range(H):
  for j in range(W):
    numb = 0
    numw = 0
    if S[i][j] == '#' and not seen[i][j]:
      dfs(i,j)
      ans += numb * numw
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

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

seen = [[False for _ in range(W)] for _ in range(H)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
numb = 0
numw = 0

def dfs(y,x):
  global numb
  global numw
  seen[y][x] = True
  if S[y][x] == '#':
    numb += 1
  if S[y][x] == '.':
    numw += 1
  for i in range(4):
    if not(0<=y+dy[i]<H) or not(0<=x+dx[i]<W):
      continue
    if seen[y+dy[i]][x+dx[i]]:
      continue
    if S[y][x] == S[y+dy[i]][x+dx[i]]:
      continue
    dfs(y+dy[i],x+dx[i])

ans = 0
for i in range(H):
  for j in range(W):
    numb = 0
    numw = 0
    if S[i][j] == '#':
      dfs(i,j)
      ans += numb * numw
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

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

seen = [[False for _ in range(W)] for _ in range(H)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
numb = 0
numw = 0

def dfs(y,x):
  global numb
  global numw
  seen[y][x] = True
  if S[y][x] == '#':
    numb += 1
  if S[y][x] == '.':
    numw += 1
  for i in range(4):
    if not(0<=y+dy[i]<H) or not(0<=x+dx[i]<W):
      continue
    if seen[y+dy[i]][x+dx[i]]:
      continue
    if S[y][x] == S[y+dy[i]][x+dx[i]]:
      continue
    dfs(y+dy[i],x+dx[i])

ans = 0
for i in range(H):
  for j in range(W):
    numb = 0
    numw = 0
    if S[i][j] == '#':
      dfs(i,j)
      ans += numb * numw
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

q=deque()
ans=0

def bfs(i,j):
    global ans
    q.append((i,j))
    while q:
        y,x=q.popleft()
        if s[y][x]=='#':
            ans+=1
        for dy,dx in ((1,0),(0,1),(-1,0),(0,-1)):
            ny = y+dy
            nx = x+dx
            if 0<=ny<h and 0<=nx<w and s[y][x]!=s[ny][nx] and field[ny][nx]==False:
                field[ny][nx]=True
                q.append((ny,nx))

                         
for i in range(h):
    for j in range(w):
        if s[i][j]=='.':
            field=[[False]*w for j in range(h)]
            field[i][j]=True
            bfs(i,j)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

q=deque()
ans=0

def bfs(i,j):
    global ans
    q.append((i,j))
    while q:
        y,x=q.popleft()
        field[y][x]=1
        if s[y][x]=='#':
            ans+=1
        for dy,dx in ((1,0),(0,1),(-1,0),(0,-1)):
            ny = y+dy
            nx = x+dx
            if 0<=ny<h and 0<=nx<w and s[y][x]!=s[ny][nx] and field[ny][nx]==float('inf'):
                field[ny][nx]=1
                q.append((ny,nx))

                         
for i in range(h):
    for j in range(w):
        if s[i][j]=='.':
            field=[[float('inf') for i in range(w)] for j in range(h)]
            bfs(i,j)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)

h,w = map(int, input().split())
board = [[int(j=="#") for j in input()] for i in range(h)]
dxdy = [[0,1],[1,0],[0,-1],[-1,0]]

def dfs(i, j, k, prev):
    if used[i][j] or board[i][j] == prev:
        return
    used[i][j] = 1
    k[board[i][j]] += 1
    for dx, dy in dxdy:
        nx, ny = i+dx, j+dy
        if 0 <= nx < h and 0 <= ny < w and not used[nx][ny] and board[nx][ny] != board[i][j]:
            dfs(nx,ny,k,board[i][j])

used = [[0]*w for i in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if used[i][j]:
            continue
        k = [0]*2
        dfs(i,j,k, -1)
        ans += k[0]*k[1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)

h,w = map(int, input().split())
board = [[int(j=="#") for j in input()] for i in range(h)]
dxdy = [(0,1),(1,0),(0,-1),(-1,0)]

def dfs(i, j, k, prev):
    if used[i][j] or board[i][j] == prev:
        return
    used[i][j] = 1
    k[board[i][j]] += 1
    for dx, dy in dxdy:
        nx, ny = i+dx, j+dy
        if 0 <= nx < h and 0 <= ny < w and not used[nx][ny] and board[nx][ny] != board[i][j]:
            dfs(nx,ny,k,board[i][j])

used = [[0]*w for i in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if used[i][j]:
            continue
        k = [0]*2
        dfs(i,j,k, -1)
        ans += k[0]*k[1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)

h,w = map(int, input().split())
board = [[int(j=="#") for j in input()] for i in range(h)]
dxdy = [(0,1),(1,0),(0,-1),(-1,0)]

def dfs(i, j, k, prev):
    if used[i][j] or board[i][j] == prev:
        return
    used[i][j] = 1
    k[board[i][j]] += 1
    for dx, dy in dxdy:
        nx, ny = i+dx, j+dy
        if 0 <= nx < h and 0 <= ny < w and board[nx][ny] != board[i][j]:
            dfs(nx,ny,k,board[i][j])

used = [[0]*w for i in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if used[i][j]:
            continue
        k = [0]*2
        dfs(i,j,k, -1)
        ans += k[0]*k[1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)

h,w = map(int, input().split())
board = [list(input()) for i in range(h)]
#print(*board, sep="\n")
dxdy = [(0,1),(1,0),(0,-1),(-1,0)]

def dfs(i, j, k, prev):
    if used[i][j] or board[i][j] == prev:
        return
    used[i][j] = 1
    k[board[i][j] == "."] += 1
    for dx, dy in dxdy:
        nx, ny = i+dx, j+dy
        if 0 <= nx < h and 0 <= ny < w and board[nx][ny] != board[i][j]:
            dfs(nx,ny,k,board[i][j])

used = [[0]*w for i in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if used[i][j]:
            continue
        k = [0]*2
        dfs(i,j,k, "1")
        ans += k[0]*k[1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:

def main():
    H,W = map(int, input().split())

    S = [list(input()) for _ in range(H)]
    stack = [(i,j) for i in range(H) for j in range(W) if S[i][j] == "#"]
    #flag = False
    ans = 0
    for i,j in stack:
        ans += solve(H,W,S,[(i,j)])
    """
    for p,q in stack:
        visited = [[False for _ in range(W)] for _ in range(H)]
        visited[p][q] = True
        substack = [(p,q)]
        for i,j in substack:
            for a,b in [(i-1,j), (i+1, j), (i, j-1), (i, j+1)]:
                if 0 <= a <= H-1 and 0 <= b <= W-1:
                    if S[i][j] == "#" and S[a][b] == ".":
                        ans += 1
                        new_stack.append((a,b))
                    elif S[i][j] == "." and S[a][b] == "#":
                        new_stack.append((a,b))
                    else:
                        continue
    """

    """
    if stack:
        flag = True
    while flag:
        flag = False
        new_stack = []
        #print("ssssss",stack)
        for i,j in stack:
            #print("--", stack)
            for a,b in [(i-1,j), (i+1, j), (i, j-1), (i, j+1)]:
                if 0 <= a <= H-1 and 0 <= b <= W-1:
                    if S[i][j] == "#" and S[a][b] == ".":
                        ans += 1
                        new_stack.append((a,b))
                    elif S[i][j] == "." and S[a][b] == "#":
                        new_stack.append((a,b))
                    else:
                        continue
            
        #print("nnn", new_stack)
        stack = new_stack
        if len(new_stack) != 0:
            #print("333333333333")
            stack = new_stack
            flag = True
    """

    print(ans)

def solve(H,W,S,stack):
    ret = 0
    flag = True
    checked = [[False for _ in range(W)] for _ in range(H)]
    while flag:
        flag = False
        new_stack = []
        #print("ssssss",stack)
        for i,j in stack:
            #print("--", stack)
            for a,b in [(i-1,j), (i+1, j), (i, j-1), (i, j+1)]:

                #else:
                    if 0 <= a <= H-1 and 0 <= b <= W-1:
                        if checked[a][b] == True:
                            continue
                        if S[i][j] == "#" and S[a][b] == ".":
                            ret += 1
                            new_stack.append((a,b))
                            checked[a][b] = True
                        elif S[i][j] == "." and S[a][b] == "#":
                            new_stack.append((a,b))
                            checked[a][b] = True
                        else:
                            continue
            
        #print("nnn", new_stack)
        #stack = new_stack
        if len(new_stack) != 0:
            #print("333333333333")
            stack = new_stack
            flag = True
        else:
            return ret

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

def main():
    H, W = map(int, input().split())
    s = [input().strip() for i in range(H)]

    starts = []
    for i in range(H):
        for j in range(W):
            if s[i][j] == "#":
                starts.append((j, i))
    ans = 0
    for sx, sy in starts:
        q = deque()
        q.append((sx, sy))
        check = [[False] * W for i in range(H)]
        tmp = 0
        while len(q) > 0:
            x, y = q.popleft()
            now = s[y][x]
            if s[y][x] == ".":
                tmp += 1
            for nx, ny in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
                if 0 <= nx and nx < W and 0 <= ny and ny < H:
                    if s[ny][nx] != now and not check[ny][nx]:
                        q.append((nx, ny))
                        check[ny][nx] = True
        ans += tmp
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

def main():
    h, w = map(int, input().split())
    s = [list(input()) for i in range(h)]

    white, black = [], []
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                black.append([i, j])
            else:
                white.append([i, j])

    ans = 0
    for bx, by in black:
        for wx, wy in white:

            queue = [[bx, by]]
            visited = [[False for i in range(w + 1)] for j in range(h+1)]
            while len(queue) != 0:
                p = queue.pop(0)
                visited[p[0]][p[1]] = True
                if p[0] == wx and p[1] == wy:
                    ans += 1
                    break
                for x, y in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                    nx = p[0] + x
                    ny = p[1] + y
                    if nx < 0 or ny < 0 or nx >= h or ny >= w or visited[nx][ny] == True:
                        continue
                    #print(nx, ny, s)
                    if (((nx+ny) % 2) == ((bx+by) % 2) and s[nx][ny] == ".") or (((nx+ny) % 2) != ((bx+by) % 2) and s[nx][ny] == "#"):
                        continue
                    queue.append([nx, ny])

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    h, w = map(int, input().split())
    s = [list(input()) for i in range(h)]

    white, black = [], []
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                black.append([i, j])
            else:
                white.append([i, j])

    ans = 0
    for bx, by in black:
        for wx, wy in white:

            queue = [[bx, by]]
            visited = [[False for i in range(w + 1)] for j in range(h+1)]
            while len(queue) != 0:
                p = queue.pop(0)
                visited[p[0]][p[1]] = True
                if p[0] == wx and p[1] == wy:
                    ans += 1
                    break
                for x, y in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                    nx = p[0] + x
                    ny = p[1] + y
                    if nx < 0 or ny < 0 or nx >= h or ny >= w or visited[nx][ny] == True:
                        continue
                    #print(nx, ny, s)
                    if (((nx+ny) % 2) == ((bx+by) % 2) and s[nx][ny] == ".") or (((nx+ny) % 2) != ((bx+by) % 2) and s[nx][ny] == "#"):
                        continue
                    queue.append([nx, ny])

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#エイシングプログラミングコンテスト2019 C

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


dx,dy = [1,0,-1,0],[0,1,0,-1]
h,w = LI()
s = [input() for _ in range(h)]
que = deque()
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            que = deque()
            que.append((i,j))
            check = [[True]*w for _ in range(h)]
            while que:
                y,x = que.popleft()
                for k in range(4):
                    nx,ny = x + dx[k], y + dy[k]
                    if 0 <= nx < w and 0 <= ny < h and check[ny][nx]:
                        if s[ny][nx] != s[y][x]:
                            if s[y][x] == '#':
                                ans += 1
                            que.append((ny,nx))
                            check[ny][nx] = False
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#エイシングプログラミングコンテスト2019 C

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


dx,dy = [1,0,-1,0],[0,1,0,-1]
h,w = LI()
s = [input() for _ in range(h)]
que = deque()
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            que = deque()
            que.append((i,j))
            check = [[True]*w for _ in range(h)]
            while que:
                y,x = que.popleft()
                for k in range(4):
                    nx,ny = x + dx[k], y + dy[k]
                    if s[y][x] == '#':
                        if 0 <= nx < w and 0 <= ny < h and check[ny][nx]:
                            if s[ny][nx] == '.':
                                ans += 1
                                que.append((ny,nx))
                            check[ny][nx] = False
                    else:
                        if 0 <= nx < w and 0 <= ny < h and check[ny][nx]:
                            if s[ny][nx] == '#':
                                que.append((ny,nx))
                            check[ny][nx] = False
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#エイシングプログラミングコンテスト2019 C

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


dx,dy = [1,0,-1,0],[0,1,0,-1]
h,w = LI()
s = [input() for _ in range(h)]
que = deque()
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            que.append((i,j))
while que:
    que2 = deque()
    y,x = que.popleft()
    que2.append((y,x))
    check = [[True]*w for _ in range(h)]
    while que2:
        y,x = que2.popleft()
        for i in range(4):
            nx,ny = x + dx[i], y + dy[i]
            if s[y][x] == '#':
                if 0 <= nx < w and 0 <= ny < h and check[ny][nx]:
                    if s[ny][nx] == '.':
                        ans += 1
                        que2.append((ny,nx))
                    check[ny][nx] = False
            else:
                if 0 <= nx < w and 0 <= ny < h and check[ny][nx]:
                    if s[ny][nx] == '#':
                        que2.append((ny,nx))
                    check[ny][nx] = False
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

ans = set()


def f(i, j):
    seen[i][j] = 1
    if S[i][j] == '.':
        ans.add((s, (i, j)))
    if i != 0:
        if seen[i-1][j] == 0 and S[i-1][j] != S[i][j]:
            f(i-1, j)
    if i != H-1:
        if seen[i+1][j] == 0 and S[i+1][j] != S[i][j]:
            f(i+1, j)
    if j != 0:
        if seen[i][j-1] == 0 and S[i][j-1] != S[i][j]:
            f(i, j-1)
    if j != W-1:
        if seen[i][j+1] == 0 and S[i][j+1] != S[i][j]:
            f(i, j+1)


for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            seen = [[0] * W for i in range(H)]
            s = (i, j)
            f(i, j)

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
T = [[] for i in range(H)]
d = []
for i in range(H):
    T[i] = list(input())
    for j in range(W):
        if T[i][j] == '#':
            d.append((i, j))

num = 0
for p, q in d:
    que = [(p, q, 0)]
    R = {}
    R[(p, q, 0)] = 1
    while que:
        x, y, k = que.pop(0)
        if k == 0:
            for dx, dy in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
                nx, ny = x + dx, y + dy
                if (nx, ny) in R:
                    continue
                if 0 <= nx < H and 0 <= ny < W and T[nx][ny] == '.':
                    R[(nx, ny)] = 1
                    que.append((nx, ny, 1))
                    num += 1

        else:
            for dx, dy in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
                nx, ny = x + dx, y + dy
                if (nx, ny) in R:
                    continue
                if 0 <= nx < H and 0 <= ny < W and T[nx][ny] == '#':
                    R[(nx, ny)] = 1
                    que.append((nx, ny, 0))
                    i = 0

print(num)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

class UnionFind():
    def __init__(self, N):
        self.par = [i for i in range(N)]
        self.size = [1] * N
        self.N = N

    # xのrootを返す
    def root(self, x):
        if self.par[x] == x:
            return x
        else: 
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    # x, yが同じrootの場合true
    def same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry

    # x,yのrootが違った場合、併合
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if self.size[rx] < self.size[ry]:
            self.par[rx] = ry
            self.size[ry] += self.size[rx]
        else:
            self.par[ry] = rx
            self.size[rx] += self.size[ry]
            
uf = UnionFind(h*w)

for j in range(h):
    for i in range(w):
        if i != w-1 and a[j][i+1] != a[j][i]:
            uf.unite(w*j+i,w*j+i+1)
        if j != h-1 and a[j+1][i] != a[j][i]:
            uf.unite(w*j+i,w*(j+1)+i)

for v in range(h*w):
    uf.root(v)

l_idx = sorted(list(set(uf.par)))

wc = [0]*len(l_idx)
bc = [0]*len(l_idx)
for j in range(h):
    for i in range(w):
        idx = l_idx.index(uf.par[w*j+i])
        if a[j][i] == ".":
            wc[idx] += 1
        else:
            bc[idx] += 1

res = 0
for i in range(len(l_idx)):
    res += wc[i] * bc[i]
print(res)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Mar  6 16:29:39 2019

@author: Yamazaki Kenichi
"""

H,W = map(int,input().split())
A = [input() for i in range(H)]
T = [[[-1,0,0] for j in range(W)] for i in range(H)]

def g(x,i,j):
    if x == '.':
        return 1 if (i+j)%2 == 0 else 2
    else:
        return 4 if (i+j)%2 == 0 else 3
def p(u):
    return T[u[0]][u[1]][0]
def findset(u):
    if p(u) == -1:
        return u
    else:
        T[u[0]][u[1]][0] = findset(p(u))
        return T[u[0]][u[1]][0]

def unite(u,v):
    if findset(u) == findset(v):
        return
#    if T[findset(u)[0]][findset(u)[1]][1]+T[findset(u)[0]][findset(u)[1]][0
#         ] >= T[findset(v)[0]][findset(v)[1]][0]+T[findset(v)[0]][findset(v)[1]][1]:
    T[findset(u)[0]][findset(u)[1]][1] += T[findset(v)[0]][findset(v)[1]][1]
    T[findset(u)[0]][findset(u)[1]][2] += T[findset(v)[0]][findset(v)[1]][2]
    T[findset(v)[0]][findset(v)[1]][0] = findset(u)
def unite_check(i1,j1,i2,j2):
    if g(A[i1][j1],i1,j1)%2 == 0 and g(A[i2][j2],i2,j2)%2 == 0:
        unite([i1,j1],[i2,j2])
#        print('unite',i1,j1,i2,j2)
    elif g(A[i1][j1],i1,j1)%2 == 1 and g(A[i2][j2],i2,j2)%2 == 1:
        unite([i1,j1],[i2,j2])
#        print('unite',i1,j1,i2,j2)
#    else:
#        print('not unite',i1,j1,i2,j2)

for i in range(H):
    for j in range(W):
        if g(A[i][j],i,j) <= 2:
            T[i][j][1] += 1
        else:
            T[i][j][2] += 1
        if i !=0:
            unite_check(i,j,i-1,j)
        if j !=0:
            unite_check(i,j,i,j-1)
ans = 0
for i in range(H):
    for j in range(W):
        if T[i][j][0] == -1:
            ans += T[i][j][1]*T[i][j][2]
print(ans)