ACM国际大学生程序设计竞赛，亚洲-Amritapuri站，2011年 问题A：MAGRID
非常感谢您在十月份帮助哈利波特找到不朽的魔法石。我们没有告诉你那只是一个在线游戏吗？现在这里是真正的任务。你有一个magrid S（一个魔法网格），它有R行和C列。此magrid中的每个单元格都有匈牙利角蜥蜴，我们勇敢的英雄必须打败它，或者是他的老师斯内普留给他的一瓶魔法药水。单元格（i，j）处的龙会从哈利身上取走|S [i] [j]|的力量点数，而单元格（i，j）处的药水会增加哈利的力量S [i] [j]。如果哈利在旅途中的任何时刻力量降至0或更低，他就会死亡，没有魔法石可以使他复活。
哈利从左上角单元格（1,1）开始，而魔法石位于右下角单元格（R，C）。从单元格（i，j）开始，哈利只能向下或向右移动一个单元格，即到达单元格（i + 1，j）或单元格（i，j + 1），他不能移动到 magrid之外。哈利在开始旅程之前使用魔法确定了哪个单元格包含什么，但缺乏基本的简单数学技能来确定他需要从哪里开始具有收集魔法石的最小强度。请再次帮助他。
输入（STDIN）：
第一行包含测试用例T的数量。 T个测试用例。 每个测试用例都由第一行中的R C组成，后跟描述R行的网格， 每行包含C个整数。从上到下，行编号为1到R，从左到右，列编号为1到C。 S [i] [j]＜0的单元格包含龙，其他单元格包含魔法药水。
输出（STDOUT）：
输出T行，每个案例一个，包含哈利应该从单元格（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;
}
请帮助我进一步优化它，因为我知道我实现的方法需要最长时间。