9495번 - 바둑

문제

N×N 크기의 바둑판이 주어진다. 바둑판 위의 흰돌은 'o', 검은돌은 'x', 빈칸은 '.'로 표현한다. 입력으로 주어지는 바둑판의 상태에서 흰돌은 서로 인접해있지 않다.

홍준이는 검은돌을 추가로 더 놓아서 흰돌을 잡을 수 있다. 실제 바둑과는 조금 다르게 흰돌은 검은돌을 잡을 수 없다.

이때, 홍준이는 빈 칸의 개수를 최대로 하려고 한다. 검은돌을 놓으면 흰돌을 잡아 빈 칸이 생기게 되지만, 검은돌을 놓은 만큼 빈 칸의 개수가 줄어들게 되기 때문에 고민에 빠졌다.

홍준이를 도와 빈 칸의 개수를 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 바둑판의 크기 N이 주어진다. (3 ≤ N ≤ 50) 다음 N개의 줄에는 바둑판의 정보가 주어진다. 흰돌은 'o', 검은돌은 'x', 빈 칸은 '.'이다. 흰돌은 서로 인접해있지 않게 주어진다.

출력

만들 수 있는 빈 칸의 최대 개수를 출력한다.

제한

힌트