#P17755. 「RSOI-3D」赛车游戏 / racing
「RSOI-3D」赛车游戏 / racing
背景
题目来源:【HT-126-Div.3】核桃 CSP-J 组模拟赛
题目描述
小 R 正在玩一款赛车游戏。
这款赛车游戏的地图可以被描述为一个 的字符网格,其中网格的每一个字符都是 01# 三个字符中的一个。每种字符的意义如下:
0:公路,经过这个字符不会产生任何代价。1:草地,经过这个字符会扣除车的 格耐久,具体见下文。#:障碍,经过这个字符会使你输掉游戏。
现在小 R 在 的地方开始了游戏。他需要依次到达 个检查点 。到达 时游戏结束。
小 R 使用的是游戏内最新款的赛车。这款赛车有一个神奇的特性:它至多只能转向 次。
初始时,小 R 的车有 格耐久。现在小 R 想在依次到达所有检查点且不输掉游戏的情况下最大化车的耐久。当然,小 R 可能无法完成游戏,此时你只需输出 -1。
注意,如果经过了同一格草地多次,那么耐久仍然会被扣除多次。
输入格式
第一行四个整数 。
接下来 行,每行 个字符描述棋盘。
接下来一行两个整数 。
接下来 行,第 行两个整数 。
输出格式
一行一个整数,表示游戏结束时车的耐久的最大值。无解输出 -1。
3 3 3 1
000
1#1
010
1 1
1 3
3 3
3 1
-1
3 3 3 10
000
1#1
010
1 1
1 3
3 3
3 1
999999998
4 4 1 10
0#00
##00
0000
0000
1 1
4 4
-1
4 4 2 1
0001
0#01
1#01
1110
4 4
4 1
4 4
999999995
4 4 2 7
0001
0#01
0#01
1110
4 4
4 1
4 4
999999997
提示
【样例 #1 解释】
显然完成这个地图至少需要 次转向,但是小 R 的车最多只能转向 次,故不可能。
【样例 2 解释】

如图是一种需要 次转向的最优解。其中:
- 绿色 S:表示起点
- 橙色数字:表示检查点
- 白色数字:表示经过的草地。
【样例 3 解释】

如图是一种需要 次转向的最优解。图示和上一个解释相同。
注意,如果经过了同一格草地多次,那么耐久仍然会被扣除多次。
【样例 4 解释】

如图是一种需要 次转向的最优解。图示和前面两个的样例解释相同。
【数据范围】
对于所有测试数据,保证:,。
所有检查点都不是 #,保证 为 0。
| 子任务编号 | 特殊性质 | 分值 | ||
|---|---|---|---|---|
| 1 | 无 | |||
| 2 | ||||
| 3 | ^ | 除 外,网格全为字符 1 |
||
| 4 | 网格全为字符 0 |
|||
| 5 | 网格没有字符 # |
|||
| 6 | ||||
| 7 | ^ | ^ | ||
| 8 | 无 | |||
| 9 | ||||