hdu 1208

本文主要是介绍hdu 1208，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

记忆化搜索 : 记忆化搜索的方式表现为 dfs+dp
记录已经搜索过的结果，如果搜索过，直接返回结果，否则才搜索。

搜索类的题，好久没写，具体细节有些忘记了，
dfs中如果需要回溯，则dfs调用后面再重新把走过的路标记为false。
比如常见的四个方向搜索

for(int i=0;i<4;i++){int xx=x+dir[i][0];int yy=y+dir[i][1];if(xx>=n||xx<0||yy>=n||yy<0)continue;if(!visited[xx][yy]){visited[xx][yy]=true;dfs(xx,yy);}//importvisited[xx][yy]=false;  // backup
}

AC代码：

#include <iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
using namespace std;typedef long long LL;const int maxn=40;int n;
int sx,sy;
int ex,ey;int g[maxn][maxn];
LL num[maxn*maxn];int dir[4][2]={1,0,0,1};//d,r;
bool visited[maxn][maxn];
LL total=0;
LL  dfs(int start){if(num[start]>0) return num[start];int x=start/n;int y=start%n;if(x==ex&&y==ey)return 1;LL sum=0;for(int i=0;i<2;i++){int xx=x+dir[i][0]*g[x][y];int yy=y+dir[i][1]*g[x][y];if(xx>=n||xx<0||yy>=n||yy<0||g[x][y]==0) continue;//int next =xx*n+yy;if(num[next]>0) sum+=num[next];else{sum+=dfs(next);}}num[start]=sum;return num[start];}int main()
{string s;while(scanf("%d",&n)!=EOF){if(n==-1)break;total=0;for(int i=0;i<n;i++){cin>>s;for(int j=0;j<n;j++){g[i][j]=s[j]-'0';}}//memset(visited,false,sizeof(visited));visited[0][0]=true;sx=sy=0;ex=ey=n-1;LL ans=0;memset(num,-1,sizeof(num));ans=dfs(0);printf("%lld\n",ans);}return 0;
}

这篇关于hdu 1208的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---