문제
“N×N 의 체스판에 Queen이 서로 공격하지 않도록 놓을 수 있는 방법을 찾아라.”
위 문제는 유명한 N-Queen 문제이다.
자료구조 시간에 N-Queen 문제를 풀면서 백트래킹을 마스터했다고 생각한 LIBe는
보다 더 어려운 문제를 풀이보기 위해서 문제를 다음과 같이 변경하였다.
“체스판에 장애물들이 있고, Queen이 장애물을 넘어갈 수 없을 때 최대로 놓을 수 있는 Queen의 개수는 몇 개일까?”
그러나 세상의 모든 일은 생각대로 되지 않는 법. 코딩 스킬이 부족했던 LIBe는 위 문제를 풀다가 포기하고 결국 문제를 다음과 같이 변경하였다.
체스판에 장애물들이 있고, Bishop이 장애물을 넘어갈 수 없을 때 최대로 놓을 수 있는 Bishop의 개수를 찾는 프로그램을 작성하시오. (Queen은 가로, 세로, 대각선으로 이동할 수 있으나, Bishop는 대각선으로만 이동이 가능하다.)
입력
입력은 여러 개의 테스트 케이스로 주어진다. 입력의 첫 줄에는 테스트 케이스의 개수 T(1≤T≤100)가 들어온다.
각각의 테스트 케이스의 첫 줄에는 체스판의 크기 N(1≤N≤8)이 주어진다.
이후 N 줄에는 체스판의 상태가 주어진다.
'.'은 Bishop을 놓을 수 있는 곳이며, '*'은 장애물이다.
출력
각각의 테스트 케이스들에 대해 최대로 놓을 수 있는 Bishop의 개수를 출력한다.
예제
2
5
.....
.....
.....
.....
.....
8
..**.*.*
**.***.*
*.**...*
.*.**.**
*.**.*.*
..**.*.*
...*.*.*
**.*.*.*
8
18
출처
Ajou U Programming Contest, algospot BISHOPS
로그인해야 코드를 작성할 수 있어요.