[USACO Dec08]跳棋获胜

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file winchk.in Output file winchk.out

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

给一个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