首页 > 其他 > 详细

滑雪问题,记忆化搜索

时间:2021-04-06 20:19:05      阅读:11      评论:0      收藏:0      [点我收藏+]
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int M=1e3+1;
const int dx[4]={1,0,-1,0};//存方向移动 
const int dy[4]={0,1,0,-1};
int r,c;
int m[M][M];//
int f[M][M];//到这点的最长距离 

int dfs(int x,int y){
    if(f[x][y]!=0) return f[x][y];//表示在搜索时,这个点已经知道最长距离 
    int maxt=1;
    int t;
    for(int i=0;i<4;i++){
        int tx=x+dx[i],ty=y+dy[i];
        //判断这个点是否符合行进 
        if(tx>0&&ty>0&&tx<=r&&ty<=c&&m[tx][ty]>m[x][y])
        {
            t=dfs(tx,ty)+1;//因为距离是经过的总长,所以是差+1 
            maxt=max(t,maxt);
        }
    }
    f[x][y]=maxt;
    return maxt;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>r>>c;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin>>m[i][j];
        }
    }
    memset(f,0,sizeof(f));
    int ans=0;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            f[i][j]=dfs(i,j);//算出各点的最长距离 
            ans=max(ans,f[i][j]);//求最长的 
        }
    }
    printf("%d\n",ans);
    return 0;
}

 

滑雪问题,记忆化搜索

原文:https://www.cnblogs.com/BlogBaudelaire/p/14623366.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!