SAC E#1 - 一道大水题 Knight
题目背景
毒奶色和F91是好朋友。
题目描述
他们经常在一起玩一个游戏，不，不是星际争霸，是国际象棋。
毒奶色觉得F91是一只鸡。他在一个n×n的棋盘上用黑色的城堡（车）、骑士（马）、主教（象）、皇后（副）、国王（帅）、士兵（卒）摆了一个阵。
然而F91觉得毒奶色是一只鸡。他发起了挑战：他要操纵一个白色骑士，不经过任何一个棋子的攻击范围（F91可以连续行动，而毒奶色的棋子不会动，除非白骑士进入了对方的攻击范围），并击杀毒奶色的国王（即进入黑国王所在的位置）。
请告诉F91他最少需要多少步骤来完成这一项壮举。
注意：
1.当F91的白骑士走到毒奶色的棋子所在的格子上的时候，会击杀（吃掉）该棋子。这个棋子也就不再对F91的白骑士有威胁了。
2.如果白骑士开场就在黑子的攻击范围内，则立刻被击杀、F91立刻失败。
3.即使白骑士在攻击王的瞬间进入了其他棋子攻击范围（即其他棋子“看护”着王所在的格子），依然算F91获胜。
攻击范围：
城堡：横、竖方向所有位置，直到被一个其他棋子阻拦。
```cpp
..#..
..#..
##C##
..#..
..#..
```
骑士：横2竖1或者横1竖2的所有位置（最多8个，类似日字）。
```cpp
.#.#.
#...#
..K..
#...#
.#.#.
```
主教：斜向（45°）所有位置，直到被一个其他棋子阻拦。
```cpp
#...#
.#.#.
..B..
.#.#.
#...#
```
皇后：城堡和主教的结合体（既能横/竖向攻击，也能45°角斜向攻击，直到被其他棋子阻挡）。
```cpp
#.#.#
.###.
##Q##
.###.
#.#.#
```
国王：身边8连通位置的8个格子。
```cpp
.....
.###.
.#X#.
.###.
.....
```
士兵：左下方/右下方（45°）的格子（最多2个）。
`````
.....
.....
..P..
.#.#.
.....
```
其中字母表示棋子类型，参考输入格式。
‘#’表示可攻击范围。
输入输出格式
输入格式
输入包含多组数据。
每一组数据中，第一行一个整数n表示棋盘规模。
接下来n行，每行一个长度为n的字符串。描述棋盘的格局。
其中：
.表示空
O表示白骑士
C表示黑城堡
K表示黑骑士
B表示黑主教
Q表示黒皇后
X表示黑国王
P表示黑士兵
输出格式
对于每一个测试数据，每行输出一个整数，表示F91的最小步数。
如果无论F91如何行动也无法击杀黑国王，输出-1。
输入输出样例
输入样例 #1
8
...X....
........
........
........
........
........
........
......O.输出样例 #1
4输入样例 #2
8
......X.
........
.O......
...P.Q.C
.....B..
........
...K....
........输出样例 #2
7说明
**输入最多包含5组数据。**
对于20%的数据，毒奶色只有国王。n <= 8。
对于30%的数据，毒奶色只有国王、骑士。n <= 8。
对于60%的数据，毒奶色只有国王、骑士、王后。n <= 50。
对于100%的数据，毒奶色可以有全套16颗棋子（2城堡，2骑士，2主教，1后，1王，8兵）。n <= 50。
温馨提示：
时间限制可能比想象之中还要更紧一点，请注意实现细节以保证性能。
样例2解释：
一种可行的做法是：
```cpp
......X.
.3..6...
.O5.....
4.2P.Q.C
1....B..
........
...K....
........
```