시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 14 10 8 80.000%

문제

민호화 강호는 바둑을 하고 있다. 민호는 흑색, 강호는 백색이다.

현재 바둑판 위에는 백돌이 인접해 있지 않다. 강호는 이미 항복한 상태로 바둑판 위에 돌을 더 놓을 수 없다. 민호는 바둑판 위에 돌을 더 놓을 수 있으며, 바둑판 위의 빈 칸의 개수를 최대로 하려고 한다.

민호는 바둑판 위의 빈 칸에 흑돌을 올려놓을 수 있다. 올려놓은 후에는 죽은 백돌을 바둑판 위에서 모두 제거한다. 백돌이 죽었다는 것은 그 칸과 인접한 칸 중에 빈 칸이 없다는 것을 의미한다.

바둑판의 상태가 주어졌을 때, 민호가 만들 수 있는 빈 칸 개수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 바둑판의 가로/세로 크기 N이 주어진다. (3 ≤ N ≤ 50)

둘째 줄부터 N개의 줄에는 바둑판의 상태가 주어지며, 아래 3개의 글자 중 하나이다.

  • 'o': 백돌
  • 'x': 흑돌
  • '.': 빈 칸

백돌이 인접한 경우는 없으며, 모든 백돌은 적어도 하나의 빈 칸과 인접해 있다.

출력

첫째 줄에 만들 수 있는 빈 칸 개수의 최댓값을 출력한다.

예제 입력 1

3
o.o
.o.
o.o

예제 출력 1

5

예제 입력 2

3
...
.o.
...

예제 출력 2

8

예제 입력 3

5
xxxxx
xxoxx
xo.ox
xxoxx
xxxxx

예제 출력 3

4

예제 입력 4

5
.xox.
.o.ox
x.o.o
ox.ox
.ox..

예제 출력 4

12

예제 입력 5

5
o.o.o
.ox..
oxxxo
..x..
o.o.o

예제 출력 5

12

힌트

예제 1의 경우에 (1, 2), (2, 1), (2, 3), (3, 2)에 흑돌을 놓으면 아래와 같은 상태가 된다.

.x.
x.x
.x.

예제 2의 경우에는 아무 돌도 놓지 않는 것이 빈 칸 개수의 최댓값이다.

출처