スキー(dp+深捜し)

Problem 35:スキー
Time Limit:1 Ms| 
Memory Limit:128 MB
Difficulty:3
Description
trsはスキーが好きです.彼は矩形のスキー場に来た.このスキー場は簡単にするために、r行c列の行列で各地形を表した.より速い速度を得るためには、滑走路を下に傾けなければならない.
例えば、サンプルの矩形は、ある点から上下左右の4つの隣接する点の1つにスライドすることができる.例えば24-17-16-1で、実は25-24-23...3-2-1がもっと長く、実際にはこれが一番長いです.
Input
1行目:2つの数字r,c(1<=r,c<=100)は、行列の行列を表す.
2.r+1行:各行c個数で、この行列を表す.
Output
1行のみ:1つの整数を出力し、スライド可能な最大長を表します.
Sample Input
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
Sample Output
25
考え方:記憶化検索(今日知ったばかりでこれは記憶化検索と呼ばれています)は、深く検索しますが、検索したものを
結果を保存すると、次の深さ検索時に直接呼び出すことができます(最適化された再帰的なフィボナ粘り数列を求める)、2つの2次元数を使用します.
len[x][y],hight[x][y]はそれぞれx,yが滑ることができる最も遠いステップ数と各点の高さを表し,再帰で動帰を実現する
小さい頃から大きいまで値を求める.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 100
 
int n, m, len[MAX][MAX], hight[MAX][MAX], dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
 
int dfs(int x, int y)
{
     
    if(len[x][y] != 0)
    {
        return len[x][y];
    }
    int max = 0, t, tx, ty;                //        （x，y）       max  0
    for(int i = 0; i < 4; i++)             //           
	{
        tx = x + dir[i][0];
        ty = y + dir[i][1];
        if(tx >= 0 && tx < n && ty >= 0 && ty < m && hight[tx][ty] < hight[x][y])
        {
            t = dfs(tx, ty);               //          
            if(t > max)    
            {
                max = t;                    //      
            }
        }
    }
    len[x][y] = max + 1;                    //       max+1
    return max + 1;                         //        ，     
}
 
int main()
{
    int i, j, maxx;
    while(scanf("%d%d", &n, &m) != EOF)
    {
        memset(len, 0, sizeof(len));         //    
        for(i = 0; i < n; i++)
        {
            for(j = 0; j < m; j++)
            {
                scanf("%d", &hight[i][j]);
            }
        }
        maxx = 0;
        for(i = 0; i < n; i++)               //          
        {
            for(j = 0; j < m; j++)
            {
                len[i][j] = dfs(i, j);       //      
                if(len[i][j] > maxx)
                {
                    maxx = len[i][j];
                }
            }
        }
        printf("%d
", maxx);                //      
    } 
     
    return 0;
}