Java实现 蓝桥杯VIP 算法训练 步与血(递推 || DFS)
2023-09-14 08:58:01 时间
试题 算法训练 步与血
问题描述
有n*n的方格,其中有m个障碍,第i个障碍会消耗你p[i]点血。初始你有C点血,你需要从(1,1)到(n,n),并保证血量大于0,求最小步数。
输入格式
第一行3个整数n,m,c,表示棋盘大小、障碍数量和你的血量
接下来m行,每行描述一个障碍。包含三个整数x y p,分别表示障碍在第x行第y列,消耗血量为p。
输出格式
如果可以到输出步数,如果不可以,输出"No"。
样例输入
10 10 10
2 8 35
1 10 25
9 9 63
5 6 46
2 6 43
8 7 92
5 3 54
3 3 22
7 9 96
9 10 13
样例输出
18
数据规模和约定
输入数据中每一个数的范围。
0<n,m<100,
正常来说应该是一个DFS,四个方向搜索,但是太慢了
,用递推,空间换时间
最小步数可以当作,一个只向右下走的路程
import java.util.Scanner;
public class Main {
//https://blog.csdn.net/a1439775520/article/details/90746562 欢迎进入讨论群
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int c = sc.nextInt();
int[][] map = new int[n + 1][n + 1];
int[][] dp = new int[n + 1][n + 1];
for (int i = 0; i < m; i++) {
int x = sc.nextInt();
int y = sc.nextInt();
int p = sc.nextInt();
map[x][y] = p;
}
sc.close();
dp[1][1] = c - map[1][1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int x = i - 1, y = j;
if (x < 1 || y < 1 || x > n || y > n || dp[x][y] - map[i][j] <= 0) {
} else {
dp[i][j] = Math.max(dp[i][j], dp[x][y] - map[i][j]);
}
x = i;
y = j - 1;
if (x < 1 || y < 1 || x > n || y > n || dp[x][y] - map[i][j] <= 0) {
} else {
dp[i][j] = Math.max(dp[i][j], dp[x][y] - map[i][j]);
}
}
}
if (dp[n][n] == 0) {
System.out.println("No");
} else {
System.out.println(2 * (n - 1));
}
}
}
相关文章
- java volatile关键字的作用_Java并发编程彻底搞懂volatile关键字「建议收藏」
- java转换字符串为时间_JAVA字符串转日期或日期转字符串
- DOS下第一个Java程序–HelloWorld[通俗易懂]
- java启动器_JAVA基础:Java 启动器如何查找类
- Java基础知识总结(超详细整理),java从入门到精通pdf「建议收藏」
- MySQL字段类型如何转为java_Java JDBC中,MySQL字段类型到JAVA类型的转换
- java uuid 随机数_Java随机数和UUID[通俗易懂]
- java中random方法取值范围_Java Random.nextInt()方法,随机产生某个范围内的整数
- java 阶乘算法_Java 实现阶乘算法
- Java的定时器_JAVA定时任务
- native2ascii java_Native2Ascii和Ascii2Native的Java实现
- java stack deque_java如何实现栈
- 二面蚂蚁金服(交叉面),已拿offer,Java岗定级阿里P6
- Java Number & Math 类
- 【愚公系列】2023年03月 Java教学课程 116-Mybatis(动态代理和动态SQL)
- 【ES三周年】Java与Elasticsearch实战:GPT助您实现数据安全和监控
- 唯品会三年,我只做了5件事,如今跳槽天猫拿下offer(Java岗)
- JAVA单例MongoDB工具类详解编程语言
- Java学习笔记之五java数组详解编程语言
- 机制Java实现Redis过期机制(redisjava过期)
- 数据库Java查询Oracle数据库:一种快捷、可靠的解决方案(java查询oracle)
- Java开发者如何快速掌握Neo4j(java操作neo4j)
- 简明易懂的介绍Linux java包的25个字的文章标题:Linux Java包:开发和运行Java程序的工具(Linuxjava包)
- 在Linux上实现Java程序的运行(linux运行java程序)
- Java编程与Oracle技术创造技术价值的奥秘(java编程oracle)
- java/jsp中中文问题详解
- java对象转换String类型的三种方法