试题 算法训练 步与血
蓝桥杯试题解答汇总链接
资源限制
时间限制：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];
int blood
[101][101];
}step
;
int main() {
int n
, m
, c
, x
, y
, p
, i
, j
;
scanf("%d%d%d",&n
,&m
,&c
);
int chess
[101][101] = {0};
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;
dp
.blood
[1][i
] = dp
.blood
[1][i
-1]-chess
[1][i
];
if(dp
.blood
[1][i
] <= 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
) {
for(j
= 2;j
<= n
; ++j
) {
if(dp
.co
[i
-1][j
]>0 && dp
.co
[i
][j
-1]>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) {
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;
}
