下山

Time Limit: 1000 MS Memory Limit: 65536 K

Total Submit: 271(111 users) Total Accepted: 129(101 users) Rating: Special Judge: No

Description

下面的矩阵可以想象成鸟瞰一座山，矩阵内的数据可以想象成山的高度。

可以从任意一点开始下山。每一步的都可以朝“上下左右”4个方向行走，前提是下一步所在的点比当前所在点的数值小。

例如处在18这个点上，可以向上、向左移动，而不能向右、向下移动。

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-24-23-22-21-20-19-18-17-16-15-14-13-12-11-10-9-8-7-6-5-4-3-2-1，应输出结果25。

Input

输入包括多组测试用例。

对于每个用例，第一行包含两个正整数R和C分别代表矩阵的行数和列数。(1 <= R,C <= 100)

从第二行开始是一个R行C列矩阵，每点的数值在[0,10000]内。

Output

输出最长的下山路径的长度。

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

Hint

深度优先搜索

Author

卢俊达

---

 

　　DFS深搜，入门题。

　　深搜入门题，注意剪枝，不然会超时。

　　代码：

1 #include 
     
       2 #include 
      
        3 int Max,r,c; 4 int a[110][110]; 5 int st[110][110]; 6 int dx[4] = {
    0,1,0,-1}; 7 int dy[4] = {
    1,0,-1,0}; 8 bool judge(int x,int y,int h) 9 {10     if(x<1 || x>r || y<1 || y>c)    //越界11         return true;12     if(a[x][y]>=h)    //如果下一步的山比当前这一步的要高，则不能走13         return true;14     return false;15 }16 void dfs(int x,int y,int s)17 {18     int i;19     if(s>Max)    Max = s;20     for(i=0;i<4;i++){    //遍历四个方向21         int nx = x + dx[i];22         int ny = y + dy[i];23         if(judge(nx,ny,a[x][y]))24             continue;25         if(s+1 > st[nx][ny])    //剪枝，如果走这一步没有之前存储的走的路径长，则不能走这一步26             st[nx][ny] = s+1;27         else 28             continue;29         dfs(nx,ny,s+1);30     }31 }32 int main()33 {34     int i,j;35     while(scanf("%d%d",&r,&c)!=EOF){36         memset(st,0,sizeof(st));37         Max = 0;38         for(i=1;i<=r;i++)    //输入39             for(j=1;j<=c;j++)40                 scanf("%d",&a[i][j]);41         for(i=1;i<=r;i++)    //遍历42             for(j=1;j<=c;j++)43                 dfs(i,j,1);44         printf("%d\n",Max);45     }46     return 0;47 }
      
     

 

Freecode :