poj 1088 (dfs+记忆化) 滑雪

题目;http://poj.org/problem?id=1088

感觉对深搜还不太熟练，所以练习一下,类似于连连看的那题,注意的是所求的是最大达长度,并不是从最大的或者最小的点出发得到的就是最长的路径

 #include<iostream>

 using namespace std;

 int dx[]={,,,-};

 int dy[]={,-,,};

 int n,m,dis[][];

 int vis[][];

 void dfs(int x,int y)

 {

     for (int i=;i<;i++)

     {

         int sx=x+dx[i];

         int sy=y+dy[i];

         if (sx<||sx>n||sy<||sy>m) continue;

         if (dis[sx][sy]<=dis[x][y]) continue;

         if (vis[sx][sy]>=vis[x][y]+) continue;

         vis[sx][sy]=vis[x][y]+;

         dfs(sx,sy);

     }

 }

 int main()

 {

     int i,j;

     cin>>n>>m;

     for (i=;i<=n;i++){

         for(j=;j<=m;j++){

             cin>>dis[i][j];

             vis[i][j]=;

         }

     }

     for (i=;i<=n;i++)

        for (j=;j<=m;j++)

          dfs(i,j);

     int mx=;

     for (i=;i<=n;i++)

        for (j=;j<=m;j++)

            if (mx<vis[i][j]) mx=vis[i][j];

     cout<<mx<<endl;

     return ;

 }

差不多

 #include<cstdio>

 #include<cstring>

 using namespace std;

 int dx[]={,-,,};

 int dy[]={,,-,};

 int n,m,vis[][];

 int hei[][];

 int dfs(int x,int y)

 {

     if (vis[x][y]) return vis[x][y];

     int ans=;

     for (int i=;i<;i++)

     {

         int sx=x+dx[i];

         int sy=y+dy[i];

         if (sx<||sx>n||sy<||sy>m) continue;

         if (hei[sx][sy]>=hei[x][y]) continue;

         vis[sx][sy]=dfs(sx,sy);

         if (ans<vis[sx][sy])

             ans=vis[sx][sy];

     }

     if (ans) return ans+;

     return ;

 }

 int main()

 {

     int i,j,x,y;

     scanf("%d %d",&n,&m);

     int mn=;

     for (i=;i<=n;i++)

     {

         for (j=;j<=m;j++)

         {

             scanf("%d",&hei[i][j]);

             if (hei[i][j]<mn)

             {

                 x=i,y=j;

                 mn=hei[i][j];

             }

         }

     }

     memset(vis,,sizeof(vis));

     vis[x][y]=;

     for (i=;i<=n;i++)

         for (j=;j<=m;j++)

             vis[i][j]=dfs(i,j);

     int mx=;

     for (i=;i<=n;i++)

         for (j=;j<=m;j++)

            if (mx<vis[i][j]) mx=vis[i][j];

     printf("%d\n",mx);

     return ;

 }