POJ 1088 滑雪 && NYOJ 10 skiing

题目链接~~>

做题感悟：开始做这题时是在 POJ 上做的，一眼就瞅出来用记忆化搜索 1A，但是在 NYOJ 上又重新打了一次代码 Wa 了，很是郁闷又在 POJ 上提交了一次 AC，幸好时间长暴力搜索水过，过了之后看了一下别人的代码才发现错误，在搜着已经有值的时候，那个点标记了没取消， POJ 数据有点水了。

解题思路：依次遍历每个点，遍历完一个点意味着这个值是这个点的最优值，把这个值存下来，如果遍历另一个点时遍历到已经遍历过的点就不用再往下遍历了。俗称：记忆化搜索。据说这题应该用动态规划过，本人还没研究，所以……

代码（NYOJ）：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      int n,m,best,max ;
     
    
   

    

     

    
    

     

      int g[105][105],a[105][105] ; 
     
    
   

    

     

    
    

     

      bool vis[105][105] ;
     
    
   

    

     

    
    

     

      int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1} ;
     
    
   

    

     

    
    

     

      void dfs(int x,int y,int num)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       best = best < num ? num : best ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int sx=x+dx[i] ;
     
    
   

    

     

    
    

     
 int sy=y+dy[i] ;
     
    
   

    

     

    
    

     
 if(sx<0||sy<0||sx>=n||sy>=m||vis[sx][sy]||a[x][y]<=a[sx][sy])
     
    
   

    

     

    
    

     
 continue ;
     
    
   

    

     

    
    

     

       vis[sx][sy]=true ;
     
    
   

    

     

    
    

     
 if(g[sx][sy])
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       best= best<g[sx][sy]+num ? g[sx][sy]+num : best ;
     
    
   

    

     

    
    

     

       vis[sx][sy]=false ; // 开始时没这一行代码
     
    
   

    

     

    
    

     
 continue ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       dfs(sx,sy,num+1) ;
     
    
   

    

     

    
    

     

       vis[sx][sy]=false ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int i,j,T ;
     
    
   

    

     

    
    

     
 scanf("%d",&T) ;
     
    
   

    

     

    
    

     
 while(T--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

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

    

     

    
    

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

    

     

    
    

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

    

     

    
    

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

    

     

    
    

     
 memset(g,0,sizeof(g)) ;
     
    
   

    

     

    
    

     

       max=0 ;
     
    
   

    

     

    
    

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

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       best=1 ;
     
    
   

    

     

    
    

     
 memset(vis,false,sizeof(vis)) ;
     
    
   

    

     

    
    

     

       vis[i][j]=true ;
     
    
   

    

     

    
    

     

       dfs(i,j,1) ;
     
    
   

    

     

    
    

     

       g[i][j]=best ;
     
    
   

    

     

    
    

     

       max= max < g[i][j] ? g[i][j] : max ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

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

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      } 
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/17510425