本文主要是介绍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 ;
}
这篇关于POJ 1088 滑雪 NYOJ 10 skiing的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
