문제1014--Bishop

1014: Bishop

실행시간 제한: 5 Sec  메모리사용 제한: 128 MB
제출: 657  통과: 92
[제출] [채점기록] [묻고답하기]

문제 설명

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

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

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

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

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

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

입력 설명

입력은 여러 개의 테스트 케이스로 주어진다. 입력의 첫 줄에는 테스트 케이스의 개수 $T$ $(1 \leq T \leq 100)$가 들어온다.

각각의 테스트 케이스의 첫 줄에는 체스판의 크기 $N$ $(1 \leq N \leq 8)$이 주어진다. 이후 $N$ 줄에는 체스판의 상태가 주어진다. .은 Bishop을 놓을 수 있는 곳이며, *은 장애물이다.

출력 설명

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

입력 예시 Copy

2
5
.....
.....
.....
.....
.....
8
..**.*.*
**.***.*
*.**...*
.*.**.**
*.**.*.*
..**.*.*
...*.*.*
**.*.*.*

출력 예시 Copy

8
18

출처/분류