欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ 2704 Pascal's Travels G++ dfs记忆化搜索

程序员文章站 2022-07-15 10:52:50
...

POJ 2704 Pascal's Travels G++ dfs记忆化搜索

POJ 2704 Pascal's Travels G++ dfs记忆化搜索

POJ 2704 Pascal's Travels G++ dfs记忆化搜索

#include <iostream>
#include <string>
#include <cstring>
using namespace std;
//英语  DFS记忆化搜索 需要熟练 背 
int da[40][40];
int vis[40][40];
long long dp[40][40];
int N;
int jg;
long long dfs(int x,int y)
{
	//cout<<"dfs "<<x<<" "<<y<<endl;
	if(x>(N-1) || y>(N-1))
	{
		return -1;
	}
	if((x==(N-1) && y==(N-1)) ||(dp[x][y]))//抄博友 
	{
		return dp[x][y];//抄博友 
	}
	vis[x][y]=1;
	int t=da[x][y];
	if((x+t)<N && vis[x+t][y]==0 && (da[x+t][y]!=0 || ((x+t)==(N-1) && y==(N-1))))
	{
		long long zhi=dfs(x+t,y);//抄博友 
		if(zhi>0)
		{
			dp[x][y]+=zhi; //抄博友 
		} 
	}
	if((y+t)<N && vis[x][y+t]==0 && (da[x][y+t]!=0 || (x==(N-1) && (y+t)==(N-1))))
	{
		long long zhi=dfs(x,y+t);//抄博友 
		if(zhi>0)
		{
			dp[x][y]+=zhi;
		}
	}
	vis[x][y]=0;
	//cout<<"DFS "<<x<<" "<<y<<" "<<dp[x][y]<<endl;
	return dp[x][y];//抄博友	
}
int main()
{
	while(1)
	{
		cin>>N;	
		if(N==-1)
		{
			break;
		}
		for(int i=0;i<N;i++)
		{
			string s;
			cin>>s;
			for(int j=0;j<N;j++)
			{
				da[i][j]=s[j]-'0';
			}
		}
		/*
		for(int i=0;i<N;i++)
		{
			for(int j=0;j<N;j++)
			{
				cout<<da[i][j];
			}
			cout<<endl;
		}*/			
		memset(dp,0,sizeof(dp));
		memset(vis,0,sizeof(vis));
		dp[N-1][N-1]=1;//抄博友 
		cout<<dfs(0,0)<<endl;	
		/*
		for(int i=0;i<N;i++)
		{
			for(int j=0;j<N;j++)
			{
				cout<<dp[i][j]<<"   ";
			}
			cout<<endl;
		}*/		
	}	
}