Bishops

문제 정보

문제

“N*N의 체스판에 Queen이 서로 공격하지 않도록 놓을 수 있는 방법을 찾아라.”

위 문제는 유명한 N-Queen 문제이다. 자료구조 시간에 N-Queen 문제를 풀면서 백트래킹을 마스터했다고 생각한 LIBe는 보다 더 어려운 문제를 풀이보기 위해서 문제를 다음과 같이 변경하였다.

“체스판에 장애물들이 있고, Queen이 장애물을 넘어갈 수 없을 때 최대로 놓을 수 있는 Queen의 개수는 몇 개일까?”

그러나 세상의 모든 일은 생각대로 되지 않는 법. 코딩 스킬이 부족했던 LIBe는 위 문제를 풀다가 포기하고 결국 문제를 다음과 같이 변경하였다.

“체스판에 장애물들이 있고, Bishop이 장애물을 넘어갈 수 없을 때 최대로 놓을 수 있는 Bishop의 개수는 몇 개일까?”

LIBe는 과연 이 문제를 풀 수 있을까?

입력

입력은 여러 개의 테스트 케이스로 주어진다. 입력의 첫 줄에는 테스트 케이스의 개수 T가 들어온다.
각각의 테스트 케이스의 첫 줄에는 체스판의 크기 N (1 <= N <= 8)이 주어진다.
이후 N줄에는 체스판의 상태가 주어진다. .은 Bishop을 놓을 수 있는 곳이며, *은 장애물이다.

출력

각각의 테스트 케이스들에 대해 최대로 놓을 수 있는 Bishop의 개수를 출력한다.

예제 입력

3
5
.....
.....
.....
.....
.....
8
..**.*.*
**.***.*
*.**...*
.*.**.**
*.**.*.*
..**.*.*
...*.*.*
**.*.*.*
8
*.*.*.*.
.*.*.*.*
*.*.*.*.
.*.*.*.*
*.*.*.*.
.*.*.*.*
*.*.*.*.
.*.*.*.*

예제 출력

8
18
7

노트

4개의 댓글이 있습니다.