2464. Checkers

The cows have taken up the game of checkers with a vengeance.Unfortunately, despite their infinite enjoyment of playing, they are terrible at the endgame. They want your help.

Given an NxN (4 <= N <= 30) checkboard, determine the optimal set of moves to end the game on the next move. Checkers move only on the ‘+’ squares and capture by jumping ‘over’ an opponent’s piece. The piece is removed as soon as it is jumped. See the example below

where N=8:

• The K’s mark Bessie’s kings; the o’s represent the
• opponent’s checkers. Bessie always moves next. The
• K - + - + Kings jump opponent’s checkers successively in any
• diagonal direction (and removes pieces when jumped).
• o - o - + - +

• K - + - + - For this board, the solution requires the lower left
• o - + - + - + King to jump successively across all three of the

• K - + - K - opponents’ checkers, thus ending the game (moving K

marked as >K<):

Original

• +
• -
• K - + - +
• -
• o - o - + - +

• K - + - + -
• o - + - + - +

• ->K<- + - K -

After move 1

• +
• -
• K - + - +
• -
• o - o - + - +

K<- K - + - + -

• +
• K -

After move 2

• +
• -
• K - + - +
• ->K<- + - + -

• o - + - +
• K - + - + -
• +
• K - + - K -

After move 3

• +
• -
• K - + - +
• -
• +
• K ->K<- + -
• +
• K - + - K -

The moves traversed these squares:

1 2 3 4 5 6 7 8 R C

1 - + - + - + - + start: 8 3

2 + - + - + - + - move: 6 1

3 - + - K - + - + move: 4 3

4 + - * - + - + - move: 6 5

5 - o - o - + - +

6 * - K - * - + -

7 - o - + - + - +

8 + - K - + - K -

Write a program to determine the (unique, as it turns out) game-ending sequence for an NxN input board if it exists. There is at least a king and at least one opponent piece on the board.

输入格式

• Line 1: A single integer: N

• Lines 2..N+1: Line i+1 contains N characters (each one of: ‘-‘, ‘+’,

‘K’, or ‘o’) that represent row i of a proper checkboard.

输出格式

• Lines 1..?: If this sequence of moves is impossible, output

“impossible” on a line by itself. If such a sequence exist,

each line contains two space-separated integers that represent

successive locations of a king whose moves will win the game.

样例

Input
8
-+-+-+-+
+-+-+-+-
-+-K-+-+
+-+-+-+-
-o-o-+-+
+-K-+-+-
-o-+-+-+
+-K-+-K-

Output
8 3
6 1
4 3
6 5


0 人解决，3 人已尝试。

0 份提交通过，共有 9 份提交。

9.9 EMB 奖励。