P3930 SAC E#1 - 一道大水题 Knight

毒奶色和 F91 是好朋友。

他们经常在一起玩一个游戏，不，不是星际争霸，是国际象棋。 毒奶色觉得 F91 是一只鸡。他在一个 $n \times n$ 的棋盘上用黑色的城堡（车）、骑士（马）、主教（象）、皇后（副）、国王（帅）、士兵（卒）摆了一个阵。 然而 F91 觉得毒奶色是一只鸡。他发起了挑战：他要操纵一个白色骑士，不经过任何一个棋子的攻击范围（F91 可以连续行动，而毒奶色的棋子不会动，除非白骑士进入了对方的攻击范围），并击杀毒奶色的国王（即进入黑国王所在的位置）。 请告诉 F91 他最少需要多少步骤来完成这一项壮举。 ### 注意： 1. 当 F91 的白骑士走到毒奶色的棋子所在的格子上的时候，会击杀（吃掉）该棋子。这个棋子也就不再对F91的白骑士有威胁了。 2. 如果白骑士开场就在黑子的攻击范围内，则立刻被击杀、F91立刻失败。 3. 即使白骑士在攻击王的瞬间进入了其他棋子攻击范围（即其他棋子“看护”着王所在的格子），依然算F91获胜。 ### 攻击范围： 城堡：横、竖方向所有位置，直到被一个其他棋子阻拦。 ``` ..#.. ..#.. ##C## ..#.. ..#.. ``` 骑士：横 $2$ 竖 $1$ 或者横 $1$ 竖 $2$ 的所有位置（最多 $8$ 个，类似日字）。 ``` .#.#. #...# ..K.. #...# .#.#. ``` 主教：斜向（$45 \degree$）所有位置，直到被一个其他棋子阻拦。 ``` #...# .#.#. ..B.. .#.#. #...# ``` 皇后：城堡和主教的结合体（既能横 / 竖向攻击，也能 $45 \degree$ 角斜向攻击，直到被其他棋子阻挡）。 ``` #.#.# .###. ##Q## .###. #.#.# ``` 国王：身边 $8$ 连通位置的 $8$ 个格子。 ``` ..... .###. .#X#. .###. ..... ``` 士兵：左下方 / 右下方（$45 \degree$）的格子（最多 $2$ 个）。 ``` ..... ..... ..P.. .#.#. ..... ``` 其中字母表示棋子类型，参考输入格式。 `#` 表示可攻击范围。

输入包含多组数据。 每一组数据中，第一行一个整数 $n$ 表示棋盘规模。 接下来 $n$ 行，每行一个长度为 $n$ 的字符串。描述棋盘的格局。 其中： `.` 表示空 `O` 表示白骑士 `C` 表示黑城堡 `K` 表示黑骑士 `B` 表示黑主教 `Q` 表示黒皇后 `X` 表示黑国王 `P` 表示黑士兵

对于每一个测试数据，每行输出一个整数，表示 F91 的最小步数。 如果无论 F91 如何行动也无法击杀黑国王，输出 `-1`。

**输入最多包含5组数据。** - 对于 $20\%$ 的数据，毒奶色只有国王。$n \le 8$。 - 对于 $30\%$ 的数据，毒奶色只有国王、骑士。$n \le 8$。 对于 $60\%$ 的数据，毒奶色只有国王、骑士、王后。$n \le 50$。 对于 $100\%$ 的数据，毒奶色可以有全套 $16$ 颗棋子（$2$ 城堡，$2$ 骑士，$2$ 主教，$1$ 后，$1$ 王，$8$ 兵）。$n \le 50$。 温馨提示： 时间限制可能比想象之中还要更紧一点，请注意实现细节以保证性能。 样例 $2$ 解释： 一种可行的做法是： ``` ......X. .3..6... .O5..... 4.2P.Q.C 1....B.. ........ ...K.... ........ ```