Life has its own fate, and meeting may not be accidental.

0%

HDU-Pascal's Travels(记忆化搜索)

题目

nxn游戏板上装有整数,每平方一个非负整数。目标是沿着板子的左上角到右下角的任何合法路径行进。任何一个正方形中的整数表示距该位置必须多大的步幅。如果步长将提前离开游戏板,则禁止沿该特定方向前进。所有步骤都必须在右侧或底部。请注意,0是一个死角,会阻止进一步的进展。
考虑图1所示的4 x 4板,其中实心圆圈标识起始位置,而虚线圆圈标识目标。图2显示了从起点到目标的三个路径,每个路径中不相关的数字都已删除。


输入格式

输入包含1到30个板的数据,最后一行仅包含整数-1。电路板的数据从包含单个正整数n(4 <= n <= 34)的行开始,n是该电路板中的行数。随后是n行数据。每行包含n个数字,0-9,中间没有空格。

输出格式

每个板的输出由一行组成,包含一个整数,该整数是从左上角到右下角的路径数。任何一块板的路径将少于2 ^ 63。

样本输入

1
4
2
2331
3
1213
4
1231
5
3110
6
4
7
3332
8
1213
9
1232
10
2120
11
5
12
11101
13
01111
14
11111
15
11101
16
11101
17
-1

样本输出

1
3
2
0
3
7

代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
int n,m,k,Max;
4
long long vis[110][110];
5
int Map[110][110]; 
6
int dir[4][2]={-1,0,1,0,0,-1,0,1};
7
long long dfs(int x,int y){
8
	if(x==n-1&&y==n-1){     //到点
9
		return 1;
10
	}
11
	if(vis[x][y]){
12
		return vis[x][y];
13
	}
14
	if(x<0||y<0||x>=n||y>=n||Map[x][y]==0){     //如果为0或者超出范围
15
		return 0;
16
	}
17
	vis[x][y]+=dfs(x+Map[x][y],y)+dfs(x,y+Map[x][y]);  //两个方向
18
	
19
	return vis[x][y];
20
}
21
int main(){
22
	while(scanf("%d",&n)!=EOF){
23
		if(n==-1){
24
			break;
25
		}
26
		memset(vis,0,sizeof(vis));
27
		char s[50];
28
		for(int i=0;i<n;i++){
29
			scanf("%s",s);
30
			for(int j=0;j<n;j++){
31
				Map[i][j]=s[j]-'0';
32
			}
33
		}
34
		printf("%lld\n",dfs(0,0));
35
	}
36
    return 0;
37
}