시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 256 56 50 30.488%

문제

체스와 관련된 문제는 처음 알고리즘을 배우기 시작할 때 부터 접하게 된다. 가장 유명한 문제로는 N-Queen 문제가 있다. 이를 번형해서 N-Rook 문제를 만들 수 있다. Rook(룩) 은 체스에서 같은 행이나 같은 열의 아무 위치로 이동할 수 있는 체스 말이다.

N × N 크기의 체스판에 룩을 최대한 많이 어떻게 배치할까? 라는 문제는 매우 쉽게 해결할 수 있다. 대각선으로 룩을 배치하면 된다.

문제를 좀 더 어렵게 만들어서, N x N 크기의 체스판에 폰이 몇 개 놓여있다. 이런 상황에서 룩을 최대 몇 개 배치할 수 있을까? 폰이 배치 되어 있으면, 룩은 폰에게 가로막혀 같은 열이나 같은 행의 모든 위치에 이동할 수 없다.

입력

첫 줄에 체스판의 크기 N이 주어진다. (1 ≤ N ≤ 100)

그리고 다음 N개의 줄에 체스판의 정보가 주어진다. '.'은 빈 칸을 의미하고, 'X'는 그 칸에 폰이 있음을 의미한다.

출력

주어진 체스판에 룩을 배치할 때, 최대 몇 개를 배치할 수 있는지 출력한다.

예제 입력

5
X....
X....
..X..
.X...
....X

예제 출력

7

힌트