题目描述

在国际象棋中，为了避免冲突并维持和平，一个好的策略是移除那些造成最多麻烦的棋子。IBM正在使用其"深蓝"计算机，通过国际象棋游戏来研究这一策略。IBM需要一个程序来计算：为了确保棋盘上剩余的棋子不再互相攻击，最少需要移除多少个棋子。

所有棋子的攻击方式遵循国际象棋标准规则：

• 国王(King) - 可以攻击相邻的任意方向格子（上、下、左、右以及对角线方向）
• 皇后(Queen) - 可以攻击任意距离的任意方向格子（上、下、左、右以及对角线方向）
• 主教(Bishop) - 可以攻击任意距离的对角线方向格子
• 车(Rook) - 可以攻击任意距离的上、下、左、右方向格子（不能对角线攻击）
• 兵(Pawns) - 本题不包含兵
• 骑士(Knight) - 采用标准的"L"形攻击方式（如横向两步纵向一步，或横向一步纵向两步等）。下图展示了骑士的攻击范围：

	 --------------
	| | |*| |*| | |
	---------------
	| |*| | | |*| |
	---------------
	| | | |N| | | |
	---------------
	| |*| | | |*| |
	---------------
	| | |*| |*| | |
	---------------
	N = 骑士
	* = 骑士可以攻击的格子

输入格式

输入包含最多100组数据，每组数据描述一个棋盘状态，格式如下（数据组间无空行）：

1. 起始行 - 单行"START"
2. 棋盘宽度（列数） - 一个正整数$w（1 ≤ w ≤ 10）$
3. 棋盘高度（行数） - 一个正整数$h（1 ≤ h ≤ 10）$
4. 棋盘布局 - h行，每行对应棋盘的一行（第一行对应棋盘第一行，依此类推）。每行是由空格分隔的单个字母列表，每个字母表示棋盘对应格子的内容：
   • K - 国王
   • Q - 皇后
   • R - 车
   • B - 主教
   • N - 骑士
   • E - 空格子
5. 结束行 - 单行"END"

输出格式

每组数据输出一行："Minimum Number of Pieces to be removed: X"，其中X为需要移除的最少棋子数，使得剩余棋子互不攻击。

输入样例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

输出样例1

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

来源

South Central USA 2001