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: Accepted

Solution code:
from collections import deque

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


def count(start, S, H, W, tested):
    if tested[start[0]][start[1]]:
        return 0
    q = deque()
    q.append((start[0], start[1], "#"))
    white = 0
    black = 0
    while(len(q)):
        i, j, color = q.popleft()
        if tested[i][j]:
            continue
        tested[i][j] = True
        if color == ".":
            white += 1
            ncolor = "#"
        else:  # color == "#":
            black += 1
            ncolor = "."
        for d in DIRECTIONS:
            ni = i + d[0]
            nj = j + d[1]
            if 0 <= ni and ni < H and 0 <= nj and nj < W and S[ni][nj] == ncolor:
                q.append((ni, nj, ncolor))
    return black * white


def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    tested = [[False] * W for _ in range(H)]
    retval = 0
    for i in range(H):
        for j in range(W):
            if(S[i][j] == "#"):
                retval += count((i, j), S, H, W, tested)
    print(retval)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
H, W = map(int, input().split())
S = [input() for _ in range(H)]

i = 0
color = []
edge = dd(lambda: dd(int))
for h in range(H):
  for w in range(W):
    color.append(S[h][w])
    if w != 0:
      j = i-1
      if S[h][w-1] != S[h][w]:
        edge[i][j] = 1
        edge[j][i] = 1
    if h != 0:
      j = i-W
      if S[h-1][w] != S[h][w]:
        edge[i][j] = 1
        edge[j][i] = 1
    i += 1

visited = [False] * i
ans = 0
for k in range(i):
  if not visited[k]:
    count = { '#': 0, '.': 0 }
    queue = set([k])
    while queue:
      j = queue.pop()
      count[color[j]] += 1
      visited[j] = True
      for dst in edge[j]:
        if not visited[dst]:
          queue.add(dst)
    ans += count['#'] * count['.']
print(ans)

Submission status: Accepted

Solution code:
import sys
fin = sys.stdin.readline
sys.setrecursionlimit(300000)
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)

visited = [[False] * W for _ in range(H)]
directions = ((-1, 0), (1, 0), (0, -1), (0, 1))
group_numblack = defaultdict(int)
group_numwhite = defaultdict(int)

def dfs_visit(i, j, visited, group):
    if visited[i][j]:
        return
    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:
            dfs_visit(next_i, next_j, visited, group)

# DFS
group = 0
for i in range(H):
    for j in range(W):
        dfs_visit(i, j, visited, group)
        # 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
# print(visited)
# print(group_numblack)
# print(group_numwhite)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500*500)

h, w = map(int, input().split())
grid = []
seen = [[False for y in range(w)] for x in range(h)]

for x in range(h):
    grid.append(input())



blackSeen = 0
whiteSeen = 0
def countFrom(a, b, lastColor):
    global blackSeen, whiteSeen
    if not (0 <= a < h and 0 <= b < w):
        return
    if seen[a][b]:
        return
    #print(a, b)
    

    thisColor = (1 if grid[a][b] == "." else -1)

    if grid[a][b] == "#" and lastColor != -1:
        blackSeen += 1
    elif grid[a][b] == "." and lastColor != 1:
        whiteSeen += 1
    else:
        return
    seen[a][b] = True

    countFrom(a+1, b, thisColor)
    countFrom(a-1, b, thisColor)
    countFrom(a, b+1, thisColor)
    countFrom(a, b-1, thisColor)

tot = 0
for x in range(h):
    for y in range(w):
        blackSeen = 0
        whiteSeen = 0
        countFrom(x, y, 0)
        #print(x, y, blackSeen, whiteSeen)
        tot += blackSeen * whiteSeen

print(tot)

Submission status: Accepted

Solution code:

TTYPE = 0
X = 1
Y = 2

def main():
    buf = input()
    buflist = buf.split()
    H = int(buflist[0])
    W = int(buflist[1])
    S = []
    for i in range(H):
        buf = input()
        S.append(buf)
    searched = []
    for i in range(H):
        searched.append([])
        for j in range(W):
            searched[i].append(False)
    group_white = []
    group_black = []
    for i in range(H):
        for j in range(W):
            if searched[i][j]:
                continue
            else:
                search_stack = [[S[i][j], i, j]]
                group_white.append(0)
                group_black.append(0)
                while len(search_stack) > 0:
                    target = search_stack.pop()
                    if searched[target[X]][target[Y]]:
                        continue
                    if target[TTYPE] == '.':
                        group_white[-1] += 1
                    else:
                        group_black[-1] += 1
                    searched[target[X]][target[Y]] = True
                    if target[X] > 0:
                        if not searched[target[X]-1][target[Y]] and ((target[TTYPE] == '.' and S[target[X]-1][target[Y]] == "#") or (target[TTYPE] == '#' and S[target[X]-1][target[Y]] == ".")):
                            search_stack.append([S[target[X]-1][target[Y]], target[X]-1, target[Y]])
                    if target[Y] > 0:
                        if not searched[target[X]][target[Y]-1] and ((target[TTYPE] == '.' and S[target[X]][target[Y]-1] == "#") or (target[TTYPE] == '#' and S[target[X]][target[Y]-1] == ".")):
                            search_stack.append([S[target[X]][target[Y]-1], target[X], target[Y]-1])
                    if target[X] < H-1:
                        if not searched[target[X]+1][target[Y]] and ((target[TTYPE] == '.' and S[target[X]+1][target[Y]] == "#") or (target[TTYPE] == '#' and S[target[X]+1][target[Y]] == ".")):
                            search_stack.append([S[target[X]+1][target[Y]], target[X]+1, target[Y]])
                    if target[Y] < W-1:
                        if not searched[target[X]][target[Y]+1] and ((target[TTYPE] == '.' and S[target[X]][target[Y]+1] == "#") or (target[TTYPE] == '#' and S[target[X]][target[Y]+1] == ".")):
                            search_stack.append([S[target[X]][target[Y]+1], target[X], target[Y]+1])
    total = 0
    for i in range(len(group_black)):
        total += group_black[i] * group_white[i]
    print(total)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

S = [[-1] * W for i in range(H)]

rec = 0
ans = [[0] * (H * W + 5) for i in range(2)]
for i in range(H):
    for j in range(W):
        if T[i][j] == "#" and S[i][j] == -1:
            rec += 1
            S[i][j] = rec
            ans[1][rec] += 1
            pre = "#"
            que = [(i, j, pre)]
            while que:
                x, y, pre = que.pop()
                for dx, dy in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
                    nx, ny = x + dx, y + dy
                    if pre == "#":
                        if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == -1 and T[nx][ny] == ".":
                            S[nx][ny] = rec
                            ans[0][rec] += 1
                            que.append((nx, ny, "."))
                    else:
                        if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == -1 and T[nx][ny] == "#":
                            S[nx][ny] = rec
                            ans[1][rec] += 1
                            que.append((nx, ny, "#"))


num1 = 0
for i in range(H * W + 5):
    num1 += ans[0][i] * ans[1][i]

print(num1)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
s = []
point = [[0 for j in range(0,w+2)] for i in range(0,h+2)]
ans = []
for _ in range(h):
    S = input()
    s.append(S)
for i in range(0,h+2):
    point[i][0] = 1
    point[i][w+1] = 1
for i in range(0,w+2):
    point[0][i] = 1
    point[h+1][i] = 1

def haba(y,x):
    point[y][x] = 1
    q = []
    q.append((y,x,s[y-1][x-1]))
    while len(q) > 0:
        (y,x,ss) = q.pop(0)
        nextPoint = [[y+1,x],[y,x+1],[y-1,x],[y,x-1]]
        for ny,nx in nextPoint:
            if point[ny][nx] != 0:
                continue
            if ss == "#" and s[ny-1][nx-1] == ".":
                ans[-1][0] += 1
                point[ny][nx] = 1
                q.append((ny,nx,s[ny-1][nx-1]))
            if ss == "." and s[ny-1][nx-1] == "#":
                ans[-1][1] += 1
                point[ny][nx] = 1
                q.append((ny,nx,s[ny-1][nx-1]))
for i in range(1,h+1):
    for j in range(1,w+1):
        if point[i][j] == 1:
            continue
        if s[i-1][j-1] == ".":
            ans.append([1,0])
        else:
            ans.append([0,1])
        haba(i,j)
sum = 0
for i,j in ans:
    sum += i*j
print(sum)

Submission status: Accepted

Solution code:
dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
H,W = map(int,input().split())
s = []
for i in range(H):
    s.append(input())

goto = [[False]*W for _ in range(H)]
count = 0
for h in range(H):
    for w in range(W):
        black = 0
        white = 0
        if s[h][w] == '#' and goto[h][w] == False:
            black = 1
            goto[h][w] = True
            stack = [[h,w,'#']]
            while(stack!=[]):
                tarr = stack.pop()
                for dx,dy in dxdy:
                    if tarr[0]+dx >= 0 and tarr[0]+dx < H and tarr[1]+dy >= 0 and tarr[1]+dy < W:
                        if s[tarr[0]+dx][tarr[1]+dy] != tarr[2] and goto[tarr[0]+dx][tarr[1]+dy] == False:
                            stack.append([tarr[0]+dx,tarr[1]+dy,s[tarr[0]+dx][tarr[1]+dy]])
                            goto[tarr[0]+dx][tarr[1]+dy] = True
                            if s[tarr[0]+dx][tarr[1]+dy] == '#':
                                black += 1
                            else:
                                white += 1
        count += black*white
print(count)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

#n = int(input())
import sys

sys.setrecursionlimit(1000000)

h,W = [int(i) for i in input().split()]
#b = [i for i in input().split()]
board = []
for _ in range(h):
    board.append(input())

checked = [[0]*W for i in range(h)]

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

ans = 0

def dfs(x,y,b,w):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
#        print(nx,ny)
#        print(checked)
        if nx < 0 or nx >= h or ny < 0 or ny >= W or checked[nx][ny]==1:
            continue
        if board[x][y] == board[nx][ny]:
            continue
#        print("ok")
        checked[nx][ny]=1
        if board[nx][ny] == '#':
            b+=1
        else:
            w+=1
        b1,w1 = dfs(nx, ny,0,0)
        b+=b1
        w+=w1
#    print(x,y,b,w)
    return b,w

#print(dfs(0,0,0,0))

for i in range(h):
    for j in range(W):
        if checked[i][j] == 1:
            continue
        checked[i][j] = 1
        if board[i][j] == '#':
            b2 = 1; w2=0
        else:
            b2 = 0; w2=1
        b1,w1 = dfs(i,j,b2,w2)
#        print(b1,w1)
        ans += b1*w1

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

II = lambda: int(input())
MI = lambda: map(int, input().split())


def make_cells(h, w):
    cells = set()
    for i in range(h):
        for j in range(w):
            cells.add((i, j))
    return cells

def make_bcells(h, w, m):
    cells = set()
    for i in range(h):
        for j in range(w):
            if m[i][j]:
                cells.add((i, j))
    return cells


def search(sc, bcells_yet, m, H, W):
    valid = lambda cell: cell[0] >= 0 and cell[0] < H and cell[1] >= 0 and cell[1] < W
    color = lambda cell: m[cell[0]][cell[1]]

    ccnt = {0:0, 1:1}
    wcells_searched = set()

    q = set()
    q.add(sc)
    while len(q) > 0:
        c = q.pop()
        dirs = filter(valid, [(c[0] + 1, c[1]), (c[0] - 1, c[1]), (c[0], c[1] + 1), (c[0], c[1] - 1)])
        for nc in dirs:
            if color(nc) != color(c):
                if color(nc) and nc in bcells_yet:
                    bcells_yet.remove(nc)
                    ccnt[1] += 1
                    q.add(nc)
                elif not color(nc) and nc not in wcells_searched:
                    wcells_searched.add(nc)
                    ccnt[0] += 1
                    q.add(nc)
    return ccnt[0] * ccnt[1]


def main():
    H, W = MI()

    m = []
    for h in range(H):
        m.append(tuple(map(lambda c:c == "#", input())))

    bcells = make_bcells(H, W, m)

    ans = 0
    while len(bcells) > 0:
        ans += search(bcells.pop(), bcells, m, H, W)
    return ans


if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

def main():
    h, w = map(int, input().split())
    mp = ["X" * (w + 2)] + ["X" + input() + "X" for _ in range(h)] + ["X" * (w + 2)]
    checked = [[False] * (w + 2) for _ in range(h + 2)]
    vec = ((1, 0), (0, -1), (-1, 0), (0, 1))


    def search(stack):
        x, y = stack.pop()
        if mp[y][x] == "#":
            b_cnt = 1
            w_cnt = 0
            another = "."
        else:
            b_cnt = 0
            w_cnt = 1
            another = "#"
        for dx, dy in vec:
            nx, ny = x + dx, y + dy
            if not checked[ny][nx] and mp[ny][nx] == another:
                checked[ny][nx] = True
                stack.append((nx, ny))
        return w_cnt, b_cnt

    ans = 0
    for y in range(1, h + 1):
        for x in range(1, w + 1):
            if not checked[y][x]:
                checked[y][x] = True
                stack = []
                stack.append((x, y))
                w_cnt = b_cnt = 0
                while stack:
                    w_add, b_add = search(stack)
                    w_cnt += w_add
                    b_cnt += b_add
                ans += w_cnt * b_cnt

    print(ans)

main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000*1000)

H, W = map(int, input().split(" "))
map_info = [input() for i in range(H)]

visit = [[False for j in range(W)] for i in range(H)]
ans = 0


def search(i, j, want_color):
    if i < 0 or i >= H:
        return
    if j < 0 or j >= W:
        return
    if visit[i][j]:
        return
    this_color = map_info[i][j]
    if want_color != this_color:
        return

    global white
    global black

    visit[i][j] = True
    if this_color == '.':
        white += 1
        next_color = '#'
    else:
        black += 1
        next_color = '.'
    search(i, j+1, next_color)
    search(i, j-1, next_color)
    search(i+1, j, next_color)
    search(i-1, j, next_color)


for i in range(H):
    for j in range(W):
        white = 0
        black = 0
        search(i, j, map_info[i][j])
        ans += black * white
print(ans)

Submission status: Accepted

Solution code:
def root(x):
    if parent[x] == x:
        return(x)
    else:
        parent[x] = root(parent[x])
        return(parent[x])


def same(x, y):
    return(root(x) == root(y))


def union(x, y):
    x = root(x)
    y = root(y)
    if(x == y):
        return False

    parent[x] = min(x, y)
    parent[y] = min(x, y)
    return True





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

parent = [i for i in range(H*W)]

neighbor = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for h in range(H):
    for w in range(W):
        for px, py in neighbor:
            tx = w + px
            ty = h + py
            # print(tx, ty, tx < 0 or tx >= w or ty < 0 or ty >= h)
            if tx < 0 or tx >= W or ty < 0 or ty >= H:
                continue
            
            # print({S[h][w], S[ty][tx]})
            if {S[h][w], S[ty][tx]} == {"#", "."}:
                union(h*W+w,ty*W+tx)

ans = {root(r):{"#":0, ".":0} for r in parent}
for i in range(H*W):
    ans[root(i)][S[i//W][i%W]] += 1
# print(parent)
# print(ans)

print(sum(v["#"]*v["."] for v in ans.values()))

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
s = ["X" * (W+2)] + ["X" + input() + "X" for _ in range(H)] + ["X" * (W+2)]
visited = [[-1 for _ in range(W+2)] for _ in range(H+2)]

DH = [1, 0, -1, 0]
DW = [0, 1, 0, -1]

ans = 0
def bfs(start, num):
	global ans
	dot, sharp = 0, 0
	que = deque([start])
	#visited = [[False for _ in [0]*(W+2)] for _ in [0]*(H+2)]
	visited[start[0]][start[1]] = num
	#cur = s[start[0]][start[1]]
	while que:
		label = que.pop()
		h, w = label[0], label[1]
		if s[h][w] == ".":
			dot += 1
		elif s[h][w] == "#":
			sharp += 1
		#if s[start[0]][start[1]] != s[h][w] and W*start[0]+start[1] < W*h+w:
			#ans += 1
		for dh, dw in zip(DH, DW):
			if s[h][w] == ".":
				if s[h+dh][w+dw] == "#" and visited[h+dh][w+dw] == -1:
					que.appendleft([h+dh, w+dw])
					visited[h+dh][w+dw] = num
			elif s[h][w] == "#":
				if s[h+dh][w+dw] == "." and visited[h+dh][w+dw] == -1:
					que.appendleft([h+dh, w+dw])
					visited[h+dh][w+dw] = num
	#del que, visited
	return dot*sharp

k = 0
for i in range(1, H+1):
	for j in range(1, W+1):
		if visited[i][j] == -1:
			ans += bfs([i, j], k)

print(ans)

Submission status: Accepted

Solution code:
#      
import collections, atexit, math, sys, bisect 

sys.setrecursionlimit(1000000)
def getIntList():
    return list(map(int, input().split()))    

try :
    #raise ModuleNotFoundError
    import numpy
    def dprint(*args, **kwargs):
        #print(*args, **kwargs, file=sys.stderr)
        # in python 3.4 **kwargs is invalid???
        print(*args,  file=sys.stderr)
    dprint('debug mode')
except Exception:
    def dprint(*args, **kwargs):
        pass



inId = 0
outId = 0
if inId>0:
    dprint('use input', inId)
    sys.stdin = open('input'+ str(inId) + '.txt', 'r') #标准输出重定向至文件
if outId>0:
    dprint('use output', outId)
    sys.stdout = open('stdout'+ str(outId) + '.txt', 'w') #标准输出重定向至文件
    atexit.register(lambda :sys.stdout.close())     #idle 中不会执行 atexit
    
H, W = getIntList()
#print(N)
zs = []
dprint(H,W)
for i in range(H):
    s = input()
    zs.append(s)
    dprint(s)
zu = [  [(i,j) for j in range(W) ]  for i in range(H) ]
dprint(11111)
def getr(p):
    #dprint('?', p)
    if p == zu[ p[0] ] [p[1] ]:
        return p
    np = getr(zu[ p[0] ] [p[1] ])
    zu[ p[0] ] [ p[1] ] = np
    return np
dprint(11111)
def uuu( p0, p1) :
    p0 = getr(p0)
    p1 = getr(p1)
    #dprint(p0, p1)
    zu[ p0[0] ] [p0[1] ] =  p1
dprint(zu)
dprint(zs)
for i in range(H):
    for j in range(W): 
        if i>0:
            if zs[i-1][j] != zs[i][j]:
                uuu( (i-1,j), (i,j) )
        if j>0:
            if zs[i][j-1] != zs[i][j]:
                uuu( (i,j-1), (i,j) )
         
dprint(11111) 
zr = dict()
dprint(11111)
for i in range(H):
    for j in range(W):
        p = (i,j)
        p = getr(p)
        if p not in zr:
            zr[p] = [0,0]
        if zs[i][j] == '.':
            zr[p][0] +=1
        else:
            zr[p][1] +=1
dprint(zr)            
r = 0
for x in zr:
    r += zr[x][0] * zr[x][1]
    
print(r)

Submission status: Accepted

Solution code:
from collections import defaultdict
def find(A,x):
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a
 
def union(A, x, y):
#    bx, by = sorted([find(A,x), find(A,y)]) # bx, by = find(A,x), find(A,y)だと無限ループ。
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    A[y] = bx
    A[by] = bx

H, W = map( int, input().split())
S = [ input() for _ in range(H)]
A = [ i for i in range(H*W)]
D = defaultdict( lambda: (0,0))
for i in range(H):
    for j in range(W):
        if i > 0 and H != 1:
            if S[i][j] != S[i-1][j]:
                union(A, i*W+j, (i-1)*W + j)
        if i < H-1 and H != 1:
            if S[i][j] != S[i+1][j]:
                union(A, i*W+j, (i+1)*W + j)
        if j > 0 and W != 1:
            if S[i][j] != S[i][j-1]:
                union( A, i*W+j, i*W + j-1)
        if j < W-1 and W != 1:
            if S[i][j] != S[i][j+1]:
                union( A, i*W+j, i*W+j+1)
for i in range(H):
    for j in range(W):
        a, b = D[ find(A,i*W+j)]
        if S[i][j] == "#":
            D[ find(A,i*W+j)] = (a+1,b)
        else:
            D[ find(A,i*W+j)] = (a,b+1)
ans = 0
for d in D:
    a, b = D[d]
    ans += a*b
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

CHECK=[[0]*W for i in range(H)]
ANSLIST=[]

for i in range(H):
    for j in range(W):
        if CHECK[i][j]==1:
            continue
        QUE = deque()
        QUE.append((i,j))
        BC=0
        WC=0

        while QUE:
            x,y=QUE.pop()
            if CHECK[x][y]==1:
                continue

            
            CHECK[x][y]=1
            #print(x,y,QUE,CHECK)

            if S[x][y]=="#":
                BC+=1
            else:
                WC+=1


            for k,l in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
                #print("!",k,l,x,y)
                if k<0 or l<0 or k>=H or l>=W:
                    #print("?",k,l)
                    continue
                if CHECK[k][l]==1:
                    continue

                if S[k][l]!=S[x][y]:
                    QUE.appendleft((k,l))
                    #print(x,y)

        ANSLIST.append((BC,WC))
        #print(i,j,ANSLIST,CHECK)

ANS=0
for a,b in ANSLIST:
    ANS+=a*b

print(ANS)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

move=((1,0),(0,1),(-1,0),(0,-1))

#深さ優先探索
def dfs(used,mat,node,nums):
    y,x=node
    color=mat[y][x]
    if used[y][x]==1 or color=='!':
        return
    
    used[y][x]=1
    nums[color]+=1
    for i,j in move:
        if mat[y+i][x+j]!=color and mat[y+i][x+j] != '!':
            dfs(used,mat,(y+i,x+j),nums)


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

grid=['!'*(W+2)]
used=[[0 for _ in range(W+2)] for _ in range(H+2)]

for i in range(H):
    grid.append('!'+input()+'!')
grid.append('!'*(W+2))

ans=0
for i in range(H+2):
    for j in range(W+2):
        nums={'#':0,'.':0}
        dfs(used,grid,(i,j),nums)
        ans+=nums['#']*nums['.']
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(300000)

H, W = map(int, input().split())
S = [input() for y in range(H)]
visited = [[False] * W for y in range(H)]

def color(y, x):
    if y < 0 or H <= y or x < 0 or W <= x or visited[y][x]:
        return "@"
    else:
        return S[y][x]


def dfs(y, x):
    b = 0
    w = 0
    nxt = "n"
    if color(y, x) == ".":
        w = 1
        nxt = "#"
    elif color(y, x) == "#":
        b = 1
        nxt = "."
    
    visited[y][x] = True
    if color(y - 1, x) == nxt:
        _b, _w = dfs(y - 1, x)
        b += _b
        w += _w
    if color(y + 1, x) == nxt:
        _b, _w = dfs(y + 1, x)
        b += _b
        w += _w
    if color(y, x - 1) == nxt:
        _b, _w = dfs(y, x - 1)
        b += _b
        w += _w
    if color(y, x + 1) == nxt:
        _b, _w = dfs(y, x + 1)
        b += _b
        w += _w

    return (b, w)

    
ans = 0
for y in range(H):
    for x in range(W):
        b, w = dfs(y, x)
        ans += b * w

print(ans)

Submission status: Accepted

Solution code:
# C
from collections import deque

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

S_list = [list(input()) for _ in range(H)]
bw = [0]*(H*W)
visited = [0]*(H*W)

G = dict()

# edge .# or #.
vid = 0
for i in range(H):
    for j in range(W):
        G[vid] = dict()
        if i > 0:
            if S_list[i][j] != S_list[i-1][j]:
                G[vid][vid-W] = 1
        if i < H-1:
            if S_list[i][j] != S_list[i+1][j]:
                G[vid][vid+W] = 1
        if j > 0:
            if S_list[i][j] != S_list[i][j-1]:
                G[vid][vid-1] = 1
        if j < W-1:
            if S_list[i][j] != S_list[i][j+1]:
                G[vid][vid+1] = 1
        if S_list[i][j] == "#":
            bw[vid] = 1
        vid += 1

# connected components
res = 0



for st in range(H*W):
    
    if visited[st] == 1:
        continue
    
    queue = deque()
    queue.append(st)
    visited[st] = 1
    res_temp = 0
    res_temp_black = 0

    while len(queue) > 0:
        s = queue.popleft()
        res_temp += 1
        if bw[s] == 1:
            res_temp_black += 1
        for t in G[s].keys():
            if visited[t] == 0:
                visited[t] = 1
                queue.append(t)
    res += res_temp_black*(res_temp-res_temp_black)

print(res)

Submission status: Accepted

Solution code:
import collections
import itertools
import operator

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

v = []
for i in range(H*W):
    hh = i//W
    ww = i % W
    v.append(S[hh][ww])

class UnionFind:
    def __init__(self, elems=None):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)

        if elems is not None:
            for elem in elems:
                _, _ = self.parent[elem], self.rank[elem]

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

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

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield [x for x, _ in group]

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

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

a = list(tree.grouper())
res = 0
for lis in a:
    br = 0
    wt = 0
    for po in lis:
        if S[po[0]][po[1]] == ".":
            wt += 1
        else:
            br += 1
    res += wt * br

print(res)

Submission status: Accepted

Solution code:
from collections import deque
H,W=map(int,input().split())
S=[input() for i in range(H)]
visit=[[False]*W for i in range(H)]
par=[[None]*W for i in range(H)]
dd={}
X=[-1,0,1,0]
Y=[0,-1,0,1]
for j in range(H):
    for i in range(W):
        if visit[j][i]:
            continue
        if S[j][i]=='.':
            continue
        lH=deque()
        lH.append((j,i,0))#0が黒
        par[j][i]=(i,j)
        num=0
        while lH:
            y,x,t=lH.popleft()
            visit[y][x]=True
            for k in range(4):
                nx=x+X[k]
                ny=y+Y[k]
                if 0<=nx<W and 0<=ny<H:
                    if visit[ny][nx]:
                        continue
                    if t==0 and S[ny][nx]=='.':
                        visit[ny][nx]=True
                        num+=1
                        lH.append((ny,nx,1))
                    elif t==1 and S[ny][nx]=='#':
                        visit[ny][nx] = True
                        par[ny][nx]=(i,j)
                        lH.append((ny,nx,0))
        dd[(i,j)]=num
#print(par)
#print(dd)
ans=0
for j in range(H):
    for i in range(W):
        if S[j][i]=='#':
            x,y=par[j][i]
            ans+=dd[(x,y)]
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
def inpl(): return list(map(int, input().split()))
H, W = inpl()
G = []

class UnionFindTree():
    
    def __init__(self, N):
        self.parent = [-1]*(N+1)
        self.rank = [1]*(N+1)
        self.size = [1]*(N+1)
  
    def find(self, i):
        if self.parent[i] == -1:
            group = i
        else:
            group = self.find(self.parent[i]) 
            self.parent[i] = group
        return group
      
    def unite(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            if self.rank[px] == self.rank[py]: # rank is same
                self.rank[px] += 1
            elif self.rank[px] < self.rank[py]:
                px, py = py, px
                
            self.parent[py] = px
            self.size[px] += self.size[py]
    
    def getsize(self, x):
        return self.size[self.find(x)]


def binarize(h, w):
    return h*W + w

def reverse(g):
    h, w = divmod(g, W)
    return h, w

UFT = UnionFindTree(H*W)

for _ in range(H):
    G.append(input())

for h in range(H-1):
    for w in range(W):
        if G[h][w] != G[h+1][w]:
            UFT.unite(binarize(h, w),
                      binarize(h+1, w))

for h in range(H):
    for w in range(W-1):
        if G[h][w] != G[h][w+1]:
            UFT.unite(binarize(h, w),
                      binarize(h, w+1))

D = defaultdict(lambda: [0, 0])
for i in range(H*W):
    h, w = reverse(i)
    D[UFT.find(i)][G[h][w] == "."] += 1

ans = 0
for k, v in D.items():
    ans += v[0] * v[1]

print(ans)