| 题目名称 | 1597. [USACO Dec08] 跳棋获胜 |
|---|---|
| 输入输出 | winchk.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 15 |
| 题目来源 |
 cqw
于2014-04-16加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：4， 提交：7， 通过率：57.14% | ||||
 cstdio |
100 | 0.064 s | 4.93 MiB | C++ |
|
mildark |
100 | 0.065 s | 4.93 MiB | C++ |
 ww944606393 |
100 | 0.158 s | 7.83 MiB | C++ |
 Wang Yen Jen |
100 | 0.174 s | 7.87 MiB | C++ |
|
cstdio |
46 | 0.047 s | 1.11 MiB | C++ |
|
mildark |
7 | 0.046 s | 3.37 MiB | C++ |
|
mildark |
0 | 0.096 s | 4.60 MiB | C++ |
| 关于 跳棋获胜 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
1：这货需要spj，所以我写了个spj，并且用USACO的标程造了.ans（从USACO扒下来的数据只有三个.ans，其中不包括第一个样例点）
2：第五个点，标程返回impossible，但手测有解。用spj检查我的程序输出的解，结果正确。（当然spj有可能写戳，手测也有可能测戳，不过看上去那组数据像是手动构造的有解） 3：所以我把spj关于impossible的部分取消了，现在的spj默认所有都有解，无法检查无解的情况 4：用这个默认有解的spj检查我程序的输出，十个点都过了 总之就是这破事不管了 (╯‘□′)╯（┻━┻ | ||||
奶牛们开始狂热地喜欢上了跳棋。不幸的是，尽管他们无限享受下棋过程，但他们讨厌思考如何终结棋局，希望得到你的帮助。
给一个NxN (4 <= N <= 500)的棋盘，决定最佳的移动方案（例如：最小的移动步数）来结束游戏。传统的方式，跳棋只能在'+'位置移动，通过跳过对手棋子将对手棋子捕获。当跳的时候，位置也相应移动，如下是一个N=8的情况：
- + - + - + - +
+ - + - + - + -
- + - K - + - +
+ - + - + - + -
- o - o - + - +
+ - K - + - + -
- o - + - + - +
+ - K - + - K -
K是贝茜的国王，o是对手的棋子。贝茜的国王可以成功的通过一些斜线的移动来捕获对手的棋子（跳跃的同时移动位置）
对于这个对局，最好的结果是左下边的K通过三次跳跃结束游戏（移动的 K 标记为 >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 -
移动穿越这些方格:
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 -
对于一个NxN的输入写一个程序决定如何结束游戏，当然如果方案存在原话。至少有一个国王和一个对手的棋子。最佳结论是国王通过每次跳跃进行移动。
输入格式:
* 第1行: 一个单独的整数: N
* 第2..N+1行: 行i+1 包含N个字符 (each one of: '-', '+', 'K', or 'o') 表示一个完整棋盘的第i行. 行2总是由'-'开始.
winchk.in
8
-+-+-+-+
+-+-+-+-
-+-K-+-+
+-+-+-+-
-o-o-+-+
+-K-+-+-
-o-+-+-+
+-K-+-K-
输出格式:
* 第1..?行: 如果没能获胜方案，输出"impossible".如果方案存在，每行包括两个用空格隔开的整数表示国王的移动路线，这个方案必须是可行的获胜方案。
winchk.out
8 3
6 1
4 3
6 5