資源限制
時間限制：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,
解題方法：
本題問的是最少的步數，在滿足到（n,n）位置血量大于0的情況下，步數就是2*（n-1），步數最少就是：不是向左走就是向下走，不回頭即可，
利用max函式，每一步都保證了在到達（i，j）位置時，血量都是最大的，即可以理解為走了耗血量最少的路徑，
例如上圖blood（2,2）=5，說明從（1,1）的位置是向右走的，而不是向下走的，
詳細見程式注釋，
源程式：
#include<iostream>
#include<string>
#include<algorithm>//max函式的頭檔案
using namespace std;
#define maxsize 100
int chessboard[maxsize][maxsize];//棋盤，其中存盤著對應位置的耗血量
int blood[maxsize][maxsize];//在某位置時的剩余血量
void init(int m)//初始化棋盤
{
//memset(chessboard, 0, sizeof(chessboard));注釋不注釋都可以
//memset(blood, 0, sizeof(blood));
int x, y, p;
for (int i = 0; i < m; i++)//耗血量及對應的位置
{
cin >> x >> y >> p;
chessboard[x][y] = p;
}
}
bool judge(int n, int m, int c)//判斷在n，n位置的血量
{
int x, y;
blood[1][1] = c - chessboard[1][1];//初始血量
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
//向下走：
//從（i-1,j）的位置走到(i,j)的位置
x = i - 1;
y = j;
if ((x >= 1 && x <= n) && (y >= 1 && y <= n) && blood[x][y] - chessboard[i][j] > 0)
blood[i][j] = max(blood[i][j], blood[x][y] - chessboard[i][j]);//獲取最大血量值（即最優解路線）
//向右走：
//從（i,j-1）的位置走到(i,j)的位置
x = i;
y = j - 1;
if ((x >= 1 && x <= n) && (y >= 1 && y <= n) && blood[x][y] - chessboard[i][j] > 0)
blood[i][j] = max(blood[i][j], blood[x][y] - chessboard[i][j]);
}
}
if (blood[n][n] > 0)
return true;
else
return false;
}
int main()
{
int n, m, c;
cin >> n >> m >> c;
init(m);
if (judge(n, m, c))
cout << 2 * n - 2 << endl;
else
cout << "No" << endl;
}
評測結果：
補充：
這道題目相比于第十屆藍橋杯B組的第五題：迷宮問題，簡單一些，只需考慮最后位置時的血量，不用關心中間路程它是怎么走的，不用給出相應的路徑，下面給出迷宮問題：
轉載于：藍橋杯官網
后面我會給出迷宮問題的程式，感興趣可以了解下，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/254477.html
標籤：其他