P2923 [USACO08DEC]赢得跳棋Winning Checkers

• 4通过
• 77提交
• 题目提供者 FarmerJohn2
• 评测方式 云端评测
• 标签 动态规划,动规,dp 队列 USACO 2008 高性能
• 难度 提高+/省选-
• 时空限制 1000ms / 128MB
• 提示：收藏到任务计划后，可在首页查看。

题目描述

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

奶牛们在疯狂地玩着西洋跳棋，但是非常不幸，不管他们多么享受，他们还是在最后阶段遇 到了可怕的麻烦，他们需要你的帮助.

有一个N x N(4 < W < 500)跳棋棋盘，请确定最佳的结束比赛步骤.跳棋子仅仅能够在标记 有“ + ”的格子里停留，通过“飞跃”俘获对方的棋子.刚刚跳过的格子将被立即封锁.请看下面 的例子：

这是一张边长为8的棋盘图.“K”代表贝茜的王；“0”代表对手的棋子.王需要斜着连续的 跳过对的棋子，跳过的格子将会被封锁.对于这个情况，获胜的方案需要最下面、最左边的王 连续的跳过三个对方的棋子（如下图所示），游戏因此结束.

请写一个程序，给出输入的棋盘的结束游戏步骤（存在时，是唯一的）.至少有一个王和一 个对手棋子在棋盘上.

无解的时候应当输出impossible

输入输出格式

输入格式：

* 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

提示
标程仅供做题后或实在无思路时参考。
请自觉、自律地使用该功能并请对自己的学习负责。
如果发现恶意抄袭标程，将按照I类违反进行处理。