Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
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
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。
DP[i][j] = Max{ DP[i-1][j], DP[i+1][j], DP[i][j-1], DP[i][j+1] } + 1;

include <iostream>

using namespace std;

include <string>

define x_max 5

define y_max 5

/*
int map[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 };

            */

int map[5][5] = { 1, 2, 3, 4, 5,
1, 17, 5, 1, 6,
15, 1, 25, 20, 7,
14, 23, 22, 1, 8,
13, 1, 1, 1, 9 };

int path[25] = { -1 };
typedef struct _heigh
{
int x;
int y;
int h;
}heigh;
int mysort(const void* tmp1, const void* tmp2)
{
return ((heigh)tmp1)->h - ((heigh)tmp2)->h;
}
int mysort2(const void* tmp1, const void* tmp2)
{
return ((int)tmp1) - ((int)tmp2);
}
int DP(int x,int y,int num)
{
int tmp[4] = { 0 };
if (path[num] > 0)
return path[num];
//up
if (x - 1 >= 0 && map[x - 1][y] < map[x][y])
{
tmp[0] += (DP(x - 1, y, num) + 1);
}

//down
if (x + 1 < x_max&& map[x + 1][y] < map[x][y])
{
    tmp[1] += (DP(x + 1, y, num) + 1);
}
    
//left
if (y - 1 >= 0 && map[x][y - 1] < map[x][y])
{
    tmp[2] += (DP(x, y - 1, num) + 1);
}
    
//right
if (y + 1 < y_max&& map[x][y + 1] < map[x][y])
{
    tmp[3] += (DP(x, y + 1, num) + 1);
}
qsort(tmp, 4, sizeof(tmp[0]), mysort2);
if (tmp[3] == 0)
    return tmp[3] + 1;
return tmp[3];

}

int main()
{
heigh* heighArray = (heigh )malloc(sizeof(heigh)25);
memset(heighArray, 0, sizeof(heighArray));
int tmp = 0;
for (int i = 0; i < x_max; i++)
{
for (int j = 0; j < y_max; j++)
{
heighArray[tmp].x = i;
heighArray[tmp].y = j;
heighArray[tmp].h = map[i][j];
tmp++;
}
}
qsort(heighArray, x_maxy_max, sizeof(heigh), mysort);
for (int i = 0; i < 25; i++)
{
cout << "从高度" << heighArray[i].h << "开始 \t(" << heighArray[i].x <<"," << heighArray[i].y << ")....";
path[i] = DP(heighArray[i].x, heighArray[i].y,i);
cout << path[i] << endl;
}
/
for (int i = 0; i < 25; i++)
{
cout << heighArray[i].h << " ";
}
*/
if (heighArray != NULL)
{
free(heighArray);
heighArray = NULL;
}

system("pause");
return 0;

}