ACM 国际大学编程竞赛，Asia-Amritapuri 站点，2011 年问题 A：MAGRID
非常感谢您在 10 月份帮助哈利波特找到不朽的魔法石。我们不是告诉过你这只是一个网络游戏吗？嗯！现在这是哈利真正的现场任务。您将获得一个具有 R 行和 C 列的 maggrid S（魔法网格）。这个魔格中的每个牢房要么有我们无畏的英雄必须击败的匈牙利马尾龙，要么有他的老师斯内普留给他的一瓶魔法药水。单元格 (i,j) 中的一条龙带走了 |S[i][j]| 他的力量点，并且在细胞 (i,j) 处的药水增加了哈利的力量 S[i][j]。如果在旅途中的任何时候他的力量下降到 0 或更少，哈利就会死去，没有魔法石可以使他复活。
哈利从左上角单元格 (1,1) 开始，魔法石在右下角单元格 (R,C) 中。从一个单元格 (i,j)，Harry 只能向下或向右移动一个单元格，即到单元格 (i+1,j) 或单元格 (i,j+1)，并且他不能移动到磁格之外。哈利在开始他的旅程之前使用了魔法来确定哪个细胞包含什么，但缺乏基本的简单数学技能来确定他开始收集魔法石所需的最小力量。请再次帮助他。
输入（标准输入）：
第一行包含测试用例 T 的数量。接下来是 T 用例。每个测试用例由第一行中的 RC 组成，然后是 R 行中的网格描述，每行包含 C 个整数。行从上到下编号为 1 到 R，列从左到右编号为 1 到 C。S[i][j] < 0 的单元格包含龙，其他包含魔法药水。
输出（标准输出）：
输出 T 行，每个案例一个包含 Harry 应该从单元格 (1,1) 开始的最小强度，以便在他到单元格 (R,C) 的整个旅程中具有正强度。
约束：
1 ≤ T ≤ 30
2 ≤ R, C ≤ 500
-103 ≤ S[i][j] ≤ 103
S[1][1] = S[R][C] = 0
时间限制：3 秒内存限制：64 MB 样本输入：
3
2 3
0 1 -3
1 -2 0
2 2
0 1
2 0
3 4
0 -2 -3 1
-1 4 0 -2
1 -2 -3 0
样本输出：
2
1
2
解释：案例 1：如果 Harry 在单元格 (1,1) 处以强度 = 1 开始，则他无法在任何可能的路径中保持正强度。他最初至少需要力量= 2。案例 2：请注意，从 (1,1) 开始，他至少需要强度 = 1。
我尝试用我的第一种方法来查看所有路径并选择能量最小的路径
#include<iostream>
#include<algorithm>
#include<stack>
#include<cmath>
using namespace std;
int TT,R,C,S[500][500];
int energy_g;
//unsigned long int fact(int a);
int trace(int r,int c,int energy,int energy_r);
int main(void)
{
cin>>TT;
for(int i=1;i<=TT;i++)
{
cin>>R>>C;
for(int r=1;r<=R;r++)
for(int c=1;c<=C;c++)
{
cin>>S[r][c];
//cout<<S[r][c];
}
energy_g=32000;
trace(1,1,0,0);
cout<<energy_g<<endl;
}
return 0;
}
int trace(int r,int c,int energy,int energy_r)
{
if(r>R || c>C)
return 0;
energy += S[r][c];
if(energy < 0)
{
energy_r+=abs(energy)+1 ;
energy+=abs(energy)+1;
}
else if(energy == 0){
energy_r +=1;
energy +=1;
}
if(r == R && c == C)
{
if(energy_r < energy_g)
energy_g = energy_r;
return 0;
}
trace(r,c+1,energy,energy_r);
trace(r+1,c,energy,energy_r);
return 0;
}
请帮助我进一步优化它，因为我知道我实施的方法需要最糟糕的时间