서로 공격하지 않도록 기물 제거하기

시간 제한1초메모리 제한128 MB

요약

최대 15개 기물이 놓인 보드마다 서로 공격하지 않는 기물만 남도록 치우는 최소 개수를 구합니다.

난이도: 보통10점 중 5점
유형: 완전 탐색, 그래프, 비트 연산
정답자: 아직 제출이 없습니다

문제

체스에서 기물을 잃지 않으려면 애초에 서로 마주치지 않게 두는 것이 좋은 전략이다. IBM은 딥블루에게 이 전략을 가르치려고 한다. 그래서 보드에 남은 기물끼리 아무도 서로를 공격하지 않는 상태로 만들려면 기물을 최소 몇 개 없애야 하는지 구하는 프로그램이 필요하다.

모든 기물은 일반적인 체스 규칙대로 공격한다.

킹(King): 상하좌우와 대각선으로 인접한 칸을 공격한다.
퀸(Queen): 상하좌우와 대각선으로 거리 제한 없이 공격한다.
비숍(Bishop): 대각선으로 거리 제한 없이 공격한다.
룩(Rook): 상하좌우로 거리 제한 없이 공격한다.
나이트(Knight): L자로 공격한다. 상하좌우 중 한 방향으로 두 칸 간 다음, 그와 직각인 방향으로 한 칸 간 자리가 공격 범위다. 아래 그림을 참고한다.
폰(Pawn): 이 문제에 폰은 나오지 않는다.

---------------
| | |*| |*| | |
---------------
| |*| | | |*| |
---------------
| | | |N| | | |
---------------
| |*| | | |*| |
---------------
| | |*| |*| | |
---------------
N = 나이트
* = 나이트가 공격할 수 있는 칸

두 기물 사이를 다른 기물이 막고 있는 상황까지 따져도 답은 같으므로, 경로가 막히는지는 신경 쓰지 않아도 된다.

입력

입력은 최대 100개의 데이터 셋으로 이루어지고, 데이터 셋 사이를 구분하는 빈 줄은 없다. 보드는 최대 10x10이며, 한 데이터 셋에 놓인 기물은 최대 15개다.

각 데이터 셋은 다섯 부분으로 나뉜다.

첫 줄에 START가 주어진다.
다음 줄에 보드의 가로 길이 $w$ 가 주어진다. ( $1 \le w \le 10$ )
다음 줄에 보드의 세로 길이 $h$ 가 주어진다. ( $1 \le h \le 10$ )
이어지는 $h$ $h$ 개의 줄에 보드의 모양이 주어진다. 각 줄에는 글자 $w$ $w$ 개가 공백으로 구분되어 있고, $n$ $n$ 번째 줄이 보드의 $n$ $n$ 번째 행이다. 각 글자의 뜻은 다음과 같다.
- K: 킹
- Q: 퀸
- R: 룩
- B: 비숍
- N: 나이트
- E: 빈 칸
마지막 줄에 END가 주어진다.

입력은 파일의 끝에서 끝난다.

출력

데이터 셋마다 한 줄씩 다음 형식으로 출력한다. 출력 사이를 구분하는 빈 줄은 없다.

Minimum Number of Pieces to be removed: X

여기서 X는 남은 기물끼리 서로 공격하지 않게 만들려고 제거해야 하는 기물의 최소 개수다.

예제1

예제 1

입력

START
3
3
K E K
E Q E
K E K
END
START
8
8
E E E E E E E E
E B E K E E N E
E E E E N E E E
E E E E E E E R
B E Q E E E E E
E E E E E Q E E
E E E E E B E E
E B E R E E E E
END

예상 출력

Minimum Number of Pieces to be removed: 1
Minimum Number of Pieces to be removed: 5