ACM 国際大学プログラミング コンテスト、アジア アムリタプリ サイト、2011 年問題 A: MAGRID
10 月にハリー・ポッターが賢者の不死の石を見つけるのを手伝ってくれて、どうもありがとう。ただのオンラインゲームだって言ってなかったっけ？うーん！ここからは、Harry の実際のオンサイト タスクです。R 行と C 列を持つ magrid S (マジック グリッド) が与えられます。この magrid の各セルには、勇敢なヒーローが倒さなければならないハンガリアン ホーンテイル ドラゴンか、先生のスネイプが彼に残した魔法のポーションのフラスコが入っています。セル (i,j) のドラゴンは |S[i][j]| を奪います。強さは彼からポイントされ、セル (i,j) のポーションはハリーの強さを S[i][j] 増加させます。旅の途中で体力が0以下になった場合、ハリーは死亡し、魔法の石で蘇生することはできません。
ハリーは左上隅のセル (1,1) から開始し、魔術師の石は右下隅のセル (R, C) にあります。セル (i,j) から、ハリーはセル (i+1,j) またはセル (i,j+1) に 1 つ下または右にしか移動できず、マグリッドの外に移動することはできません。ハリーは旅を始める前に魔法を使って、どのセルに何が入っているかを判断しましたが、魔術師の石を集めるために必要な最小の力を判断するための基本的な単純な数学のスキルがありません. もう一度彼を助けてください。
入力 (STDIN):
最初の行には、テスト ケース T の数が含まれます。T ケースが続きます。各テスト ケースは、最初の行の RC とそれに続く R 行のグリッドの説明で構成され、それぞれに C の整数が含まれます。行には上から下に 1 から R までの番号が付けられ、列には左から右に 1 から C までの番号が付けられます。S[i][j] < 0 のセルにはドラゴンが含まれ、その他のセルには魔法のポーションが含まれます。
出力 (STDOUT):
出力 T 行。ハリーがセル (1,1) から始めて、セル (R,C) までの旅を通して正の強さを持つ必要がある最小の強さを含むケースごとに 1 行。
制約:
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 : セル (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;
}
私が実装した方法は最悪の時間がかかることを知っているので、さらに最適化するのを手伝ってください