P2923 [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 - + - +
+ - + - + - + - + - + - + - + - + ->KKKK
输入格式
第一行有一个整数 $N$。
接下来 $N$ 行是一个 $N \times N$ 的矩阵，每个字符之间没有空格。
输出格式
若有一条路径，输出每行包含两个空格分隔的整数，表示一位国王的连续位置。
若没有这样的路径,则一行输出"impossible"。