Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

记忆化搜索,一直wa,求解

Posted by 201030720425 at 2011-05-12 09:25:38 on Problem 2251
#include<cstdio>
#include<string>
#include<cstring>
#include<stack>
#include<iostream>
#define N 35
using namespace std;
int X,Y,Z,dp[N][N][N],dr[6][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}},bi[N][N][N]={0};
char a[N][N][N];
int min(int a,int b)
{
	return a>b?b:a;
}
int DP(int z,int x,int y)
{
	
	int i,j,k,ans;
	//printf("%d-%d-%d\n",x,y,z);
	if(dp[z][x][y]!=-1)
		return dp[z][x][y];
	else
	{
		if(a[z][x][y]=='#')
			dp[z][x][y]=0;
		else
			if(a[z][x][y]=='E')
				dp[z][x][y]=1;
			else
				{
					ans=0;
					for(i=0;i<6;i++)
					{
						if(z+dr[i][0]<Z&&z+dr[i][0]>=0&&x+dr[i][1]<X&&x+dr[i][1]>=0&&y+dr[i][2]<Y&&y+dr[i][2]>=0&&bi[z+dr[i][0]][x+dr[i][1]][y+dr[i][2]]!=1)
						{
		                     bi[z][x][y]=1;
							if(DP(z+dr[i][0],x+dr[i][1],y+dr[i][2])>0)
							{
								if(ans>0)
									ans=min(ans,DP(z+dr[i][0],x+dr[i][1],y+dr[i][2])+1);
								else
									ans=DP(z+dr[i][0],x+dr[i][1],y+dr[i][2])+1;
								
							}
						}
					}
					dp[z][x][y]=ans;
				}
	}
	return  dp[z][x][y];
}
int main()
{
	int x,y,z,i,j,k,ans;
	while(cin>>Z>>X>>Y,Z||X||Y)
	{
		
	//	memset(a,' ',sizeof(a));
		for(i=0;i<Z;i++)
		{
			for(j=0;j<X;j++)
			{
				getchar();
				for(k=0;k<Y;k++)
				{
					scanf("%c",&a[i][j][k]);
					if(a[i][j][k]=='S')
					{
						z=i;x=j;y=k;
					}
				}
				
			}
			getchar();
		}
		memset(bi,0,sizeof(bi));
	   memset(dp,-1,sizeof(dp));
		ans=DP(z,x,y)-1;
		if(ans>=0)
		{
			printf("Escaped in %d minute(s).\n",ans);
		}
		else
		{
			printf("Trapped!\n");
		}
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator