首页 > 代码库 > hdu 1088 滑雪

hdu 1088 滑雪

2024-07-16 17:21:33   233人阅读

果然书要结合题来看才有效果

通过这题对记忆化搜索有了初步的理解

 

碰到没有访问过的点 进行搜索 之后记录下该点能滑出的最远距离

碰到搜索过的点 直接加上 dp[i] 就可以了

 

#include<stdio.h>#include<string.h>#include<math.h>#include<iostream>#include<algorithm>#include<queue>#include<stack>#define mem(a,b) memset(a,b,sizeof(a))#define ll __int64#define MAXN 1000#define INF 0x7ffffffusing namespace std;int r,c;int dp[120][120];//dp[i][j] 表示从该点出发滑出的最远距离int map[120][120];int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};int maxx,maxn;void dfs(int a,int b,int coun){    if(map[a][b]==-1) return ;    if(maxn<coun) maxn=coun;    int x,y;    for(int i=0;i<4;i++)    {        x=a+dir[i][0];        y=b+dir[i][1];        if(map[x][y]<map[a][b]&&dp[x][y]==-1)                    dfs(x,y,coun+1);                            else if(map[x][y]<map[a][b]&&dp[x][y]!=-1)//记忆化        {            int temp=dp[x][y]+coun;            if(temp>maxn) maxn=temp;        }    }}int main(){    int i,j;    while(scanf("%d%d",&r,&c)!=EOF)    {        maxx=0;        mem(dp,-1);        mem(map,-1);//初始化 边界        for(i=1;i<=r;i++)                    for(j=1;j<=c;j++)                            scanf("%d",&map[i][j]);                           for(i=1;i<=r;i++)                    for(j=1;j<=c;j++)            {               maxn=0;               dfs(i,j,1);               dp[i][j]=maxn;               if(maxn>maxx) maxx=maxn;            }                printf("%d\n",maxx);    }    return 0;}

　　


联系
我们