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: Runtime Error

Solution code:
import numpy as np
h, w = list(map(int, input().split()))
ss = []
for k in range(h):
    s = input()
    ss.append(s)

field = np.zeros([h, w])
for hk in range(h):
    for wk in range(w):
        field[hk,wk] = ss[hk][wk] == '.'

right = np.zeros_like(field)
right[:,:-1] = field[:,:-1] - field[:,1:] != 0

left = np.zeros_like(field)
left[:,1:] = field[:,1:] - field[:,:-1] != 0

down = np.zeros_like(field)
down[:-1,:] = field[:-1,:] - field[1:,:] != 0

up = np.zeros_like(field)
up[1:,:] = field[1:,:] - field[:-1,:] != 0

ans = {}

from itertools import product

for hk1, wk1 in product(range(h), range(w)):
    ans[(hk1, wk1)] = []

for hk1, wk1 in product(range(h), range(w)):
    if right[hk1, wk1]:
        ans[(hk1, wk1)].append((hk1, wk1 + 1))
    if left[hk1, wk1]:
        ans[(hk1, wk1)].append((hk1, wk1 - 1))
    if up[hk1, wk1]:
        ans[(hk1, wk1)].append((hk1 - 1, wk1))
    if down[hk1, wk1]:
        ans[(hk1, wk1)].append((hk1 + 1, wk1))


def check(start, kidoku):
    nex = ans[start]
    plus = 0
    tansaku = []
    for n in nex:
        if n in kidoku:
            pass
        else:
            kidoku.append(n)
            plus += 1
            check(n, kidoku)
    return kidoku

s = 0
for hk1, wk1 in product(range(h), range(w)):
    if field[hk1,wk1] == 0:
        lis = check((hk1,wk1), [])
        for l in lis:
            if field[l[0],l[1]] == 1:
                s += 1
#         print(hk1, wk1, lis)
#         s += len(lis) - 1

print(s)

Submission status: Runtime Error

Solution code:
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: Runtime Error

Solution code:
H,W=map(int,input().split())
S=[input() for i in [0]*H]
m=[[-1]*W for _ in [0]*H]
def dfs(i,j,k):
    m[i][j]=k
    if i+1<H and m[i+1][j]==-1 and S[i][j]!=S[i+1][j]:
        dfs(i+1,j,k)
    if i-1>0 and m[i-1][j]==-1 and S[i][j]!=S[i-1][j]:
        dfs(i-1,j,k)
    if j+1<W and m[i][j+1]==-1 and S[i][j]!=S[i][j+1]:
        dfs(i,j+1,k)
    if j-1>0 and m[i][j-1]==-1 and S[i][j]!=S[i][j-1]:
        dfs(i,j-1,k)
k=0
for i in range(H):
    for j in range(W):
        if m[i][j]==-1:
            dfs(i,j,k)
            k += 1
d={}
di=set()
for i in range(H):
    for j in range(W):
        mij=m[i][j]
        sij=0 if S[i][j]=='.' else 1
        if (mij,sij) in d.keys():d[(mij,sij)]+=1
        else:d[(mij,sij)]=1
        di|={mij}
r=0
for i in di:
    if (i,0) in d.keys() and (i,1) in d.keys():
        r += d[(i,0)]*d[(i,1)]
#print(m)
#print(d,di)
print(r)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, S):
    g = defaultdict(dict)
    for i, r in enumerate(S):
        for j, c in enumerate(r):
            if i > 0 and S[i-1][j] != c:
                g[(i, j)][(i-1, j)] = 1
                g[(i-1, j)][(i, j)] = 1
            if i < H-1 and S[i+1][j] != c:
                g[(i, j)][(i+1, j)] = 1
                g[(i+1, j)][(i, j)] = 1
            if j > 0 and S[i][j-1] != c:
                g[(i, j)][(i, j-1)] = 1
                g[(i, j-1)][(i, j)] = 1
            if j < W-1 and S[i][j+1] != c:
                g[(i, j)][(i, j+1)] = 1
                g[(i, j+1)][(i, j)] = 1
    
    ans = 0
    for k in g:
        i, j = k
        if S[i][j] != '#':
            continue
        s = [k]
        done = set([k])
        while s:
            # print(s)
            k = s.pop()
            for n in g[k]:
                if n not in done:
                    s.append(n)
                    done.add(n)
            i, j = k
            if S[i][j] == '.':
                ans += 1
            

    return ans


def main():
    # H, W = read_int_n()
    # S = []
    # for _ in range(H):
    #     S.append(read_str())
    S = []
    H = 400
    W = 400
    for _ in range(H):
        S.append(random.choices('#.', k=W))
    print(slv(H, W, S))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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(x, y):
        checked[y][x] = True
        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:
                w_add, b_add = search(nx, ny)
                w_cnt += w_add
                b_cnt += b_add
        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]:
                w_cnt, b_cnt = search(x, y)
                ans += w_cnt * b_cnt

    print(ans)

main()

Submission status: Runtime Error

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

res = 0
ans = [[0]*w for i in range(h)]


def f(x,y):
    c = 0
    if x+1 < h and s[x+1][y] =="#" and ans[x+1][y] == 0:
        ans[x+1][y] = 1
        c += 1
        if x+2 < h and s[x+2][y] == ".":
            c += f(x+2,y)
        if y+1 < w and s[x+1][y+1] == ".":
            c += f(x+1,y+1)
    if y+1 < w and s[x][y+1] == "#" and ans[x][y+1] == 0:
        ans[x][y+1] = 1
        c += 1
        if x+1 <h and s[x+1][y+1] == ".":
            c += f(x+1,y+1)
        if y+2 < w and s[x][y+2] == ".":
            c += f(x,y+2)
    return c

def g(x,y):
    c = 0
    if x+1 < h and s[x+1][y] =="." and ans[x+1][y] == 0:
        ans[x+1][y] = 1
        c += 1
        if x+2 < h and s[x+2][y] == "#":
            c += g(x+2,y)
        if y+1 < w and s[x+1][y+1] == "#":
            c += g(x+2,y)
    if y+1 < w and s[x][y+1] == "." and ans[x][y+1] == 0:
        ans[x][y+1] = 1
        c += 1
        if x+1 <h and s[x+1][y+1] == "#":
            c += g(x+1,y+1)
        if y+2 < w and s[x][y+2] == "#":
            c += g(x,y+2)
    return c
res = 0
for i in range(h):
    for j in range(w):
        ans = [[0]*w for i in range(h)]
        if s[i][j] == ".":
            #print(f(i,j))
            res += f(i,j)
        else:
            #print(g(i,j))
            res += g(i,j)
            

print(res)

Submission status: Runtime Error

Solution code:
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: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(114514)

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: Runtime Error

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
def dfs(k):
  black = 1 if color[k] == '#' else 0
  white = 1 if color[k] == '.' else 0
  visited[k] = True
  for dst in edge[k]:
    if not visited[dst]:
      b, w = dfs(dst)
      black += b
      white += w
  return black, white

ans = 0
for k in range(i):
  black, white = dfs(k)
  ans += black * white
print(ans)

Submission status: Runtime Error

Solution code:
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)