A3086 | 神庙大冒险
来源官方 / 2024
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
时间限制:1000ms
空间限制:128mb
Yuilice掉入了一个奇怪的神庙，在这个神庙当中充斥着各种各样的怪物，Yuilice原本还挺怕的，但是看下时间马上要到四点给B班上课了，因此他一下子精神了，准备火速回到柯桥上课。
我们可以把神庙看成是一个$N \times N$的二维矩阵，Yuilice一开始存在着$T$点体力值，他只能进行向右或者向下的移动，并且从行为$S_x$，列为$S_y$的起点出发。在这个矩阵当中，存在着以下几种情况
- 字符
.代表道路，Yuilice每走一格道路就会损失1点体力值。- 字符
M代表怪物，Yuilice因为迫切的想要回到B班上课，因此他可以使用$k$点体力消灭该格的怪物来到该格当中。(假如起点就有怪物，那么怪物就会被Yuilice降落的余波消灭，不需要消耗体力值)- 字符
D代表神奇果实，Yuilice可以来到该格吃下果实，补充$z$点体力，并且每格的果实只能被食用一次。现在已知终点所处坐标为$[N,N]$请你计算出Yuilice回到B班时，他最多还有多少体力值来给B班的同学上课呢？
输入格式
第一行包括六个整数$n,T,k,z,S_x,S_y$，分别代表地图的大小、初始体力值、消灭怪物的体力值、补充体力值、与起点横坐标与纵坐标。
随后$n$行，每行输入$n$个字符，代表神庙的地图。
随后$n$行，每行输入$n$个字符，代表神庙的地图。
输出格式
输出一个整数代表Yuilice到达B班的最多体力值。
输入输出样例
输入 #1
3 3 1 100 1 1 ..M ..M DM.
输出 #1
100
输入 #2
3 3 1 100 1 1 DDD DDD DDD
输出 #2
503
输入 #3
3 3 1 100 1 1 MMM MMM MMM
输出 #3
-1
【样例解释】
第一组样例:
- Yuilice由$[1,1]$来到$[2,1]$ 体力值为:2
- Yuilice由$[2,1]$来到$[3,1]$吃下了神奇果实 体力值为:102
- Yuilice由$[3,1]$来到$[3,2]$消灭了怪物 体力值为:101
- Yuilice由$[3,2]$来到$[3,3]$ 体力值为:100
第二组样例:
- Yuilice从落地开始最多走4步到达终点，总计吃5个果实，最后体力值为503
第三组样例:
- 无论Yuilice如何行走，都要消灭4只怪物，体力值变化为。
- $[1,1] , T = 3$
- $[1,2] , T = 3 - z = 2$
- $[1,3] , T = 2 - z = 1$
- $[2,3] , T = 3 - z = 0$
- $[3,3] , T = 3 - z = -1$
- 最终体力透支为
注: 该路线只是多条相同数值的路线的其中一条。
【数据限制】
对于$50\%$的数据$1 \leq n \leq 15 , 1 \leq T,k,z \leq 10^9 , 1 \leq S_x,S_y \leq n$。
对于$100\%$的数据$1 \leq n \leq 100 , 1 \leq T,k,z \leq 10^9 , 1 \leq S_x,S_y \leq n$。
题目保证$[S_x,S_y] \neq [N,N]$
第一组样例:
- Yuilice由$[1,1]$来到$[2,1]$ 体力值为:2
- Yuilice由$[2,1]$来到$[3,1]$吃下了神奇果实 体力值为:102
- Yuilice由$[3,1]$来到$[3,2]$消灭了怪物 体力值为:101
- Yuilice由$[3,2]$来到$[3,3]$ 体力值为:100
第二组样例:
- Yuilice从落地开始最多走4步到达终点，总计吃5个果实，最后体力值为503
第三组样例:
- 无论Yuilice如何行走，都要消灭4只怪物，体力值变化为。
- $[1,1] , T = 3$
- $[1,2] , T = 3 - z = 2$
- $[1,3] , T = 2 - z = 1$
- $[2,3] , T = 3 - z = 0$
- $[3,3] , T = 3 - z = -1$
- 最终体力透支为
-1注: 该路线只是多条相同数值的路线的其中一条。
【数据限制】
对于$50\%$的数据$1 \leq n \leq 15 , 1 \leq T,k,z \leq 10^9 , 1 \leq S_x,S_y \leq n$。
对于$100\%$的数据$1 \leq n \leq 100 , 1 \leq T,k,z \leq 10^9 , 1 \leq S_x,S_y \leq n$。
题目保证$[S_x,S_y] \neq [N,N]$
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？