시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

체스에서 전투를 피하고 기물을 지키려할 때 좋은 전략은 만남을 피하는 것이다. IBM은 Deep Blue에게 체스에서 이런 전략을 학습시키려한다. 따라서 IBM은 서로를 공격하는 기물이 없도록 만들 때, 최소의 없애야할 기물의 수를 찾는 프로그램이 필요하다.

모든 기물은 일반적인 체스 기물의 공격법을 따른다.

  • 킹(King) - 모든 방향으로 인접한 칸 공격 가능.(상하좌우, 대각선)
  • 퀸(Queen) - 모든 방향으로 길이 제한 없이 공격 가능.(상하좌우, 대각선)
  • 비숍(Bishop) - 대각선 방향으로 길이 제한 없이 공격 가능.
  • 룩(Rook) - 상하좌우 방향으로 길이 제한 없이 공격 가능.
  • 폰(Pawns) - 이 문제에서 폰은 없습니다.
  • 나이트(Knight) - L모양으로 공격 가 = [상, 하, 좌, 우]로 두 칸 [좌 또는 우, 좌 또는 우, 상 또는 하, 상 또는 하]로 한칸 있는 곳 공격 가능. 아래 참조
---------------
| | |*| |*| | |
---------------
| |*| | | |*| |
---------------
| | | |N| | | |
---------------
| |*| | | |*| |
---------------
| | |*| |*| | |
---------------
N = 나이트
* = 나이트가 공격할 수 있는 지점

입력

이 문제의 입력은 최고 100개의 데이터 셋으로 이루어진다. 각 데이터 셋은 다음 설명과 같이 구성되어 있으며 데이터 셋을 구분하는 빈 줄은 없다. 보드느 최고 10x10이며 기물은 최고 15개이다.

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

  1. 시작줄 - "START"
  2. 보드 가로 - 한 줄의 자연수 w, 1 <= w <= 10
  3. 보드 세로 - 한 줄의 자연수 h, 1 <= h <= 10
  4. 보드의 생김새 - h 줄의 w개의 띄워쓰기로 구분된 글자가 들어온다. n 번째 줄은 보드의 n번째 행을 의미한다. 각각의 글자는 다음을 의미한다
    • K - 킹(King)
    • Q - 퀸(Queen)
    • R - 룩(Rook)
    • B - 비숍(Bishop)
    • K - 나이트(Knight)
    • E - 빈공간(Empty Square)
  5. 마지막줄 - "END"

출력

각 데이터셋에 대하여 하나의 출력셋이 존재한다. 각각의 출력셋은 빈 줄로 구분되지 않는다.

각 출력셋은 한 줄로 구성되는데 아래의 문장에서 마지막의 X는 남은 기물들이 서로를 공격하지 않기 위해 제거해야할 최소 기물의 수이다.

 "Minimum Number of Pieces to be removed: X"

예제 입력

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

힌트