BOJ 4672 Don't Get Rooked

문제 링크:

문제 내용

$n \times n$ ($1 \le n \le 4$)크기의 체스판이 있습니다. 이 체스판의 일부 칸에는 장애물이 있습니다.

이 체스판에 서로 공격하는 기물이 없도록 최대한 많은 체스 룩을 놓으려고 합니다. 룩은 상하좌우 네 방향으로 공격할 수 있지만, 장애물을 뛰어넘어서 공격할 수는 없습니다. 이때의 룩의 개수를 출력하세요.

입력

여러 개의 테스트 케이스가 주어집니다. 입력의 마지막에는 0이 주어집니다.

각 테스트 케이스에 대해, $n$의 값이 먼저 주어지고, 그 다음 $n$줄에 체스판이 주어집니다. 장애물은 X, 빈 칸은 .입니다.

출력

각 테스트 케이스에 대해 문제의 정답을 한 줄에 출력합니다.

문제 풀이