题目描述

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 NxN (4 <= N <= 500) 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 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 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          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 - 

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 NxN 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.

POINTS: 330

输入格式

* 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. 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.

题目大意

题目描述

奶牛在激烈地下跳棋。

不幸的是，尽管他们玩得很开心，但他们在最后阶段很艰难，需要你的帮助。

给定一个 $N \times N(4 \le N \le 500)$ 的棋盘，确定帮助贝西“吃”掉所有对方棋子的移动次数最少的路径。

移动规则：

1. 沿对角线方向移动。

2. 必须越过对方棋子到达下一个位子。

3. 被越过的对方棋子视为“吃”掉。

4. 贝西只能操控她的其中1个国王连续移动。

请看下面的例子，其中 $N=8$ ：

1. 对手棋子标记为 o

2. 贝西的国王标记为 K

3. 正在移动的国王标记为 >K<

初始状态             移动一次后          移动两次后           移动三次后
- + - + - + - +     - + - + - + - +    - + - + - + - +     - + - + - + - + 
+ - + - + - + -     + - + - + - + -    + - + - + - + -     + - + - + - + - 
- + - 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          行 列 
1 - + - + - + - +    起点:  8  3 
2 + - + - + - + -    路径:  6  1 
3 - + - K - + - +    路径:  4  3 
4 + - * - + - + -    路径:  6  5 
5 - o - o - + - + 
6 * - K - * - + - 
7 - o - + - + - + 
8 + - K - + - K - 

编写一个程序来确定贝西的国王的移动路径。棋盘上至少有一个国王和一个对手棋子。

输入格式

第一行有一个整数 $N$。

接下来 $N$ 行是一个 $N \times N$ 的矩阵，每个字符之间没有空格。

输出格式

若有一条路径，输出每行包含两个空格分隔的整数，表示一位国王的连续位置。

若没有这样的路径,则一行输出"impossible"。

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

8 3 
6 1 
4 3 
6 5