skiing
时间限制：3000 ms | 内存限制：65535 KB
难度：5
描述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更长。事实上，这是最长的一条。
输入
第一行表示有几组测试数据，输入的第二行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。
后面是下一组数据；
输出
输出最长区域的长度。
样例输入
1
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
样例输出
-
25
思路：用一个二维矩阵gaodu[][]来存储输入进来的数据，用一个一维数组shunxu[]来将gaodu矩阵里的数据进行带横纵坐标的排序，一维数组可以使用一个自己定义的结构体类型。用另外一个二维数组lujing[][]来进行记录gaodu数组对应点上可以滑行的最长距离。对gaodu数组中的数据都排完顺序之后，选择最小的一个在gaodu数组中进行四周的比对。gaodu[i][j]与四周：上gaodu[i-1][j]，下gaodu[i+1][j]，左gaodu[i][j-1]，右gaodu[i][j+1]进行比较，上下左右某一点如果>gaodu[i][j]，则可走。最初初始化lujing[][]的矩阵的时候，lujing[][]所有元素都为0，当且仅当（上下左右某点x点>gaodu[i][j]&&lujing[i][j]+1>x点对应lujing上记录的值得时候）,将lujing上的点更新。依次遍历所有shunxu中的值，将lujing的矩阵填数完毕，再获得lujing矩阵的最大值，也就得到了题目要求的路径的最大长度。AC代码如下：
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<algorithm> #include<cmath> #include<iostream> using namespace std; int gaodu[105][105]; int lujing[105][105]; int fangxiang[4][2]={{1,0}, {-1,0}, {0,1}, {0,-1}}; static int MAX_NUM=10005; struct sz { int x; int y; int z; } shunxu[MAX_NUM]; int cmp(sz a,sz b) { if(a.z<b.z) return 1; else return 0; } int main() { int n; scanf("%d",&n); while(n--) { memset(gaodu,0,sizeof(gaodu)); memset(lujing,0,sizeof(lujing)); for(int i=0;i<MAX_NUM;i++) { shunxu[i].x=0; shunxu[i].y=0; shunxu[i].z=0; } int r,c; scanf("%d%d",&r,&c); for(int i=0;i<r;i++) { for(int j=0;j<c;j++) { scanf("%d",&gaodu[i][j]); shunxu[i*r+j].z=gaodu[i][j]; shunxu[i*r+j].x=i; shunxu[i*r+j].y=j; } } sort(shunxu,shunxu+r*c,cmp); for(int i=0;i<r*c;i++) { int zhongx=shunxu[i].x; int zhongy=shunxu[i].y; for(int j=0;j<4;j++) { int xx=zhongx+fangxiang[j][0]; int yy=zhongy+fangxiang[j][1]; if(gaodu[xx][yy]>shunxu[i].z&&(lujing[zhongx][zhongy]+1)>lujing[xx][yy]) lujing[xx][yy]=lujing[zhongx][zhongy]+1; } } int max=0; for(int i=0;i<r;i++) { for(int j=0;j<c;j++) { if(lujing[i][j]>max) max=lujing[i][j]; } } printf("%d ",max+1); } system("pause"); return 0; }2014-05-04 14:07:45