| 下山 | ||||||
| ||||||
| 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 | ||||||
| 卢俊达 |
代码如下：
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int vis[101][101],a[101][101];
int xx[4]={0,0,1,-1};
int yy[4]={1,-1,0,0};
int n,m,num;
int dfs(int x,int y )
{
if(vis[x][y]>num)
num=vis[x][y];
for(int i=0;i<4;i++)
{
int tx=x+xx[i];
int ty=y+yy[i];
if(tx>0&&ty>0&&tx<=n&&ty<=m&&vis[x][y]+1>vis[tx][ty]&&a[tx][ty]<a[x][y])
{
vis[tx][ty]=vis[x][y]+1;
dfs(tx,ty);
}
}
}
int main()
{
int i,j;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
scanf("%d",&a[i][j]);
}
}
int sum=0;
memset(vis,0,sizeof(vis));
num=0;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
if(a[i][j]<=sum)continue;
if(vis[i][j]==0)
vis[i][j]=1;
dfs(i,j);
if(num>sum)
sum=num;
}
}
printf("%d\n",sum);
}
return 0;
}