https://www.luogu.com.cn/problem/P1434

题目大意:

找一条路径,从高到低,遍历过的地点最长。
输入 #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
输出 #1 
25
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=500200,M=2002;
int n,m,maxn=0,a[M][M],mp[M][M];
//mp存储比自己小的地方的数量
int dx[]={-1,0,0,1},dy[]={0,-1,1,0};
int dfs(int x,int y)
{
    if(mp[x][y]) return mp[x][y];//如果已经标记过,直接返回
    //没有标记过的话,这个地方是第一个点,默认是最小的地点
    mp[x][y]=1;
    for(int i=0;i<4;i++)//四个方向对比
    {
        int xx=dx[i]+x,yy=dy[i]+y;
        if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&a[x][y]>a[xx][yy])//因为找的地方是更小的,所以直接是>
        {
            dfs(xx,yy);//进入这个点往下搜索
            mp[x][y]=max(mp[x][y],mp[xx][yy]+1);//到底是自己更大,还是我往下的那一条带上自己更大
        }
    }
    return mp[x][y];//返回值
}
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        maxn=0;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cin>>a[i][j];
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                maxn=max(maxn,dfs(i,j));//遍历,从这个点往下寻找比自己小的地方
            }
        }
        cout<<maxn<<endl;
    }
    return 0;
}

原文地址:http://www.cnblogs.com/Vivian-0918/p/16846997.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性