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

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

小 R 正在玩一款赛车游戏。 这款赛车游戏的地图可以被描述为一个 $n\times m$ 的字符网格，其中网格的每一个字符都是 `01#` 三个字符中的一个。每种字符的意义如下： - `0`：公路，经过这个字符不会产生任何代价。 - `1`：草地，经过这个字符会扣除车的 $1$ 格耐久，具体见下文。 - `#`：障碍，经过这个字符会使你输掉游戏。 现在小 R 在 $(x_0,y_0)$ 的地方开始了游戏。他需要依次到达 $k$ 个检查点 $(x_1,y_1),(x_2,y_2),\cdots,(x_k,y_k)$。到达 $(x_k,y_k)$ 时游戏结束。 小 R 使用的是游戏内最新款的赛车。这款赛车有一个神奇的特性：**它至多只能转向 $t$ 次**。 初始时，小 R 的车有 $10^9$ 格耐久。现在小 R 想在依次到达所有检查点且不输掉游戏的情况下最大化车的耐久。当然，小 R 可能无法完成游戏，此时你只需输出 `-1`。 注意，如果经过了同一格草地多次，那么耐久仍然会被扣除多次。

第一行四个整数 $n,m,k,t$。 接下来 $n$ 行，每行 $m$ 个字符描述棋盘。 接下来一行两个整数 $x_0,y_0$。 接下来 $k$ 行，第 $i$ 行两个整数 $x_i,y_i$。

一行一个整数，表示游戏结束时车的耐久的最大值。无解输出 `-1`。

**【样例 #1 解释】** 显然完成这个地图至少需要 $2$ 次转向，但是小 R 的车最多只能转向 $1$ 次，故不可能。 **【样例 2 解释】**  如图是一种需要 $2$ 次转向的最优解。其中： - 绿色 S：表示起点 - 橙色数字：表示检查点 - 白色数字：表示经过的草地。 **【样例 3 解释】**  如图是一种需要 $1$ 次转向的最优解。图示和上一个解释相同。 注意，如果经过了同一格草地多次，那么耐久仍然会被扣除多次。 **【样例 4 解释】**  如图是一种需要 $7$ 次转向的最优解。图示和前面两个的样例解释相同。 **【数据范围】** 对于所有测试数据，保证：$1\le n,m \le 50,0\le t \le 100, 1\le k \le 10$,$(x_i,y_i)\neq(x_{i+1},y_{i+1})$。 所有检查点都不是 `#`，保证 $(x_0,y_0)$ 为 `0`。 | 子任务编号 | $n,m\le$ | $t\le$ |特殊性质 |分值 | |:-:|:-:|:-:|:-:|:-:| | 1 | $5$ | $10$ |无 | $10$ | | 2 | $20$ | $50$ | 无 | $15$ | | 3 | ^ | ^ | 除 $(x_0,y_0)$ 外，网格全为字符 `1` | $5$ | | 4 | ^ | ^ | 网格全为字符 `0` | $5$ | | 5 | ^ | ^ | 网格没有字符 `#` | $10$ | | 6 | $50$ | $100$ | $n=1$ | $10$ | | 7 | ^ | ^ | $k=1$ | $15$ | | 8 | ^ | $0$ | 无 | $5$ | | 9 | ^ | $100$ | 无 | $25$ |