Description

They often play a game together. No, not StarCraft, but chess.

Du nai se thinks F91 is a chicken. He set up a formation on an $n \times n$ chessboard using black rooks, knights, bishops, a queen, a king, and pawns.

However, F91 thinks Du nai se is a chicken. He issues a challenge: he will control a white knight, move without stepping on any square that is within the attack range of any piece (F91 can move continuously, and Du nai se’s pieces do not move, unless the white knight enters a square in their attack range), and capture Du nai se’s king (i.e., land on the square where the black king is).

Please tell F91 the minimum number of moves needed to accomplish this.

Note:

1. When F91’s white knight moves onto a square occupied by one of Du nai se’s pieces, it captures that piece. That piece no longer threatens the white knight.
2. If the white knight starts in the attack range of a black piece, it is captured immediately and F91 loses at once.
3. Even if the white knight enters the attack range of other pieces at the exact moment it captures the king (i.e., other pieces “guard” the king’s square), F91 still wins.

Attack ranges:

Rook: all squares in the horizontal and vertical directions, until blocked by another piece.

..#..
..#..
##C##
..#..
..#..

Knight: all positions with a horizontal move of 2 and a vertical move of 1, or a horizontal move of 1 and a vertical move of 2 (at most 8 squares, L-shaped).

.#.#.
#...#
..K..
#...#
.#.#.

Bishop: all squares along diagonals ($45^\circ$), until blocked by another piece.

#...#
.#.#.
..B..
.#.#.
#...#

Queen: the combination of rook and bishop (it can attack horizontally/vertically and along $45^\circ$ diagonals, until blocked by other pieces).

#.#.#
.###.
##Q##
.###.
#.#.#

King: the 8 neighboring squares in the 8-connected neighborhood.

.....
.###.
.#X#.
.###.
.....

Pawn: the squares down-left / down-right ($45^\circ$) (at most 2 squares).

.....
.....
..P..
.#.#.
.....

The letters indicate piece types; see the input format. # indicates squares in the attack range.

Input Format

The input contains multiple sets of testdata.

For each set, the first line contains an integer $n$ indicating the board size.

The next $n$ lines each contain a string of length $n$ describing the board.

Where:

• . indicates an empty square.
• O indicates the white knight.
• C indicates a black rook.
• K indicates a black knight.
• B indicates a black bishop.
• Q indicates a black queen.
• X indicates a black king.
• P indicates a black pawn.

Output Format

For each set of testdata, output one integer per line, indicating the minimum number of moves F91 needs.

If it is impossible for F91 to capture the black king no matter how he moves, output -1.

8
...X....
........
........
........
........
........
........
......O.

4

8
......X.
........
.O......
...P.Q.C
.....B..
........
...K....
........

7

Hint

The input contains at most 5 sets of testdata.

• For 20% of the testdata, Du nai se has only the king. $n \le 8$.
• For 30% of the testdata, Du nai se has only the king and knights. $n \le 8$.
• For 60% of the testdata, Du nai se has only the king, knights, and the queen. $n \le 50$.
• For 100% of the testdata, Du nai se may have the full set of 16 pieces (2 rooks, 2 knights, 2 bishops, 1 queen, 1 king, 8 pawns). $n \le 50$.

Kind reminder: the time limit might be tighter than you think. Please pay attention to implementation details to ensure performance.

Explanation for sample 2:

One feasible sequence is:

......X.
.3..6...
.O5.....
4.2P.Q.C
1....B..
........
...K....
........

Translated by ChatGPT 5