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: Wrong Answer

Solution code:
class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]


    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])


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

        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

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

def kake(i, j):
    return i * W + j

u = UnionFind(H*W)

for i in range(H):
    for j in range(W):
        if H != 1:
            if i != 0:
                if S[i][j] != S[i - 1][j]:
                    u.unite(kake(i, j), kake(i - 1, j))
            if i != H - 1:
                if S[i][j] != S[i + 1][j]:
                    u.unite(kake(i, j), kake(i + 1, j))
        if W != 1:
            if j != 0:
                if S[i][j] != S[i][j - 1]:
                    u.unite(kake(i, j), kake(i, j - 1))
            if j != W - 1:
                if S[i][j] != S[i][j + 1]:
                    u.unite(kake(i, j), kake(i, j + 1))


ans = [[0, 0] for _ in range(H*W)]

for i in range(H):
    for j in range(W):
        if (i+j)%2 == 0:
            ans[u.parent[kake(i, j)]][0] += 1
        else:
            ans[u.parent[kake(i, j)]][1] += 1

pri = 0

for i in range(H):
    for j in range(W):
        pri += ans[kake(i, j)][0] * ans[kake(i, j)][1]

print(pri)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
board = []
black = "#"
white = "."
for _ in range(H):
    board.append(input())

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

deltas = [(1, 0), (-1, 0), (0, 1), (0, -1)]

ans = 0

for start_i in range(H):
    for start_j in range(W):
        if flags[start_i][start_j] is True:
            continue
        else:
            flags[start_i][start_j] = True
            reachable = 1
            n_black = 0
            n_white = 0
            if board[start_i][start_j] == black:
                n_black = 1
            else:
                n_white = 1
            visit = []
            for dx, dy in deltas:
                if \
                start_i + dx >= 0 \
                and start_i + dx < H \
                and start_j + dy >= 0 \
                and start_j + dy < W \
                and flags[start_i + dx][start_j + dy] is False:
                    visit.append((start_i, start_j, start_i + dx, start_j + dy))
            while len(visit) != 0:
                visit_info = visit.pop()
                prev_i = visit_info[0]
                prev_j = visit_info[1]
                next_i = visit_info[2]
                next_j = visit_info[3]
                if \
                board[prev_i][prev_j] != board[next_i][next_j] \
                and flags[next_i][next_j] is False:
                    reachable += 1
                    flags[next_i][next_j] = True
                    if board[next_i][next_j] == black:
                        n_black += 1
                    else:
                        n_white += 1
                    start_i = next_i
                    start_j = next_j
                    for dx, dy in deltas:
                        if \
                        start_i + dx >= 0 \
                        and start_i + dx < H \
                        and start_j + dy >= 0 \
                        and start_j + dy < W \
                        and flags[start_i + dx][start_j + dy] is False:
                            visit.append((start_i, start_j, start_i + dx, start_j + dy))
            if reachable >= 2:
                ans += n_black * n_white

print(ans)

Submission status: Wrong Answer

Solution code:
import collections
H,W=map(int,input().split())
S=[input() for i in [0]*H]
M=[[-1]*W for _ in [0]*H]
k=0
for y in range(H):
    for x in range(W):
        if M[y][x]!=-1:continue #visited
        M[y][x]=k
        Q=collections.deque()
        Q.append((y,x))
        while len(Q)>0:
            i,j=Q.popleft()
            s=S[i][j]
            if i+1<H and M[i+1][j]==-1 and s!=S[i+1][j]:
                M[i+1][j]=k
                Q.append((i+1,j))
            if i-1>0 and M[i-1][j]==-1 and s!=S[i-1][j]:
                M[i-1][j]=k
                Q.append((i-1,j))
            if j+1<W and M[i][j+1]==-1 and s!=S[i][j+1]:
                M[i][j+1]=k
                Q.append((i,j+1))
            if j-1>0 and M[i][j-1]==-1 and s!=S[i][j-1]:
                M[i][j-1]=k
                Q.append((i,j-1))
        k+=1
ds={}
dd={}
for i in range(H):
    for j in range(W):
        m=M[i][j]
        if S[i][j]=='#':ds[m]=ds.get(m,0)+1
        else:dd[m]=dd.get(m,0)+1
r=0
for i in range(k):
    r += ds.get(i,0)*dd.get(i,0)
print(r)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
S = ['' for i in range(H)]
for i in range(H):
  S[i] = input()
R = [[[i, j] for j in range(W)] for i in range(H)]
U = [[1 for j in range(W)] for i in range(H)]
def root(A):
  if R[A[0]][A[1]] == A:
    return A
  else:
    R[A[0]][A[1]] = root(R[A[0]][A[1]])
    return R[A[0]][A[1]]
def union(A, B):
  rA = root(A)
  rB = root(B)
  if rA[0] < rB[0]:
    R[rB[0]][rB[1]] = rA
    U[rA[0]][rA[1]] += U[rB[0]][rB[1]]
  elif rB[0] < rA[0]:
    R[rA[0]][rA[1]] = rB
    U[rB[0]][rB[1]] += U[rA[0]][rA[1]]
  elif rA[1] < rB[1]:
    R[rB[0]][rB[1]] = rA
    U[rA[0]][rA[1]] += U[rB[0]][rB[1]]
  elif rB[1] < rA[1]:
    R[rA[0]][rA[1]] = rB
    U[rB[0]][rB[1]] += U[rA[0]][rA[1]]
for i in range(H):
  for j in range(W):
    if S[i][j] == ".":
      if i > 0 and S[i - 1][j] == "#":
        if j > 0 and S[i - 1][j - 1] == ".":
          union([i, j], [i - 1, j - 1])
        if i > 1 and S[i - 2][j] == ".":
          union([i, j], [i - 2, j])
        if j < W - 1 and S[i - 1][j + 1] == ".":
          union([i, j], [i - 1, j + 1])
      if j > 0 and S[i][j - 1] == "#":
        if i > 0 and S[i - 1][j - 1] == ".":
          union([i, j], [i - 1, j - 1])
        if i > 1 and S[i - 2][j] == ".":
          union([i, j], [i - 2, j])
        if i < H - 1 and S[i + 1][j - 1] == ".":
          union([i, j], [i + 1, j - 1])
for i in range(H):
  for j in range(W):
    root([i, j])
cnt = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == "#":
      if i > 0 and S[i - 1][j] == ".":
        r = R[i - 1][j]
        cnt += U[r[0]][r[1]]
      elif i < H - 1 and S[i + 1][j] == ".":
        r = R[i + 1][j]
        cnt += U[r[0]][r[1]]
      elif j > 0 and S[i][j - 1] == ".":
        r = R[i][j - 1]
        cnt += U[r[0]][r[1]]
      elif j < W - 1 and S[i][j + 1] == ".":
        r = R[i][j + 1]
        cnt += U[r[0]][r[1]]
print(cnt)

Submission status: Wrong Answer

Solution code:
def solve(H, W, Ss):
    d = [[set() for __ in range(W)] for _ in range(H)]
    for _ in range(4):
        for h in range(0, H):
            for w in range(0, W):
                for (hi, wi) in [(h + 1, w), (h - 1, w), (h, w - 1), (h, w + 1)]:
                    if 0 <= hi < H and 0 <= wi < W:
                        if Ss[hi][wi] != Ss[h][w]:
                            d[hi][wi].update(d[h][w])
                            d[hi][wi].add((h, w))
    ans = 0
    for h in range(0, H):
        for w in range(0, W):
            if Ss[h][w] == ".":
                for hi, wi in d[h][w]:
                    ans += 1 if Ss[hi][wi] == "#" else 0
    return ans



if __name__ == "__main__":
    H, W = tuple(map(int, input().split(" ")))
    Ss = list([input() for l in range(H)])
    print(solve(H, W, Ss))

Submission status: Wrong Answer

Solution code:
#import sys

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

s =[input() for _ in range(H)]
bw = set()
bb = set()

for n,i in enumerate(s):
    for m,j in enumerate(i):
        if j == '.':
            continue
        if n!=0 and s[n-1][m]=='.':
            bw.add(((n,m),(n-1,m)))
            if n-1!=0 and s[n-2][m]=='#':
                bb.add(((n,m),(n-2,m)))
            if m!=0 and s[n-1][m-1]=='#':
                bb.add(((n,m),(n-1,m-1)))
            if m!=W-1 and s[n-1][m+1]=='#':
                bb.add(((n,m),(n-1,m+1)))

        if m!=0 and s[n][m-1]=='.':
            bw.add(((n,m),(n,m-1)))
            if n!=0 and s[n-1][m-1]=='#':
                bb.add(((n,m),(n-1,m-1)))
            if m-1!=0 and s[n][m-2]=='#':
                bb.add(((n,m),(n,m-2)))
            if n!=H-1 and s[n+1][m-1]=='#':
                bb.add(((n,m),(n+1,m-1)))

        if n!=H-1 and s[n+1][m]=='.':
            bw.add(((n,m),(n+1,m)))
            if m!=0 and s[n+1][m-1]=='#':
                bb.add(((n,m),(n+1,m-1)))
            if n+1!=H-1 and s[n+2][m]=='#':
                bb.add(((n,m),(n+2,m)))
            if m!=W-1 and s[n+1][m+1]=='#':
                bb.add(((n,m),(n+1,m+1)))

        if m!=W-1 and s[n][m+1]=='.':
            bw.add(((n,m),(n,m+1)))
            if n!=0 and s[n-1][m+1]=='#':
                bb.add(((n,m),(n-1,m+1)))
            if n!=H-1 and s[n+1][m+1]=='#':
                bb.add(((n,m),(n+1,m+1)))
            if m+1!=W-1 and s[n][m+2]=='#':
                bb.add(((n,m),(n,m+2)))
bw2 = set()
for i in bb:
    b0,b1 = i
    for j in bw:
        b2,w0 = j
        if b1 == b2:
            bw2.add((b0,w0))

for l in bw2:
    bw.add(l)
print(len(bw))

Submission status: Wrong Answer

Solution code:
import itertools
h, w = map(int, input().split())
s_list = []
for i in range(h):
  s_list.append(list(input()))
area_list = []
check_list = []

def rec_create_area(point, tmp_area, current_str):
  new_point_list = []
  new_point_list.append([point[0] + 1, point[1]])
  new_point_list.append([point[0], point[1] + 1])
  for new_point in new_point_list:
    if new_point in check_list:
      continue
    if new_point[0] >= h or new_point[1] >= w:
      continue
    new_str = s_list[new_point[0]][new_point[1]]
    if new_str == current_str:
      continue
    if new_str == "#":
      tmp_area[0] += 1
    else:
      tmp_area[1] += 1
    check_list.append(new_point)
    rec_create_area(new_point, tmp_area, new_str)
  
for a, b in itertools.product(range(h), range(w)):
  check_point = [a, b]
  if check_point in check_list:
    continue
  current_str = s_list[0][0]
  if current_str == "#":
    tmp_area = [1, 0]
  else:
    tmp_area = [0, 1]
  rec_create_area(check_point, tmp_area, current_str)
  area_list.append(tmp_area)
  
print(sum([x[0] * x[1] for x in area_list]))

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
s = [list(input()) for i in range(h)]

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

used = set()
usedall = set()
ans = 0

for j in range(h):
    for i in range(w):
        if (i, j) in usedall:
            continue

        used = {(i, j)}
        usedall.add((i, j))
        q = deque([(i, j)])

        while q:
            ii, jj = q.popleft()
            cur = s[jj][ii]
            if cur == "#":
                next = "."
            else:
                next = "#"

            if ii == w - 1 and jj == h - 1:
                break

            for k in range(4):
                if not (0 <= ii + dx[k] < w):
                    continue
                if not (0 <= jj + dy[k] < h):
                    continue

                if s[jj + dy[k]][ii + dx[k]] == cur:
                    continue
                if (ii + dx[k], jj + dy[k]) in used:
                    continue

                used.add((ii + dx[k], jj + dy[k]))
                usedall.add((ii + dx[k], jj + dy[k]))
                q.append((ii + dx[k], jj + dy[k]))

        black = 0
        white = 0
        for m, n in used:
            if s[n][m] == "#":
                black += 1
            else:
                white += 1

        ans += black * white

print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]


    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])


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

        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

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

def kake(i, j):
    return i * W + j

u = UnionFind(H*W)

for i in range(H):
    for j in range(W):
        if i != 0:
            if S[i][j] != S[i-1][j]:
                u.unite(kake(i, j), kake(i-1, j))
        if i != H - 1:
            if S[i][j] != S[i+1][j]:
                u.unite(kake(i, j), kake(i+1, j))
        if j != 0:
            if S[i][j] != S[i][j-1]:
                u.unite(kake(i, j), kake(i, j-1))
        if j != W - 1:
            if S[i][j] != S[i][j+1]:
                u.unite(kake(i, j), kake(i, j+1))


ans = [[0,0] for _ in range(H*W)]

for i in range(H):
    for j in range(W):
        if (i+j)%2 == 0:
            ans[u.parent[kake(i, j)]][0] += 1
        else:
            ans[u.parent[kake(i, j)]][1] += 1

pri = 0

for i in range(H):
    for j in range(W):
        pri += ans[kake(i,j)][0]*ans[kake(i,j)][1]

print(pri)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
s=[input()for _ in range(h)]
a=[[0]*w for _ in range(h)]
ans=0
p=[]
q=[]
for i in range(h):
    for j in range(w):
        if s[i][j]=='.':continue
        for dx,dy in zip([-1,1,0,0],[0,0,-1,1]):
            if i+dy<0 or i+dy>=h or j+dx<0 or j+dx>=w:continue
            if s[i+dy][j+dx]=='.':
                a[i][j]+=1
                ans+=1
        for dx,dy in zip([1,1],[-1,1]):
            if i+dy<0 or i+dy>=h or j+dx<0 or j+dx>=w:continue
            if s[i+dy][j+dx]=='#':
                p.append([[i,j],[i+dy,j+dx]])
        for dx,dy in zip([0,2],[2,0]):
            if i+dy<0 or i+dy>=h or j+dx<0 or j+dx>=w:continue
            if s[i+dy][j+dx]=='#':
                q.append([[i,j],[i+dy,j+dx]])
for t in p:
    u,v=t
    uy,ux=u
    vy,vx=v
    ans+=max(0,a[uy][ux]+a[vy][vx]-4)
for t in q:
    u,v=t
    uy,ux=u
    vy,vx=v
    ans+=max(0,a[uy][ux]+a[vy][vx]-2)
print(ans)

Submission status: Wrong Answer

Solution code:
H, W=map(int, input().split())
S=[list(input()) for _ in range(H)]
S0=[[-1 for _ in range(W)] for _ in range(H)]
# print(S)
# print(S0)

num=1
S0[0][0]=0

for i in range(H):
	for j in range(W):
		if i==0 and j==0:
			continue
		if i>0 and j>0:
			if S[i-1][j]!=S[i][j]:
				S0[i][j]=S0[i-1][j]
			elif S[i][j-1]!=S[i][j]:
				S0[i][j]=S0[i][j-1]

			if S[i-1][j]==S[i][j] and S[i][j-1]==S[i][j]:
				S0[i][j]=num
				num+=1
		if i==0:
			if S[i][j-1]!=S[i][j]:
				S0[i][j]=S0[i][j-1]
			if S[i][j-1]==S[i][j]:
				S0[i][j]=num
				num+=1
		if j==0:
			if S[i-1][j]!=S[i][j]:
				S0[i][j]=S0[i-1][j]
			if S[i-1][j]==S[i][j]:
				S0[i][j]=num
				num+=1
# print(S0)
ans=0
a=[[0, 0] for _ in range(num)]

for i in range(H):
	for j in range(W):
			if S[i][j]=='#':
				a[S0[i][j]][0]+=1
			else:
				a[S0[i][j]][1]+=1
for i in range(num):
	ans+=a[i][0]*a[i][1]
print(ans)

Submission status: Wrong Answer

Solution code:
def make_road(i, j, b, w):
    global H, W
    visited[i][j] = 1
    if S[i][j] == "#":
        b += 1
    else:
        w += 1
    if j < W - 1:
        if S[i][j + 1] != S[i][j] and visited[i][j + 1] == 0:
            b, w = make_road(i, j + 1, b, w)
    if i < H - 1:
        if S[i + 1][j] != S[i][j] and visited[i + 1][j] == 0:
            b, w = make_road(i + 1, j, b, w)
    return b, w


H, W = map(int, input().split())
S = [list(input()) for i in range(H)]
visited = [[0 for i in range(W)] for j in range(H)]
graf = [[0 for i in range(W)] for j in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if visited[i][j] == 0:
            b, w = make_road(i, j, 0, 0)
            ans += b * w
print(ans)

Submission status: Wrong Answer

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

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

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

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

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

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


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

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

ans = 0
for r in range(H):
    for c in range(W):
        if uf.root(r * W + c):
            sz = uf.size(r * W + c)

            wt = sz // 2
            bk = sz - wt
            ans += wt * bk

        elif uf.root((r * W + c) * 2):
            sz = uf.size((r * W + c) * 2)

            bk = sz // 2
            wt = sz - bk
            ans += wt * bk

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

import numpy as np


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

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

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

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


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
fin = sys.stdin.readline
from collections import defaultdict


H, W = [int(elem) for elem in fin().split()]
S = [tuple(elem for elem in fin()[:-1]) for _ in range(H)]
# print(S_list)

# index = lambda i, j: i * H + j
# uf = UnionFind(H * W)
visited = [[False] * W for _ in range(H)]
directions = ((-1, 0), (1, 0), (0, -1), (0, 1))
group_numblack = defaultdict(int)
group_numwhite = defaultdict(int)
# DFS
group = 0
for i in range(H):
    for j in range(W):
        stack = [(i, j)]
        while stack:
            i, j = stack.pop()
            if visited[i][j]:
                continue
            visited[i][j] = True
            if S[i][j] == "#":
                group_numblack[group] += 1
            else:
                group_numwhite[group] += 1
            for di, dj in directions:
                next_i, next_j = i + di, j + dj
                if next_i < 0 or next_i >= H or next_j < 0 or next_j >= W:
                    continue
                elif visited[next_i][next_j]:
                    continue
                elif S[i][j] == S[next_i][next_j]:
                    continue
                else:
                    stack.append((next_i, next_j))
        group += 1


num_pairs = 0
for group in group_numblack.keys():
    num_pairs += group_numblack[group] * group_numwhite[group]
print(num_pairs)

Submission status: Time Limit Exceeded

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

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 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 all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

def main():
    h, w = map(int, input().split())
    tizu = [input().strip() for _ in range(h)]
    
    directions = [[1, 0], [0, 1]]
    UF = UnionFind(h * w)
    for i in range(h):
        for j in range(w):
            for dy, dx in directions:
                ny = i + dy
                nx = j + dx
                if ny == h or nx == w:
                    continue
                if tizu[i][j] != tizu[ny][nx]:
                    UF.union(i * w + j, ny * w + nx)
    
    ans = 0
    for _, lst in UF.all_group_members().items():
        b_cnt = 0
        w_cnt = 0
        for num in lst:
            i = num // w
            j = num % w
            if tizu[i][j] == "#":
                b_cnt += 1
            else:
                w_cnt += 1
        ans += b_cnt * w_cnt
    print(ans)

main()

Submission status: Time Limit Exceeded

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

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 = map(int, input().split())
tizu = [input().strip() for _ in range(h)]

directions = [[1, 0], [0, 1]]
UF = UnionFind(h * w)
for i in range(h):
    for j in range(w):
        for dy, dx in directions:
            ny = i + dy
            nx = j + dx
            if ny == h or nx == w:
                continue
            if tizu[i][j] != tizu[ny][nx]:
                UF.union(i * w + j, ny * w + nx)

ans = 0
for _, lst in UF.all_group_members().items():
    b_cnt = 0
    w_cnt = 0
    for num in lst:
        i = num // w
        j = num % w
        if tizu[i][j] == "#":
            b_cnt += 1
        else:
            w_cnt += 1
    ans += b_cnt * w_cnt
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import deque
from copy import deepcopy

h,w=nii()
s=[list(input()) for i in range(h)]

def BFS(sy,sx,ans):
  temp_s=deepcopy(s)

  que=deque()
  que.append((sy,sx))

  while que:
    y,x=que.popleft()
    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:
        if (temp_s[y][x]=='#' and temp_s[ny][nx]=='.') or \
           (temp_s[y][x]=='.' and temp_s[ny][nx]=='#'):
          que.append((ny,nx))
          if temp_s[ny][nx]=='.':
            ans.add(((sy,sx),(ny,nx)))
            ans.add(((y,x),(ny,nx)))
          if temp_s[y][x]=='#':
            s[y][x]=='D'
    temp_s[y][x]='D'

  return ans

ans=set()
for i in range(h):
  for j in range(w):
    if s[i][j]=='#':
      ans=BFS(i,j,ans)

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import deque
from copy import deepcopy

h,w=nii()
s=[list(input()) for i in range(h)]

def BFS(sy,sx,ans):
  temp_s=deepcopy(s)

  que=deque()
  que.append((sy,sx))

  while que:
    y,x=que.popleft()
    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:
        if (temp_s[y][x]=='#' and temp_s[ny][nx]=='.') or \
           (temp_s[y][x]=='.' and temp_s[ny][nx]=='#'):
          que.append((ny,nx))
          if temp_s[ny][nx]=='.':
            ans.add(((sy,sx),(ny,nx)))
    temp_s[y][x]='D'

  return ans

ans=set()
for i in range(h):
  for j in range(w):
    if s[i][j]=='#':
      ans=BFS(i,j,ans)

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10010010)

def aising19_c():
    h, w = (int(x) for x in input().split())
    grid = [[s for s in str(input())] for _ in range(h)]
    visited = [[False]*w for _ in range(h)]
    ans = 0

    def dfs(x, y):
        nonlocal ans
        visited[x][y] = True
        for dx, dy in ((-1,0),(0,-1),(0,1),(1,0)):
            nx, ny = x+dx, y+dy
            if nx < 0 or h <= nx or ny < 0 or w <= ny: continue
            if grid[nx][ny] == grid[x][y]: continue
            if visited[nx][ny]: continue
            if grid[nx][ny] == '.': ans += 1
            dfs(nx, ny)

    for i in range(h):
        for j in range(w):
            if grid[i][j] == '#':
                dfs(i, j)
                visited = [[False]*w for _ in range(h)]
    print(ans)

if __name__ == '__main__':
    aising19_c()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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))
visited = [[False] * w for _ in range(h)]

ans = 0

for i in range(h):
    for j in range(w):
        if visited[i][j]:
            ans += visited[j][j]
            continue
        if s[i][j] == "#":
            grid = [[0] * w for _ in range(h)]
            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]:
                            q.append((cx + mx, cy + my))
                            if s[cx + mx][cy + my] == ".":
                                grid[cx + mx][cy + my] = 2
            grid = sum(grid, [])
            add = grid.count(2)
            ans += add
            visited[i][j] = add
            continue

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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 = [[0] * w for _ in range(h)]
            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]:
                            q.append((cx + mx, cy + my))
                            if s[cx + mx][cy + my] == ".":
                                grid[cx + mx][cy + my] = 2
            grid = sum(grid, [])
            ans += grid.count(2)
            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 = np.array([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)