Problem:


 MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Problem D: Fissure Puzzle Easy

Problem

$N \times N$個のマスから成るグリッドがある。最初すべてのマスは白色である。以下の手順に従って黒色のマスを増やしていく。

上から偶数番目かつ、左から偶数番目であるマスの中で、白色のマスを1つ選ぶ。選んだマスは黒色に変化する。さらに、そのマスの上下左右それぞれの方向について、隣接している白色のマスも連鎖的に黒色に変化する。この連鎖はその方向に白色のマスが存在しなくなるまで続く。(以下に例を示す)

□□□□□□□□□

□□□□□□□□□

□□□□□□□□□

□□□□□□□□□

□□□□□□□□□

□□□□□□□□□

□□□□□□□□□

□□□□□□□□□

□□□□□□□□□

↓上から4番目、左から6番目を選ぶ

□□□□□■□□□

□□□□□■□□□

□□□□□■□□□

■■■■■■■■■

□□□□□■□□□

□□□□□■□□□

□□□□□■□□□

□□□□□■□□□

□□□□□■□□□

↓上から2番目、左から2番目を選ぶ

□■□□□■□□□

■■■■■■□□□

□■□□□■□□□

■■■■■■■■■

□□□□□■□□□

□□□□□■□□□

□□□□□■□□□

□□□□□■□□□

□□□□□■□□□

↓上から6番目、左から8番目を選ぶ

□■□□□■□□□

■■■■■■□□□

□■□□□■□□□

■■■■■■■■■

□□□□□■□■□

□□□□□■■■■

□□□□□■□■□

□□□□□■□■□

□□□□□■□■□

あなたは上から$i$番目で左から$j$番目のマスの色が$A_{i,j}$であるグリッドを作りたい。マスを選ぶ最小の回数を求めよ。

Input

入力は以下の形式で与えられる。

$N$

$A_{1,1}$ $A_{1,2}$ ... $A_{1,N}$

$A_{2,1}$ $A_{2,2}$ ... $A_{2,N}$

...

$A_{N,1}$ $A_{N,2}$ ... $A_{N,N}$

  $A_{i,j}$が'o'であるときは上から$i$番目、左から$j$番目のマスが白色であることを表し、'x'のときは黒色のマスであることを表す。

Constraints

入力は以下の条件を満たす。

    
$3 \le N \le 127$

    
$N$は奇数である

    
$A_{i,j}$は'o'か'x'である

    
必ず作ることができるような入力しか与えられない

Output

  1行目にマスを選ぶ回数の最小値を出力する。

Sample Input 1

5
oxooo
oxooo
oxooo
xxxxx
oxooo

Sample Output 1

1

Sample Input 2

9
oxoooooxo
oxxxxxxxx
oxoooooxo
xxxxxxxxx
oxoxooooo
oxxxxxxxx
oxoxoxooo
oxoxxxxxx
oxoxoxooo

Sample Output 2

4



Sample input:
5
oxooo
oxooo
oxooo
xxxxx
oxooo


Sample output:
1

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
A = [input() for i in range(n)]

cnt = 0
dd = [[-1, 0], [0, -1], [1, 0], [0, 1]]
used = {}
for i in range(n):
    for j in range(n):
        if A[i][j] == 'x' or (i, j) in used:
            continue
        deq = deque([(j, i)])
        used[i, j] = 1
        cnt += 1
        while deq:
            x, y = deq.popleft()
            for dx, dy in dd:
                nx = x + dx; ny = y + dy
                if 0 <= nx < n and 0 <= ny < n:
                    if A[ny][nx] == 'o' and (ny, nx) not in used:
                        used[ny, nx] = 1
                        deq.append((nx, ny))
print(cnt//3)