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 Counter


class UnionFind:
    def __init__(self, n):
        # total number of nodes.
        self.n = n
        # node id -> root node id
        self._root_table = list(range(n))
        # root node id -> group size
        self._size_table = [1] * n

    def find(self, x):
        """Returns x's root node id."""
        r = self._root_table[x]
        if r != x:
            # Update the cache on query.
            r = self._root_table[x] = self.find(r)
        return r

    def union(self, x, y):
        """Merges two groups."""
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        # Ensure that x is the larger (or equal) group.
        if self._size_table[x] < self._size_table[y]:
            x, y = y, x

        self._size_table[x] += self._size_table[y]
        self._root_table[y] = x

    def size(self, x):
        return self._size_table[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._root_table) if x == i]

    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, map(int, input().split()))
grid = []
for i in range(H):
    grid.append(input())
uf = UnionFind(H * W)
for i in range(H):
    for j in range(W):
        nid = i * W + j
        c = grid[i][j]
        if i > 0 and grid[i - 1][j] != c:
            uf.union(nid, (i - 1) * W + j)
        if i < H - 1 and grid[i + 1][j] != c:
            uf.union(nid, (i + 1) * W + j)
        if j > 0 and grid[i][j - 1] != c:
            uf.union(nid, i * W + (j - 1))
        if j < W - 1 and grid[i][j + 1] != c:
            uf.union(nid, i * W + (j + 1))

whites = Counter()
for i in range(H):
    for j in range(W):
        if grid[i][j] == ".":
            whites[uf.find(i * W + j)] += 1
ans = 0
for i in range(H):
    for j in range(W):
        if grid[i][j] == "#":
            ps = whites[uf.find(i * W + j)]
            ans += ps

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(a, b):
    global dist
    q = deque()
    q.append([a, b])
    bl, wh = 0, 0
    dist[a][b] = 0
    while q:
        p = q.popleft()
        x, y = p[0], p[1]
        if s[x][y] == "#":
            bl += 1
            for u in v:
                xx, yy = x + u[0], y + u[1]
                if s[xx][yy] == "." and dist[xx][yy] == -1:
                    dist[xx][yy] = dist[x][y] + 1
                    q.append([xx, yy])
        else:
            wh += 1
            for u in v:
                xx, yy = x + u[0], y + u[1]
                if s[xx][yy] == "#" and dist[xx][yy] == -1:
                    dist[xx][yy] = dist[x][y] + 1
                    q.append([xx, yy])
    return bl * wh

h, w = map(int, input().split())
s = [["$"] + list(input()) + ["$"] for _ in range(h)]
t = ["$"] * (w + 2)
s.insert(0, t)
s.append(t)
dist = [[-1] * (w + 2) for _ in range(h + 2)]
v = [[1, 0], [-1, 0], [0, 1], [0, -1]]
ans = 0
for i in range(1, h + 1):
    for j in range(1, w + 1):
        if dist[i][j] == -1:
            ans += bfs(i, j)
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        '木の初期化をする'
        self.p = [-1] * n
        self.rank = [1]*n
        self.b = [0]*n
        self.w = [0]*n
        self.parent = set(range(n))

    def find(self, x):
        'x の親を返す'
        if self.p[x] == -1:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def unite(self, x, y):
        'rankの低い親を高い方のの親にする'
        if not self.same(x,y):
            x = self.find(x)
            y = self.find(y)
            if self.rank[x] > self.rank[y]:
                x,y = y,x
            elif self.rank[x] == self.rank[y]:
                self.rank[y] += 1
            self.b[y] += self.b[x]
            self.w[y] += self.w[x]
            self.p[x] = y
            if x in self.parent:
                self.parent.remove(x)
            return True
        else:
            return False

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

h,w = map(int,input().split())
uf = UnionFind(h*w)
S = []
for i in range(h):
    S.append(input())
    for j,s in enumerate(S[i]):
        if s == '#':
            uf.b[i*w+j] += 1
        else:
            uf.w[i*w+j] += 1

for i in range(h):
    for j in range(w):
        for di,dj in [[1,0],[0,1]]:
            ni = i+di
            nj = j+dj
            if ni < h and nj < w and S[i][j] != S[ni][nj]:
                uf.unite(i*w+j,ni*w+nj)
ans = 0
for p in uf.parent:
    ans += uf.b[p] * uf.w[p]
print(ans)

Submission status: Accepted

Solution code:
dy = (-1,0,1,0)
dx = (0,1,0,-1)

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

ans = 0
dist = [[-1] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if dist[i][j] < 0:
            odd = 0
            even = 1
            dist[i][j] = 0
            stack = [(i,j)]
            while stack:
                a,b = stack.pop()
                if grid[a][b] == '#':
                    for k in range(4):
                        y = a + dy[k]
                        x = b + dx[k]
                        if y < 0 or y >= h:
                            continue
                        if x < 0 or x >= w:
                            continue
                        if grid[y][x] == '.' and dist[y][x] < 0:
                            if dist[a][b] == 0:
                                dist[y][x] = 1
                                odd += 1
                            else:
                                dist[y][x] = 0
                                even += 1
                            stack.append((y,x))
                else:
                    for k in range(4):
                        y = a + dy[k]
                        x = b + dx[k]
                        if y < 0 or y >= h:
                            continue
                        if x < 0 or x >= w:
                            continue
                        if grid[y][x] == '#' and dist[y][x] < 0:
                            if dist[a][b] == 0:
                                dist[y][x] = 1
                                odd += 1
                            else:
                                dist[y][x] = 0
                                even += 1
                            stack.append((y,x))    
            ans += even * odd
print(ans)

Submission status: Accepted

Solution code:
h,w=[int(j) for j in input().split()]
s=[input()for i in range(h)]
par=[-1 for i in range(h*w)]
def root(a):
    if par[a]<0:
        return a
    else:
        return root(par[a])

def size(a):
    return -par[root(a)]

def connect(a,b):
    a=root(a)
    b=root(b)
    if a==b:
        return False
    if size(a)<size(b):
        a,b=b,a
    par[a]+=par[b]
    par[b]=a
    return True

for i in range(h):
    for j in range(w):
        for x,y in [(1,0),(-1,0),(0,1),(0,-1)]:
            p,q=i+x,j+y
            if 0<=p<h and 0<=q<w:
                if s[p][q]!=s[i][j]:
                    if root(w*p+q)!=root(w*i+j):
                        connect(w*p+q,w*i+j)

from collections import Counter
c=Counter()
for i in range(h):
    for j in range(w):
        p=i*w+j
        q=root(p)
        if c[q]==0:
            c[q]=[0,0]
        if s[i][j]=="#":
            c[q][0]+=1
        else:
            c[q][1]+=1
ans=0
for i in c:
    ans+=c[i][0]*c[i][1]
print(ans)

Submission status: Accepted

Solution code:
h,w=[int(j) for j in input().split()]
s=[list(input())for i in range(h)]
par=[-1 for i in range(h*w)]    #par<0なら自身が親で要素の個数、>0なら子で親の位置示す
def root(a):
    if par[a]<0:
        return a
    else:
        return root(par[a])

def size(a):
    return -par[root(a)]

def connect(a,b):
    a=root(a)
    b=root(b)
    if a==b:
        return False
    if size(a)<size(b):
        a,b=b,a
    par[a]+=par[b]
    par[b]=a
    return True

for i in range(h):
    for j in range(w):
        for x,y in [(1,0),(-1,0),(0,1),(0,-1)]:
            p,q=i+x,j+y
            if 0<=p<h and 0<=q<w:
                if s[p][q]!=s[i][j]:
                    if root(w*p+q)!=root(w*i+j):
                        connect(w*p+q,w*i+j)

from collections import Counter
c=Counter()
for i in range(h):
    for j in range(w):
        p=i*w+j
        q=root(p)
        if c[q]==0:
            c[q]=[0,0]
        if s[i][j]=="#":
            c[q][0]+=1
        else:
            c[q][1]+=1
ans=0
for i in c:
    ans+=c[i][0]*c[i][1]
print(ans)

Submission status: Accepted

Solution code:
h,w=[int(j) for j in input().split()]
s=[input()for i in range(h)]
par=[-1 for i in range(h*w)]    #par<0なら自身が親で要素の個数、>0なら子で親の位置示す
def root(a):
    if par[a]<0:
        return a
    else:
        return root(par[a])

def size(a):
    return -par[root(a)]

def connect(a,b):
    a=root(a)
    b=root(b)
    if a==b:
        return False
    if size(a)<size(b):
        a,b=b,a
    par[a]+=par[b]
    par[b]=a
    return True

for i in range(h):
    for j in range(w):
        for x,y in [(1,0),(-1,0),(0,1),(0,-1)]:
            p,q=i+x,j+y
            if 0<=p<h and 0<=q<w:
                if s[p][q]!=s[i][j]:
                    if root(w*p+q)!=root(w*i+j):
                        connect(w*p+q,w*i+j)

from collections import Counter
c=Counter()
for i in range(h):
    for j in range(w):
        p=i*w+j
        q=root(p)
        if c[q]==0:
            c[q]=[0,0]
        if s[i][j]=="#":
            c[q][0]+=1
        else:
            c[q][1]+=1
ans=0
for i in c:
    ans+=c[i][0]*c[i][1]
print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
s=[]
for _ in range(h):
	s.append(input())
num=[[-1]*w for _ in range(h)]
stack=[]
def dfs():
	while stack:
		r=stack.pop()
		for x in ((1,0),(-1,0),(0,1),(0,-1)):
			a,b,c,d=r[0],r[1],x[0],x[1]
			if 0<=a+c<h and 0<=b+d<w:
				if s[a+c][b+d]!=s[a][b] and num[a+c][b+d]==-1:
					num[a+c][b+d]=num[a][b]
					stack.append((a+c,b+d))
color=0
for i in range(h):
	for j in range(w):
		if num[i][j]==-1:
			stack.append((i,j))
			num[i][j]=color
			dfs()
			color+=1
color_num=[[0,0]for _ in range(color)]
for i in range(h):
	for j in range(w):
		if s[i][j]==".":
			color_num[num[i][j]][0]+=1
		else:
			color_num[num[i][j]][1]+=1
ans=0
for x in color_num:
	ans+=x[0]*x[1]
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

h,w = map(int, input().split())
s = ["0" * (w+2)]  + ["0"+input()+"0" for i in range(h)] + ["0" * (w+2)] 
not_visited = [[0] * (w+2)] + [[0] + [1] * w + [0] for i in range(h)] + [[0] * (w+2)]
ans = 0
for i in range(1,h+1):
  for j in range(1,w+1):
    if s[i][j] == ".":
      continue
    black, white = 1,0
    queue = deque([(i,j,1)])
    not_visited[i][j] = 0
    while queue:
      H,W,color = queue.popleft()
      if not_visited[H-1][W]:
        if color and s[H-1][W] == ".":
          not_visited[H-1][W] = 0
          white += 1
          queue.append((H-1,W,0))
        elif color == 0 and s[H-1][W] == "#":
          not_visited[H-1][W] = 0
          black += 1
          queue.append((H-1,W,1))
      if not_visited[H+1][W]:
        if color and s[H+1][W] == ".":
          not_visited[H+1][W] = 0
          white += 1
          queue.append((H+1,W,0))
        elif color == 0 and s[H+1][W] == "#":
          not_visited[H+1][W] = 0
          black += 1
          queue.append((H+1,W,1))
      if not_visited[H][W-1]:
        if color and s[H][W-1] == ".":
          not_visited[H][W-1] = 0
          white += 1
          queue.append((H,W-1,0))
        elif color == 0 and s[H][W-1] == "#":
          not_visited[H][W-1] = 0
          black += 1
          queue.append((H,W-1,1))
      if not_visited[H][W+1]:
        if color and s[H][W+1] == ".":
          not_visited[H][W+1] = 0
          white += 1
          queue.append((H,W+1,0))
        elif color == 0 and s[H][W+1] == "#":
          not_visited[H][W+1] = 0
          black += 1
          queue.append((H,W+1,1))
    ans += black * white
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
h,w=map(int,input().split())
s=[list(input()) for _ in range(h)]
visited=[[False]*w for _ in range(h)]

def dfs(y,x):
    visited[y][x]=True
    blk,wht=0,0
    for dy,dx in ((-1,0),(0,-1),(1,0),(0,1)):
      ny,nx=y+dy,x+dx
      if (not (0<=ny<h)) or (not (0<=nx<w)) or visited[ny][nx]: 
        continue
      if s[y][x]!=s[ny][nx]:
        nb,nw=dfs(ny,nx)
        blk+=nb
        wht+=nw
    if s[y][x]=="#":
      blk+= 1
    else:
      wht+= 1
    return blk,wht

ans=0
for i in range(h):
  for j in range(w):
    #到達できる限り進み、残ったやつを順にdfs
    if not visited[i][j]:
      blk,wht=dfs(i,j)
      ans+=blk*wht
print(ans)

Submission status: Accepted

Solution code:
import queue

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

q = queue.Queue()

check = [-1]*(h*w)

vx = [0,1,0,-1]
vy = [1,0,-1,0]

for i in range(h*w):
    y = i//w
    x = i%w
    if si[y][x] == '#':
        if check[i] != -1:
            continue
        q.put([i,'#'])
        check[i] = i
        
        while not q.empty():
            num, clr = q.get()
            y = num//w
            x = num%w
            
            for j in range(4):
                ny = y + vy[j]
                nx = x + vx[j]
                if ny >= 0 and ny < h and nx >= 0 and nx < w:
                    new_num = ny*w+nx
                    if check[new_num] != -1:
                        continue
                    #print(new_num)
                    if clr == '#':
                        if si[ny][nx] == '.':
                            q.put([new_num,'.'])
                            check[new_num] = check[num]
                    else:
                        if si[ny][nx] == '#':
                            q.put([new_num,'#'])
                            check[new_num] = check[num]
    
#print(check)

ans = 0

li = [0]*(h*w+1)

for i in range(h):
    for j in range(w):
        if si[i][j] == '.':
            li[check[i*w+j]] += 1

#print(li)

for i in range(h):
    for j in range(w):
        if si[i][j] == '#':
            ans += li[check[i*w+j]]
            
print(ans)

Submission status: Accepted

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

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1 for _ in range(n+1)]
 
    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
 
    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
 
    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
ki = UnionFind(h*w)

vx = [0,1,0,-1]
vy = [1,0,-1,0]

for i in range(h):
    for j in range(w):
        if si[i][j] == '#':
            for k in range(4):
                ny = i + vy[k]
                nx = j + vx[k]
                if ny >= 0 and ny < h and nx >= 0 and nx < w:
                    if si[ny][nx] == '.':
                        if ki.same_check(i*w+j,ny*w+nx) == True:
                            continue
                        ki.union(i*w+j,ny*w+nx)
ans = 0

li = [0]*(h*w+1)

for i in range(h):
    for j in range(w):
        if si[i][j] == '.':
            li[ki.find(i*w+j)] += 1

for i in range(h):
    for j in range(w):
        if si[i][j] == '#':
            ans += li[ki.find(i*w+j)]
            
print(ans)

Submission status: Accepted

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

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1 for _ in range(n+1)]
 
    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
 
    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
 
    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
ki = UnionFind(h*w)

vx = [0,1,0,-1]
vy = [1,0,-1,0]

for i in range(h):
    for j in range(w):
        if si[i][j] == '#':
            for k in range(4):
                ny = i + vy[k]
                nx = j + vx[k]
                if ny >= 0 and ny < h and nx >= 0 and nx < w:
                    if si[ny][nx] == '.':
                        #if ki.same_check(i*w+j,ny*w+nx) == True:
                        #    continue
                        ki.union(i*w+j,ny*w+nx)
ans = 0

li = [0]*(h*w+1)

for i in range(h):
    for j in range(w):
        if si[i][j] == '.':
            li[ki.find(i*w+j)] += 1

for i in range(h):
    for j in range(w):
        if si[i][j] == '#':
            ans += li[ki.find(i*w+j)]
            
print(ans)

Submission status: Accepted

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

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1 for _ in range(n+1)]
 
    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
 
    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
 
    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
ki = UnionFind(h*w)

vx = [0,1,0,-1]
vy = [1,0,-1,0]

for i in range(h):
    for j in range(w):
        if si[i][j] == '#':
            #print(i,j,i,j)
            for k in range(4):
                ny = i + vy[k]
                nx = j + vx[k]
                if ny >= 0 and ny < h and nx >= 0 and nx < w:
                    #print(ny,nx)
                    if si[ny][nx] == '.':
                        #print(i,j,ny,nx)
                        #print(ki.same_check(i*w+j,ny*w+nx))
                        if ki.same_check(i*w+j,ny*w+nx) == True:
                            continue
                        #print(i,j,k)
                        ki.union(i*w+j,ny*w+nx)
                        #print(ki.par)
ans = 0
#exit()


#print(ki.size)
#print(ki.par)
li = [0]*(h*w+1)
"""
for i in range(h):
    for j in range(w):
        #print(ki.find(i*w+j),1111111)
        ki.find(i*w+j)
"""
#print(ki.par)
for i in range(h):
    for j in range(w):
        if si[i][j] == '.':
            li[ki.find(i*w+j)] += 1
            #print(ki.par[i*w+h],ki.par)
#print(li)
#print(ki.par)

for i in range(h):
    for j in range(w):
        if si[i][j] == '#':
            #print(ki.size[i*w+j])
            #print(i,j)
            #tmp = 
            #print(ki.find(i*w+j))
            ans += li[ki.find(i*w+j)]
            #print(ans,i,j)
            
print(ans)

Submission status: Accepted

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

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1 for _ in range(n+1)]
 
    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
 
    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
 
    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
ki = UnionFind(h*w)

vx = [0,1,0,-1]
vy = [1,0,-1,0]

for i in range(h):
    for j in range(w):
        if si[i][j] == '#':
            #print(i,j,i,j)
            for k in range(4):
                ny = i + vy[k]
                nx = j + vx[k]
                if ny >= 0 and ny < h and nx >= 0 and nx < w:
                    #print(ny,nx)
                    if si[ny][nx] == '.':
                        #print(i,j,ny,nx)
                        #print(ki.same_check(i*w+j,ny*w+nx))
                        if ki.same_check(i*w+j,ny*w+nx) == True:
                            continue
                        #print(i,j,k)
                        ki.union(i*w+j,ny*w+nx)
                        #print(ki.par)
ans = 0
#exit()


#print(ki.size)
#print(ki.par)
li = [0]*(h*w+1)

for i in range(h):
    for j in range(w):
        #print(ki.find(i*w+j),1111111)
        ki.find(i*w+j)
        """
        if si[i][j] == '.':
            li[ki.find(i*w+h)] += 1
            print(ki.find(i*w+h))
        """
#print(ki.par)
for i in range(h):
    for j in range(w):
        if si[i][j] == '.':
            li[ki.par[i*w+j]] += 1
            #print(ki.par[i*w+h],ki.par)
#print(li)
#print(ki.par)

for i in range(h):
    for j in range(w):
        if si[i][j] == '#':
            #print(ki.size[i*w+j])
            #print(i,j)
            #tmp = 
            #print(ki.find(i*w+j))
            ans += li[ki.find(i*w+j)]
            #print(ans,i,j)
            
print(ans)

Submission status: Accepted

Solution code:

from collections import deque
h,w=map(int,input().split())
s=[]
for _ in range(h):
    s.append(input())
ans=0        
sc=[[0 for i in range(w)] for j in range(h)]

for x in range(h):
    for y in range(w):
        if s[x][y]=='.' or sc[x][y]==1:
            continue
        path = deque([[x,y]])
        sc[x][y]=1
        b=1
        wh=0
        while len(path)>0:
            p = path.popleft()
            i,j=p[0],p[1]
            tc = '.' if s[i][j] == '#' else '#'
            point = b if s[i][j] == '#' else wh           
            if i > 0 and s[i-1][j]==tc and sc[i-1][j]==0:
                sc[i-1][j]=1
                path.append([i-1,j])
                if s[i-1][j] == '#':
                    b += 1
                else:
                    wh += 1
                ans += point
            if j > 0 and s[i][j-1]==tc and sc[i][j-1]==0:
                sc[i][j-1]=1
                path.append([i,j-1])
                if s[i][j-1] == '#':
                    b += 1
                else:
                    wh += 1
                ans += point
            if i < h-1 and s[i+1][j]==tc and sc[i+1][j]==0:
                sc[i+1][j]=1
                path.append([i+1,j])
                if s[i+1][j] == '#':
                    b += 1
                else:
                    wh += 1
                ans += point
            if j < w-1 and s[i][j+1]==tc and sc[i][j+1]==0:
                sc[i][j+1]=1
                path.append([i,j+1])
                if s[i][j+1] == '#':
                    b += 1
                else:
                    wh += 1
                ans += point
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


h, w = LI()
grid = SRL(h)
visited = [[0] * w for _ in range(h)]

def solve(sy, sx):
    dq = deque([(sy, sx)])
    visited[sy][sx] = 1
    bi = [0, 1]
    while dq:
        cy, cx = dq.popleft()
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            ny = cy + i
            nx = cx + j
            if 0 <= ny < h and 0 <= nx < w and not visited[ny][nx]:
                if grid[ny][nx] != grid[cy][cx]:
                    bi[int(grid[sy][sx] == grid[ny][nx])] += 1
                    dq += [(ny, nx)]
                    visited[ny][nx] = 1
    return bi[0] * bi[1]

ans = 0
for y in range(h):
    for x in range(w):
        if visited[y][x]:
            continue
        else:
            ans += solve(y, x)


print(ans)

Submission status: Accepted

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

H, W = map(int, input().split())
C = [list(input()) for i in range(H)]
INF = 10 ** 9
go = [[1, 0], [0, 1], [-1, 0], [0, -1]]
que = deque()
ans  = -1

mass = ["#","."]
groups = [[-1 for _ in range(W)] for _ in range(H)]
group_num = -1
for sx in range(W):
    for sy in range(H): # スタート地点のループ
        if C[sy][sx] == "#" and groups[sy][sx] == -1:
            group_num += 1
            que.append((sy,sx))
            groups[sy][sx] = group_num
            while que: #行けるだけいく
                y,x = que.popleft()
                for temp in go:
                    gx,gy = temp
                    nx = x + gx
                    ny = y + gy
                    should = abs(sx - nx) + abs(sy - ny) #奇数→
                    should %= 2
                    if 0<= nx < W and 0<= ny < H and C[ny][nx] == mass[should]:
                        if groups[ny][nx] == -1: # ここの更新にminはいらない(幅優先なので自明に最短距離を進む)
                            groups[ny][nx] = group_num
                            que.append( (ny,nx))
ans = 0
di_sharp = defaultdict(lambda :0)
di_dot = defaultdict(lambda :0)
ma = -1
for sx in range(W):
    for sy in range(H):
        if groups[sy][sx] >= 0:
           color = groups[sy][sx]
           ma = max(ma,color)
           if C[sy][sx] =="#":
               di_sharp[color] += 1
           else:
               di_dot[color] += 1

for i in range(ma + 1):
    ans += di_dot[i]  * di_sharp[i]

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

def dfs(x, y):
  stack = deque()
  stack.append((x, y))
  num_w = 0
  num_b = 0
  while stack:
    cx, cy = stack.popleft()
    cc = S[cy][cx]
    for i, j in zip(dx, dy):
      nx = i + cx
      ny = j + cy
      if (0 <= nx < w and 0 <= ny < h) and not visited[ny][nx] and S[ny][nx] != cc:
        visited[ny][nx] = True
        stack.append((nx, ny))
        if cc == ".":
          num_w += 1
        else:
          num_b += 1
  else:
    return num_w, num_b

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

visited = [[False] * w for _ in range(h)]
  
ans = 0
for i in range(w):
  for j in range(h):
    if not visited[j][i]:
      num_w, num_b = dfs(i, j)
      ans += num_b * num_w
      
print(ans)

Submission status: Accepted

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

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

def dfs(y, x):
    visited[y][x] = True
    blk, wht = 0, 0

    for dy, dx in ((-1, 0), (0, -1), (1, 0), (0, 1)):
        ny, nx = y+dy, x+dx
        if (not (0 <= ny < h)) or (not (0 <= nx < w)) or visited[ny][nx]: continue
        if s[y][x] != s[ny][nx]:
            nb, nw = dfs(ny, nx)
            blk += nb; wht += nw
    
    if s[y][x] == "#": blk += 1
    else: wht += 1

    return blk, wht

ans = 0
for i in range(h):
    for j in range(w):
        if not visited[i][j]:
            blk, wht = dfs(i, j)
            ans += blk * wht

print(ans)