2462. Winning Checkers

单点时限: 5.0 sec

内存限制: 256 MB

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

Given an () checkboard, determine the optimal set of moves (i.e., smallest number 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 in the traditional way. The piece is removed as soon as it is jumped. See the example below where :

- + - + - + - +  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 best solution requires the lower
- o - + - + - +  left 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 game-ending sequence for an input board if it exists. There is at least a king and at least one opponent piece on the board. The king can jump a piece on every move of the optimal solution.

输入格式

  • Line 1: A single integer:

  • Lines 2..N+1: Line contains characters (each one of: ‘-‘, ‘+’, ‘K’, or ‘o’) that represent row of a proper checkboard. Line 2 always begins with ‘-‘.

输出格式

  • Lines 1..?: If there is no winning sequence of jump, output “impossible” on a line by itself. If such a sequence exists, each line contains two space-separated integers that represent successive locations of a king whose moves will win the game. Any such sequence is acceptable.

样例

Input
8
-+-+-+-+
+-+-+-+-
-+-K-+-+
+-+-+-+-
-o-o-+-+
+-K-+-+-
-o-+-+-+
+-K-+-K-
Output
8 3
6 1
4 3
6 5

1 人解决,4 人已尝试。

2 份提交通过,共有 26 份提交。

9.9 EMB 奖励。

创建: 10 年,11 月前.

修改: 2 年前.

最后提交: 2 年前.

来源: USACO 2008 DEC

题目标签