Bishop > 문제은행

fff

1290 : Bishop

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
38 회   
시도횟수
284 회   

문제

“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


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010-2019 jungol. All right reserved.

TOP