试题 算法训练 步与血

                                                                                  蓝桥杯试题解答汇总链接

资源限制

       时间限制：1.0s 内存限制：256.0MB

---

问题描述

       有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,

---

试题解析

步数最小就得每次只能向下或向右走，那么这样就很容易取动态规划了设dp.co[i][j]为走到(i,j)位置需要的步数那么dp.co[i][j]=min(dp.co[i-1][j],dp.co[i][j-1])但其中有障碍所以还需要保存到每个位置的血量>0，否则说明这个点不能走

---

代码

#include <stdio.h>
typedef struct s{int co[101][101];// 走到(i,j)需要的最小步数 int blood[101][101];// 走到(i,j)剩余的血量 
}step;
int main() {// n、m、c、x、y、p对应题意 int n, m, c, x, y, p, i, j;scanf("%d%d%d",&n,&m,&c);int chess[101][101] = {0};// 棋盘chess的值为此处消耗的血量 for(i = 0;i < m; ++i) {scanf("%d%d%d",&x,&y,&p);chess[x][y] = p;}step dp;dp.blood[1][1] = c;// 初始化血量 dp.co[1][1] = 0;// 初始化步数 for(i = 2;i <= n; ++i) {// 初始化第一行第一列 dp.co[1][i] = dp.co[1][i-1]+1;// 从(1,i-1)到(1,i)步数+1 dp.blood[1][i] = dp.blood[1][i-1]-chess[1][i];// 去掉消耗的血量 if(dp.blood[1][i] <= 0) {// 血量不大于0说明这里不能走步数设为0 dp.co[1][i] = 0;}dp.co[i][1] = dp.co[i-1][1]+1;dp.blood[i][1] = dp.blood[i-1][1]-chess[i][1];if(dp.blood[i][1] <= 0) {dp.co[i][1] = 0;}}for(i = 2;i <= n; ++i) {// 从(2,2)开始递推 for(j = 2;j <= n; ++j) {if(dp.co[i-1][j]>0 && dp.co[i][j-1]>0) {// 左边和上边步数不为0说明都能通行 if(dp.co[i-1][j] <= dp.co[i][j-1]) {dp.co[i][j] = dp.co[i-1][j]+1;dp.blood[i][j] = dp.blood[i-1][j]-chess[i][j];if(dp.blood[i][j] <= 0) {dp.co[i][j] = 0;}}else {dp.co[i][j] = dp.co[i][j-1]+1;dp.blood[i][j] = dp.blood[i][j-1]-chess[i][j];if(dp.blood[i][j] <= 0) {dp.co[i][j] = 0;}}}else if(dp.co[i-1][j] == 0) {// 有一个为0取另外一个 dp.co[i][j] = dp.co[i][j-1]+1;dp.blood[i][j] = dp.blood[i][j-1]-chess[i][j];if(dp.blood[i][j] <= 0) {dp.co[i][j] = 0;}}else{dp.co[i][j] = dp.co[i-1][j]+1;dp.blood[i][j] = dp.blood[i-1][j]-chess[i][j];if(dp.blood[i][j] <= 0) {dp.co[i][j] = 0;}}}}if(dp.blood[n][n] > 0) {printf("%d",dp.co[n][n]);}else {printf("No");}return 0;
}