OI题库

奶牛们开始狂热地喜欢上了跳棋。不幸的是，尽管他们无限享受下棋过程，但他们讨厌思考如何终结棋局，希望得到你的帮助。

给一个NxN (4 <= N <= 500)的棋盘，决定最佳的移动方案（例如：最小的移动步数）来结束游戏。传统的方式，跳棋只能在'+'位置移动，通过跳过对手棋子将对手棋子捕获。当跳的时候，位置也相应移动，如下是一个N=8的情况：

- + - + - + - +

+ - + - + - + -

- + - K - + - +

+ - + - + - + -

- o - o - + - +

+ - K - + - + -

- o - + - + - +

+ - K - + - K -

K是贝茜的国王，o是对手的棋子。贝茜的国王可以成功的通过一些斜线的移动来捕获对手的棋子（跳跃的同时移动位置）

对于这个对局，最好的结果是左下边的K通过三次跳跃结束游戏（移动的 K 标记为 >K<）

   Original          After move 1       After move 2        After move 3

- + - + - + - +     - + - + - + - +    - + - + - + - +     - + - + - + - +

+ - + - + - + -     + - + - + - + -    + - + - + - + -     + - + - + - + -

- + - K - + - +     - + - K - + - +    - + - K - + - +     - + - K - + - +

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

- o - o - + - +     - o - o - + - +    - + - o - + - +     - + - + - + - +

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

- o - + - + - +     - + - + - + - +    - + - + - + - +     - + - + - + - +

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

移动穿越这些方格:

 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 -

对于一个NxN的输入写一个程序决定如何结束游戏，当然如果方案存在原话。至少有一个国王和一个对手的棋子。最佳结论是国王通过每次跳跃进行移动。

输入格式:

* 第1行: 一个单独的整数: N

* 第2..N+1行: 行i+1 包含N个字符 (each one of: '-', '+', 'K', or 'o') 表示一个完整棋盘的第i行. 行2总是由'-'开始.

winchk.in

8

-+-+-+-+

+-+-+-+-

-+-K-+-+

+-+-+-+-

-o-o-+-+

+-K-+-+-

-o-+-+-+

+-K-+-K-

输出格式:

* 第1..?行: 如果没能获胜方案，输出"impossible".如果方案存在，每行包括两个用空格隔开的整数表示国王的移动路线，这个方案必须是可行的获胜方案。

winchk.out

8 3

6 1

4 3

6 5