UVa 10285-Longest Run on a Snowboard(メモリ検索)

昨日ブログの目録を整理して、紫書の第九章のまだしていない問題を見て、本をめくってこの水の問題を見ました.
r*cの数表を与えて各場所の高さを代表して、スキーをする時高度は厳格に下げて、最長のスキーの経路を求めます.
最長経路を記憶化して探索し、各点の最長経路を配列gに存在させ、1点を計算して最長経路を維持すればよい.

#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
const int maxn=110;
const int x[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int h[maxn][maxn],g[maxn][maxn];
int dp(int a,int b){
    if(g[a][b]>=0) return g[a][b];//         。
    bool flag=0;
    for(int i=0;i<4;++i)
        if(h[a][b]>h[a+x[i][0]][b+x[i][1]]&&h[a+x[i][0]][b+x[i][1]]!=-1){
            g[a][b]=max(dp(a+x[i][0],b+x[i][1])+1,g[a][b]);//           。
            flag=1;
        }
    if(!flag) return 0;//           0。
    return g[a][b];
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        memset(h,-1,sizeof(h));
        memset(g,-1,sizeof(g));
        char s[maxn];
        int r,c,best=0;
        scanf("%s%d%d",s,&r,&c);
        for(int i=1;i<=r;++i)
            for(int j=1;j<=c;++j)
                scanf("%d",&h[i][j]);
        for(int i=1;i<=r;++i)
            for(int j=1;j<=c;++j)
                best=max(dp(i,j),best);//          ，      。
        printf("%s: %d
",s,best+1);
    }
    return 0;
}