33OJ
登录 注册

#P17755. 「RSOI-3D」赛车游戏 / racing

「RSOI-3D」赛车游戏 / racing

背景

题目来源:【HT-126-Div.3】核桃 CSP-J 组模拟赛

题目描述

小 R 正在玩一款赛车游戏。

这款赛车游戏的地图可以被描述为一个 n×mn\times m 的字符网格,其中网格的每一个字符都是 01# 三个字符中的一个。每种字符的意义如下:

  • 0:公路,经过这个字符不会产生任何代价。
  • 1:草地,经过这个字符会扣除车的 11 格耐久,具体见下文。
  • #:障碍,经过这个字符会使你输掉游戏。

现在小 R 在 (x0,y0)(x_0,y_0) 的地方开始了游戏。他需要依次到达 kk 个检查点 (x1,y1),(x2,y2),⋯ ,(xk,yk)(x_1,y_1),(x_2,y_2),\cdots,(x_k,y_k)。到达 (xk,yk)(x_k,y_k) 时游戏结束。

小 R 使用的是游戏内最新款的赛车。这款赛车有一个神奇的特性:它至多只能转向 tt 次。

初始时,小 R 的车有 10910^9 格耐久。现在小 R 想在依次到达所有检查点且不输掉游戏的情况下最大化车的耐久。当然,小 R 可能无法完成游戏,此时你只需输出 -1。

注意,如果经过了同一格草地多次,那么耐久仍然会被扣除多次。

输入格式

第一行四个整数 n,m,k,tn,m,k,t。

接下来 nn 行,每行 mm 个字符描述棋盘。

接下来一行两个整数 x0,y0x_0,y_0。

接下来 kk 行,第 ii 行两个整数 xi,yix_i,y_i。

输出格式

一行一个整数,表示游戏结束时车的耐久的最大值。无解输出 -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 解释】

显然完成这个地图至少需要 22 次转向,但是小 R 的车最多只能转向 11 次,故不可能。

【样例 2 解释】

如图是一种需要 22 次转向的最优解。其中:

  • 绿色 S:表示起点
  • 橙色数字:表示检查点
  • 白色数字:表示经过的草地。

【样例 3 解释】

如图是一种需要 11 次转向的最优解。图示和上一个解释相同。

注意,如果经过了同一格草地多次,那么耐久仍然会被扣除多次。

【样例 4 解释】

如图是一种需要 77 次转向的最优解。图示和前面两个的样例解释相同。

【数据范围】

对于所有测试数据,保证:1≤n,m≤50,0≤t≤100,1≤k≤101\le n,m \le 50,0\le t \le 100, 1\le k \le 10,(xi,yi)≠(xi+1,yi+1)(x_i,y_i)\neq(x_{i+1},y_{i+1})。

所有检查点都不是 #,保证 (x0,y0)(x_0,y_0) 为 0。

子任务编号 n,m≤n,m\le t≤t\le 特殊性质 分值
1 55 1010 无 1010
2 2020 5050 1515
3 ^ 除 (x0,y0)(x_0,y_0) 外,网格全为字符 1 55
4 网格全为字符 0
5 网格没有字符 # 1010
6 5050 100100 n=1n=1
7 ^ ^ k=1k=1 1515
8 00 无 55
9 100100 2525