[USACO08DEC] Winning Checkers G
题意翻译
## 题目描述
奶牛在激烈地下跳棋。
不幸的是，尽管他们玩得很开心，但他们在最后阶段很艰难，需要你的帮助。
给定一个 $N \times N(4 \le N \le 500)$ 的棋盘，确定帮助贝西“吃”掉**所有对方棋子**的移动次数最少的路径。
移动规则：
1. 沿对角线方向移动。
1. 必须越过对方棋子到达下一个位子。
1. 被越过的对方棋子视为“吃”掉。
1. 贝西只能操控她的其中**1**个国王**连续**移动。
请看下面的例子，其中 $N=8$ ：
1. 对手棋子标记为 o
1. 贝西的国王标记为 K
1. 正在移动的国王标记为 >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"。
题目描述
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:
```cpp
- + - + - + - + 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.
输入输出样例
输入样例 #1
8
-+-+-+-+
+-+-+-+-
-+-K-+-+
+-+-+-+-
-o-o-+-+
+-K-+-+-
-o-+-+-+
+-K-+-K-
输出样例 #1
8 3
6 1
4 3
6 5