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:
import sys

sys.setrecursionlimit(10 ** 9)

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

visited = [[False for _ in range(W)] for _ in range(H)]
vectors = [[0, -1], [-1, 0], [0, 1], [1, 0]]
ans = 0

def dfs(h, w):
    # 入力された値はindex out of rangeにならないvalidationが掛けられている
    if visited[h][w]:
        return (0, 0)
    
    visited[h][w] = True

    if inputs[h][w] == '#':
        black, white = 1, 0 
    else:
        black, white = 0, 1

    for vector in vectors:
        next_h = h + vector[0]
        next_w = w + vector[1]
        if not (0 <= next_h < H and 0 <= next_w < W):
            continue
        next_color = inputs[next_h][next_w]
        if inputs[h][w] != next_color:
            p_black, p_white = dfs(next_h, next_w)
            black += p_black
            white += p_white

    return (black, white)

for h in range(H):
    for w in range(W):
        black, white = dfs(h, w)
        ans += black * white  

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

# AISing Programming Contest 2019：C - Alternating Path
import sys
sys.setrecursionlimit(10000000)

H, W = [int(i) for i in raw_input().strip().split(' ')]
S = []
for _ in range(H):
    S.append(raw_input().strip())
C = '#.'
CR = {'#':0, '.':1}


def find(h, w, sumi):
    while True:
        if sumi[h][w] == False:
            return (h, w)
        w += 1
        if w >= W:
            w = 0
            h += 1
            if h >= H:
                return None
    return None


def chain((h, w), t, c, sumi):
    if 0 <= h < H and 0 <= w < W:
        pass
    else:
        return c
    if sumi[h][w]:
        return c
    if S[h][w] == C[t]:
        sumi[h][w] = True
        c[t] += 1
        for ptr in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
            c = chain((h+ptr[0], w+ptr[1]), 1-t, c, sumi)
        return c
    return c


def main():
    sumi = [[False for _ in range(W)] for _ in range(H)]
    h, w = 0, 0
    n = 0
    while True:
        c = [0, 0]
        # print 'sumi:', sumi
        result = find(h, w, sumi)
        if not result:
            break
        h, w = result[0], result[1]
        # print 'found:', h, w
        c = chain((h, w), CR[S[h][w]], c, sumi)
        # print c
        n += c[0] * c[1]
    print n


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

# AISing Programming Contest 2019：C - Alternating Path
C = '#.'
CR = {'#':0, '.':1}

H, W = [int(i) for i in raw_input().strip().split(' ')]
S = []
for _ in range(H):
    # S.append(raw_input().strip())
    S.append([CR[c] for c in raw_input().strip()])


def find(h, w, sumi):
    while True:
        if sumi[h][w] == False:
            return (h, w)
        w += 1
        if w >= W:
            w = 0
            h += 1
            if h >= H:
                return None
    return None


'''
def chain((h, w), t, c, sumi):
    if 0 <= h < H and 0 <= w < W:
        pass
    else:
        return c
    if sumi[h][w]:
        return c
    if S[h][w] == t:
        sumi[h][w] = True
        c[t] += 1
        for ptr in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
            c = chain((h+ptr[0], w+ptr[1]), 1-t, c, sumi)
        return c
    return c
'''


# dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
dd = [(0, 1), (1, 0), (0, -1), (-1, 0)]

def find_chain((hh, ww), t, sumi):
    # chain_sumi = [[False for _ in range(W)] for _ in range(H)]
    chain_sumi = set()
    h, w = hh, ww
    sumi[h][w] = True
    chain_sumi.add((h, w))
    c = [0, 0]
    c[t] = 1
    d = 0
    stack = []
    while True:
        while True:
            if d >= 4:
                break
            hd = h + dd[d][0]
            wd = w + dd[d][1]
            d += 1
            if 0 <= hd < H and 0 <= wd < W:
                if (hd, wd) not in chain_sumi:
                    td = S[hd][wd]
                    if td == t-((hh+ww+hd+wd)&1):
                        sumi[hd][wd] = True
                        chain_sumi.add((hd, wd))
                        c[td] += 1
                        stack.append([h, w, d])
                        h , w, d = hd, wd, 0
        if len(stack) == 0:
            break
        h, w, d = stack.pop()
    # print 'sumi :', sumi
    # print 'chain_sumi :', chain_sumi
    return c


def main():
    sumi = [[False for _ in range(W)] for _ in range(H)]
    h, w = 0, 0
    n = 0
    while True:
        # print 'sumi:', sumi
        result = find(h, w, sumi)
        if not result:
            break
        h, w = result[0], result[1]
        # print 'found:', h, w
        c = find_chain((h, w), S[h][w], sumi)
        # print c
        n += c[0] * c[1]
    print n


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jan 12 18:50:46 2019
AIsingD
@author: maezawa
"""

h, w = list(map(int, input().split()))
a = [list('*'*(w+2))]
for _ in range(h):
    a.append(['*']+list(input())+['*'])
a.append(list('*'*(w+2)))
b = [[0]*(w+2) for _ in range(h+2)]
#print(a)

dirs = [(-1,0),(0,1),(1,0),(0,-1)]
ans = 0

for i in range(1, h+1):
    for j in range(1, w+1):
        if a[i][j] == '#' and b[i][j] == 0:
            stackb = [(i, j)]
            cntb = 0
            cntw = 0
            stackw = []
            while stackb:
                inext, jnext = stackb.pop(-1)
                if b[inext][jnext] != 0:
                    continue
                cntb += 1
                b[inext][jnext] = 1
                for direction in dirs:
                    inextb = inext + direction[0]
                    jnextb = jnext + direction[1]
                    if a[inextb][jnextb] == '.' and b[inextb][jnextb] == 0:
                        stackw.append((inextb,jnextb))
                while stackw:
                    inext, jnext = stackw.pop(-1)
                    if b[inext][jnext] != 0:
                        continue
                    cntw += 1
                    b[inext][jnext] = 1
                    for direction in dirs:
                        inextw = inext + direction[0]
                        jnextw = jnext + direction[1]
                        if a[inextw][jnextw] == '#' and b[inextw][jnextw] == 0:
                            stackb.append((inextw,jnextw))

            #print((i,j),cntb, cntw)
            ans += cntb*cntw
print(ans)

Submission status: Accepted

Solution code:
import itertools
H, W = [int(_) for _ in input().split()]
S = [input() for _ in range(H)]
is_searched = [[False for _ in range(W)] for _ in range(H)]


def dfs(p, q):
    if is_searched[p][q] == 1:
        return 0
    count = {'#': 0, '.': 0}
    stack = [[p, q]]
    while stack:
        x, y = stack.pop()
        if is_searched[x][y] != 1:
            is_searched[x][y] = 1
            count[S[x][y]] += 1
            dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]
            for dx, dy in dxy:
                nx, ny = x + dx, y + dy
                if 0 <= nx < H and 0 <= ny < W and S[x][y] != S[nx][ny]:
                    stack += [[nx, ny]]
    return count['#'] * count['.']


ans = 0
for i, j in itertools.product(range(H), range(W)):
    ans += dfs(i, j)
print(ans)

Submission status: Accepted

Solution code:
import itertools
H, W = [int(_) for _ in input().split()]
S = [input() for _ in range(H)]
is_searched = [[False for _ in range(W)] for _ in range(H)]


def dfs(p, q):
    if is_searched[p][q] == 1:
        return 0
    count = {'#': 0, '.': 0}
    stack = [[p, q]]
    while stack:
        x, y = stack.pop()
        if is_searched[x][y] != 1:
            is_searched[x][y] = 1
            count[S[x][y]] += 1
            dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]
            for dx, dy in dxy:
                nx, ny = x + dx, y + dy
                if 0 <= nx < H and 0 <= ny < W and S[x][y] != S[nx][ny]:
                    stack += [[nx, ny]]
    return count['#'] * count['.']


print(sum([dfs(i, j) for i, j in itertools.product(range(H), range(W))]))

Submission status: Accepted

Solution code:
import itertools
H, W = [int(_) for _ in input().split()]
S = [input() for _ in range(H)]
is_searched = [[False for _ in range(W)] for _ in range(H)]


def dfs(p, q):
    if is_searched[p][q] == 1:
        return 0
    count = {'#': 0, '.': 0}
    que = [[p, q]]
    while que:
        x, y = que.pop(0)
        if is_searched[x][y] != 1:
            is_searched[x][y] = 1
            count[S[x][y]] += 1
            dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]
            for dx, dy in dxy:
                nx, ny = x + dx, y + dy
                if 0 <= nx < H and 0 <= ny < W and S[x][y] != S[nx][ny]:
                    que += [[nx, ny]]
    return count['#'] * count['.']


print(sum([dfs(i, j) for i, j in itertools.product(range(H), range(W))]))

Submission status: Accepted

Solution code:
import itertools
H, W = [int(_) for _ in input().split()]
S = [input() for _ in range(H)]
A = [[0 for _ in range(W)] for _ in range(H)]


def dfs(p, q):
    if A[p][q] == 1:
        return 0
    count = {'#': 0, '.': 0}
    stack = [[p, q]]
    while stack:
        x, y = stack.pop()
        if A[x][y] != 1:
            count[S[x][y]] += 1
            A[x][y] = 1
            dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]
            for dx, dy in dxy:
                nx, ny = x + dx, y + dy
                if 0 <= nx < H and 0 <= ny < W and S[x][y] != S[nx][ny]:
                    stack += [[nx, ny]]
    return count['#'] * count['.']


print(sum([dfs(i, j) for i, j in itertools.product(range(H), range(W))]))

Submission status: Accepted

Solution code:
def main():
    """
    1 <= H, W <= 400
    |Si| = W  (#, .)
    """
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]

    ans = f(H, W, S)
    print(ans)


def f(H, W, S):
    ans1 = editorial(H, W, S)
    ans2 = f_rec(H, W, S)

    assert ans1 == ans2
    return ans1


def editorial(H, W, S):
    """
    ある地点からの黒と白のマスの数
    黒から白への行き方は
    黒の数から白の数
    """
    from collections import deque
    di = [1, 0, -1, 0]
    dj = [0, 1, 0, -1]
    color = [[S[i][j] == "#" for j in range(W)]
             for i in range(H)]
    used = [[False] * W for i in range(H)]

    ans = 0
    for i in range(H):
        for j in range(W):
            if used[i][j]:
                continue
            used[i][j] = True

            b, w = 0, 0
            que = deque([(i, j)])
            while que:
                ci, cj = que.pop()
                if color[ci][cj]:
                    b += 1
                else:
                    w += 1

                for d in range(4):
                    ni = ci + di[d]
                    nj = cj + dj[d]
                    in_range = 0 <= ni < H and 0 <= nj < W
                    if not in_range:
                        continue
                    if used[ni][nj]:
                        continue
                    if color[ci][cj] == color[ni][nj]:
                        continue

                    used[ni][nj] = True
                    que.append((ni, nj))

            ans += b * w

    return ans


def f_rec(H, W, S):
    import sys
    sys.setrecursionlimit(10 ** 9)
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    def rec(h, w, vis):
        vis[h][w] = True
        bl, wh = 0, 0
        if S[h][w] == "#":
            bl += 1
        else:
            wh += 1

        for i in range(4):
            ny = h + dy[i]
            nx = w + dx[i]
            in_range = 0 <= ny < H and 0 <= nx < W
            if in_range and not vis[ny][nx] and S[ny][nx] != S[h][w]:
                n_bl, n_wh = rec(ny, nx, vis)
                bl += n_bl
                wh += n_wh

        return bl, wh

    vis = [[False] * W for _ in range(H)]
    ans = 0
    for h in range(H):
        for w in range(W):
            bl, wh = rec(h, w, vis)
            ans += bl * wh

    return ans


def TLE_pypy3(H, W, S):
    """
    c1 to c2:
        c1: black(#), c2: white(.)
        c1 - not c1 - c1 - c2

    上下左右に隣り合うマスへの移動を繰り返し
    a to b: N * N = 400 ^ 2 = 1.6 * 10^5
    Nb to Nw == Nw to Nb

    あるマスからどこまで進めるか（直線）
    North <-> South
    West  <-> East

    a to b: ok
    b to c: ok
    a to c: ok (3段論法)

    """
    # south, north, east, west
    d = zip([0, 0, 1, -1],
            [1, -1, 0, 0])
    d = list(d)
    to = {"#": ".", ".": "#"}

    b = []
    for _ in range(H):
        b2 = []
        for _ in range(W):
            b2.append([None] * 4)
        b.append(b2)

    blacks = {}
    for y in range(H):
        for x in range(W):
            src = S[y][x]
            if src == "#":
                blacks[(y, x)] = -1

            for i, (dx, dy) in enumerate(d):
                nx = x + dx
                ny = y + dy

                valid = 0 <= nx < W and 0 <= ny < H
                if not valid:
                    continue

                if S[ny][nx] == to[src]:
                    b[y][x][i] = (ny, nx)

    ans = 0
    # #からなので、候補
    for (y, x), _ in blacks.items():
        # 黒から辿り、１ターンでー候補白を見つけ黒へたどる、次のターンの黒を見つける
        bs = [(y, x)]
        # 辿った黒白のマスをまた辿らないようにする
        used_bs = {}
        used_ws = {}
        while bs:
            by, bx = bs.pop()
            used_bs[(by, bx)] = None

            # 黒から白
            whites = []
            for pos in b[by][bx]:
                if pos and pos not in used_ws:
                    ans += 1
                    whites.append(pos)
                    used_ws[pos] = None

            # 白から黒
            for wy, wx in whites:
                for pos in b[wy][wx]:
                    if pos and pos not in used_bs:
                        bs.append(pos)

    return ans


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    """
    1 <= H, W <= 400
    |Si| = W  (#, .)
    """
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]

    ans = f(H, W, S)
    print(ans)


def f(H, W, S):
    ans1 = editorial(H, W, S)
    #ans2 = f_rec(H, W, S)

    #assert ans1 == ans2
    return ans1


def editorial(H, W, S):
    """
    ある地点からの黒と白のマスの数
    黒から白への行き方は
    黒の数から白の数
    """
    from collections import deque
    di = [1, 0, -1, 0]
    dj = [0, 1, 0, -1]
    color = [[S[i][j] == "#" for j in range(W)]
             for i in range(H)]
    used = [[False] * W for i in range(H)]

    ans = 0
    for i in range(H):
        for j in range(W):
            if used[i][j]:
                continue
            used[i][j] = True

            b, w = 0, 0
            que = deque([(i, j)])
            while que:
                ci, cj = que.pop()
                if color[ci][cj]:
                    b += 1
                else:
                    w += 1

                for d in range(4):
                    ni = ci + di[d]
                    nj = cj + dj[d]
                    in_range = 0 <= ni < H and 0 <= nj < W
                    if not in_range:
                        continue
                    if used[ni][nj]:
                        continue
                    if color[ci][cj] == color[ni][nj]:
                        continue

                    used[ni][nj] = True
                    que.append((ni, nj))

            ans += b * w

    return ans


def f_rec(H, W, S):
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    def rec(h, w, vis):
        vis[h][w] = True
        bl, wh = 0, 0
        if S[h][w] == "#":
            bl += 1
        else:
            wh += 1

        for i in range(4):
            ny = h + dy[i]
            nx = w + dx[i]
            in_range = 0 <= ny < H and 0 <= nx < W
            if in_range and not vis[ny][nx] and S[ny][nx] != S[h][w]:
                n_bl, n_wh = rec(ny, nx, vis)
                bl += n_bl
                wh += n_wh

        return bl, wh

    vis = [[False] * W for _ in range(H)]
    ans = 0
    for h in range(H):
        for w in range(W):
            bl, wh = rec(h, w, vis)
            ans += bl * wh

    return ans


def TLE_pypy3(H, W, S):
    """
    c1 to c2:
        c1: black(#), c2: white(.)
        c1 - not c1 - c1 - c2

    上下左右に隣り合うマスへの移動を繰り返し
    a to b: N * N = 400 ^ 2 = 1.6 * 10^5
    Nb to Nw == Nw to Nb

    あるマスからどこまで進めるか（直線）
    North <-> South
    West  <-> East

    a to b: ok
    b to c: ok
    a to c: ok (3段論法)

    """
    # south, north, east, west
    d = zip([0, 0, 1, -1],
            [1, -1, 0, 0])
    d = list(d)
    to = {"#": ".", ".": "#"}

    b = []
    for _ in range(H):
        b2 = []
        for _ in range(W):
            b2.append([None] * 4)
        b.append(b2)

    blacks = {}
    for y in range(H):
        for x in range(W):
            src = S[y][x]
            if src == "#":
                blacks[(y, x)] = -1

            for i, (dx, dy) in enumerate(d):
                nx = x + dx
                ny = y + dy

                valid = 0 <= nx < W and 0 <= ny < H
                if not valid:
                    continue

                if S[ny][nx] == to[src]:
                    b[y][x][i] = (ny, nx)

    ans = 0
    # #からなので、候補
    for (y, x), _ in blacks.items():
        # 黒から辿り、１ターンでー候補白を見つけ黒へたどる、次のターンの黒を見つける
        bs = [(y, x)]
        # 辿った黒白のマスをまた辿らないようにする
        used_bs = {}
        used_ws = {}
        while bs:
            by, bx = bs.pop()
            used_bs[(by, bx)] = None

            # 黒から白
            whites = []
            for pos in b[by][bx]:
                if pos and pos not in used_ws:
                    ans += 1
                    whites.append(pos)
                    used_ws[pos] = None

            # 白から黒
            for wy, wx in whites:
                for pos in b[wy][wx]:
                    if pos and pos not in used_bs:
                        bs.append(pos)

    return ans


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H, W = [int(x) for x in input().strip().split(" ")]

import sys
sys.setrecursionlimit(1000000)
b = []
bset = set()
wset = set()
i = 0
j = 0
for line in sys.stdin:
    b.append(line.strip())
    for s in line.strip():
        if s == "#":
            bset.add((i, j))
        else:
            wset.add((i, j))
        j += 1
    j = 0
    i += 1

fbset = set()
fwset = set()

def it_b(i, j):
    fbset.add((i, j))
    totalb = 1
    totalw = 0
    bset.remove((i, j))
    #print("b", i,j)
    if i - 1 >= 0:
        if b[i-1][j] == "." and (i-1, j) not in fwset:
            rb, rw = it_w(i-1, j)
            totalb += rb
            totalw += rw
    if j - 1 >= 0:
        if b[i][j-1] == "." and (i, j-1) not in fwset:
            rb, rw = it_w(i, j-1)
            totalb += rb
            totalw += rw
    if i + 1 <= H-1:
        if b[i+1][j] == "." and (i+1, j) not in fwset:
            rb, rw = it_w(i+1, j)
            totalb += rb
            totalw += rw
    if j + 1 <= W-1:
        if b[i][j+1] == "." and (i, j+1) not in fwset:
            rb, rw = it_w(i, j+1)
            totalb += rb
            totalw += rw
    return totalb, totalw

def it_w(i, j):
    fwset.add((i, j))
    totalb = 0
    totalw = 1
    #print("w", i,j)
    if i - 1 >= 0:
        if b[i-1][j] == "#" and (i-1, j) not in fbset:
            rb, rw = it_b(i-1, j)
            totalb += rb
            totalw += rw
    if j - 1 >= 0:
        if b[i][j-1] == "#" and (i, j-1) not in fbset:
            rb, rw = it_b(i, j-1)
            totalb += rb
            totalw += rw
    if i + 1 <= H-1:
        if b[i+1][j] == "#" and (i+1, j) not in fbset:
            rb, rw = it_b(i+1, j)
            totalb += rb
            totalw += rw
    if j + 1 <= W-1:
        if b[i][j+1] == "#" and (i, j+1) not in fbset:
            rb, rw = it_b(i, j+1)
            totalb += rb
            totalw += rw
    return totalb, totalw

t = 0
while True:
    if len(bset) == 0:
        break
    x = bset.pop()
    bset.add(x)
    rb, rw = it_b(x[0], x[1])
    t += rb * rw
print(t)

Submission status: Accepted

Solution code:
#encoding:utf-8

import numpy as np
import sys
sys.setrecursionlimit(1000000)

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


def count_answer(x,y,num_b,num_w):
    # print(used)

    if S[x][y] == "#":
        num_b += 1
    else:
        num_w += 1
    used[x][y] = 1
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    # print("x,y:",x,y)
    for i in range(4):
        next_x = x + dx[i]
        next_y = y + dy[i]
        # print(next_x,next_y)
        if next_x == -1 or next_y == -1 or next_x >= H or next_y >= W:
            pass
        elif used[next_x,next_y] == 1:
            pass
        elif S[next_x][next_y] != S[x][y]:
            num_b,num_w = count_answer(next_x,next_y,num_b,num_w)
    return num_b,num_w

answer = 0
used = np.zeros((H,W))
for i in range(H):
    for j in range(W):
        if used[i][j] == 1:
            continue
        num_b = 0
        num_w = 0
        if S[i][j] == "#":
            num_b,num_w  = count_answer(i,j,num_b,num_w)
            answer += num_b*num_w
print(answer)

Submission status: Accepted

Solution code:
h,w=list(map(int,input().split()))
ans=0
arr=[]
for _ in range(h):
    arr+=[list(input())]
visited={}
for i in range(h):
    for j in range(w):
        visited[(i,j)]=False
for i in range(h):
    for j in range(w):
        stack=[(i,j)]
        visited[(i,j)]=True
        numblack=0
        numwhite=0
        while stack!=[]:
            current=stack.pop()
            if arr[current[0]][current[1]]=='.':
                numwhite+=1
            else:
                numblack+=1
            children=[]
            a,b=current[0],current[1]
            if a-1>=0:
                children+=[(a-1,b)]
            if a+1<h:
                children+=[(a+1,b)]
            if b-1>=0:
                children+=[(a,b-1)]
            if b+1<w:
                children+=[(a,b+1)]
            for child in children:
                if not visited[child] and (arr[child[0]][child[1]]!=arr[current[0]][current[1]]):
                    visited[child]=True
                    stack+=[child]
        ans+=numblack*numwhite
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

MAX_N = 400
di = (1, 0, -1, 0)
dj = (0, 1, 0, -1)

def can_extend(i, j, d, H, W, color):
    ni = i + di[d]
    nj = j + dj[d]
    if not (0 <= ni < H and 0 <= nj < W):
        return False
    if color[i][j] == color[ni][nj]:
        return False
    return True


def solve(H, W, color):
    ans = 0
    is_used = [[False] * MAX_N for i in range(MAX_N)]
    for i in range(H):
        for j in range(W):
            if is_used[i][j]:
                continue
            black = 0
            white = 0
            que = deque()
            is_used[i][j] = True
            que.append((i, j))
            while que:
                p = que.popleft()
                ci = p[0]
                cj = p[1]
                if color[ci][cj]:
                    black += 1
                else:
                    white += 1

                for d in range(4):
                    if not can_extend(ci, cj, d, H, W, color):
                        continue
                    ni = ci + di[d]
                    nj = cj + dj[d]
                    if is_used[ni][nj]:
                        continue
                    is_used[ni][nj] = True
                    que.append((ni, nj))

            ans += black * white

    return ans


H, W = [int(v) for v in input().split()]
s = [input() for i in range(H)]
color = []
for row in s:
    color.append([v == '#' for v in row])

print(solve(H, W, color))

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int,input().split())
s = [input() for _ in range(H)] #'_'は、その変数は使っていないという表現(習慣)

def func(h,w): #黒のみ
    move = [(0,-1), (-1,0),(0,1), (1,0)]
    w_cnt = 0
    b_cnt = 0
    que = deque()
    que.append((h,w))
    while len(que) > 0:
        xh, xw = que.popleft()
        if visited[xh][xw] == 0:
            visited[xh][xw] = 1
            if s[xh][xw] == "#":
                b_cnt += 1
            else:
                w_cnt += 1
        else:
            continue
        for mh, mw in move:
            if 0 <= xh + mh < H and 0 <= xw + mw <W:
                if s[xh][xw] != s[xh+mh][xw+mw] and visited[xh+mh][xw+mw] == 0:
                    que.append((xh+mh,xw+mw))
    return b_cnt, w_cnt

cnt = 0
visited = [[0 for _ in range(W)] for _ in range(H)]

for i in range(H):
    for j in range(W):
        if s[i][j] == "#" and visited[i][j] == 0:
            b_cnt, w_cnt = func(i,j)
            cnt += b_cnt * w_cnt

print(cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

used = [[0]*w for _ in range(h)]
dx=[ 0, 1, 0,-1]
dy=[ 1, 0,-1, 0]

def dfs(x, y):
    global numb, numw #numbたちがグローバル変数だと教えてあげる
    #(x,y)地点を訪問済みにする
    used[x][y] = 1
    #(x,y)地点での処理を行う（マスの色をカウントするなど）
    if board[x][y] == '#':
        numb += 1
    else:
        numw += 1
    #foreach((nx,ny) \in (x,y)のお隣さん){(nx,ny)に訪問していないとき、dfs(nx,ny)} 
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or nx >= h or ny < 0 or ny >= w or used[nx][ny] == 1: continue #範囲外参照 or (nx,ny)は確認済み スキップ
        if board[x][y]!=board[nx][ny]: #さらに(nx,ny)と(x,y)がつながっている場合(nx,ny)を訪問
            dfs(nx,ny)
    return #情報をもらうとき：返り値、各地点の情報のみで更新：グローバル変数、情報を送るとき：引数

ans=0
for i in range(h):
    for j in range(w):
        numw = 0
        numb = 0
        if used[i][j] == 1: continue #すでに確認した地点は見ない
        dfs(i,j)
        ans += numw*numb

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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


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


V=[ [ 0 for i in range(W) ] for j in range(H) ]


def dfs(x,y,current):
	bc=0	#black count
	wc=0	#white count
	q = deque([]) 
	V[x][y]=1
	q.append( (x,y,current) )

	while q:
		x,y,current=q.popleft()

		if current == "#":	  bc+=1
		else:  wc+=1

		for dx,dy in D:
			if 0<=x+dx<H and 0<=y+dy<W:
				next=S[x+dx][y+dy] 
				if V[x+dx][y+dy]==0 and current !=next:
						V[x+dx][y+dy]=1
						q.append( (x+dx, y+dy,next) )

	return bc*wc




ans=0
for x in range(H):
	for y in range(W):
		if S[x][y]=="#" and V[x][y]==0:
			ans+=dfs(x,y, "#")

print ans

Submission status: Accepted

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

from collections import defaultdict

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

class UnionFind:
    def __init__(self, n):
        self.rank = [0]*n
        self.parent = [i for i in range(n)]

    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 merge(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
        elif self.rank[x] > self.rank[y]:
            self.parent[y] = x
        else:
            self.parent[x] = y
            self.rank[y] += 1

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

uf = UnionFind(h * w)
for i in range(h):
    for j in range(w):
        if j < w-1:
            if s[i][j] != s[i][j + 1]:
                uf.merge(i*w + j, i*w + j + 1)
        if i < h-1:
            if s[i][j] != s[i+1][j]:
                uf.merge(i*w + j, (i+1)*w + j)

d_w = defaultdict(int)
d_b = defaultdict(int)
for i in range(h):
    for j in range(w):
        parent = uf.find(i*w + j)
        if s[i][j] == ".":
            d_w[parent] += 1
        else:
            d_b[parent] += 1

ans = 0
for i in range(h):
    for j in range(w):
        ans += d_w[i*w + j] * d_b[i*w + j]

print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
s = [[''] * (w + 2)]
s += [[''] + list(input()) + [''] for _ in range(h)]
s += [[''] * (w + 2)]
m = [[1] * (w + 2)]
m += [[1] + [0] * w + [1] for _ in range(h)]
m += [[1] * (w + 2) for _ in range(h + 2)]
ans = 0
for i in range(1, h + 1):
    for j in range(1, w + 1):
        if m[i][j] == 1:
            continue
        m[i][j] = 1
        qs = [[i, j]]
        white = 0
        black = 0
        while len(qs) != 0:
            q = qs.pop(0)
            if s[q[0]][q[1]] == '.':
                white += 1
            else:
                black += 1
            m[q[0]][q[1]] = 1
            for k in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                if m[q[0] + k[0]][q[1] + k[1]] == 0 and s[q[0]][q[1]] != s[q[0] + k[0]][q[1] + k[1]]:
                    m[q[0] + k[0]][q[1] + k[1]] = 1
                    qs.append([q[0] + k[0], q[1] + k[1]])
        ans += black * white
print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
m = [[0] * w for _ in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if m[i][j] == 1:
            continue
        m[i][j] = 1
        qs = [[i, j]]
        white = 0
        black = 0
        while len(qs) != 0:
            q = qs.pop(0)
            if s[q[0]][q[1]] == '.':
                white += 1
            else:
                black += 1
            m[q[0]][q[1]] = 1
            for k in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                if not (0 <= q[0] + k[0] <= h - 1) or not (0 <= q[1] + k[1] <= w - 1):
                    continue
                if m[q[0] + k[0]][q[1] + k[1]] == 0 and s[q[0]][q[1]] != s[q[0] + k[0]][q[1] + k[1]]:
                    m[q[0] + k[0]][q[1] + k[1]] = 1
                    qs.append([q[0] + k[0], q[1] + k[1]])
        ans += black * white
print(ans)