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

Re:救命啊,老是哇,检查半天都看不出错.

Posted by timeloop at 2008-09-07 20:49:39 on Problem 1324
In Reply To:救命啊,老是哇,检查半天都看不出错. Posted by:timeloop at 2008-09-07 15:31:13
忘了输出case了,改成这样还是WA.
#include <stdio.h>
#include <string.h>
int n,m,l;
bool hash [21][21][4][4][4][4][4][4][4];//0表示上,1表下,2表左,3表右
struct ss
{
	int x;
	int y;
}szb[8],tmp9[8];
int map[21][21];
struct zt
{
	int x;
	int y;
	int b[7];
	int cnt;
}dl[1400000],tmp1,tmp2,tmp3;
void in(struct zt a)
{
hash[a.x][a.y][a.b[0]][a.b[1]][a.b[2]][a.b[3]][a.b[4]][a.b[5]][a.b[6]]=1;	
}

void in1(struct zt &a,struct zt &b)
{
	int i;
	a.x=b.x;
	a.y=b.y;
   for(i=0;i<7;i++)
	   a.b[i]=b.b[i];
}
void fj(struct zt a)
{
	int i;
	tmp9[0].x=a.x;
	tmp9[0].y=a.y;

for(i=1;i<l;i++)
{
	if(a.b[i-1]==0)
	{
		tmp9[i].x=tmp9[i-1].x-1;
		tmp9[i].y=tmp9[i-1].y;
	}
	else if(a.b[i-1]==1)
	{
		tmp9[i].x=tmp9[i-1].x+1;
		tmp9[i].y=tmp9[i-1].y;
	}
	else if(a.b[i-1]==2)
	{
		tmp9[i].x=tmp9[i-1].x;
		tmp9[i].y=tmp9[i-1].y-1;
	}
	else if(a.b[i-1]==3)
	{
		tmp9[i].x=tmp9[i-1].x;
		tmp9[i].y=tmp9[i-1].y+1;
	}
}
for(i=0;i<l;i++)
{
	map[tmp9[i].x][tmp9[i].y]=1;
}
}
void ffj(struct zt a)
{
	int i;
for(i=0;i<l;i++)
{
	map[tmp9[i].x][tmp9[i].y]=0;
}
}
bool check(int x,int y)
{
	if(x<1||x>n)
		return 0;
	if(y<1||y>m)
		return 0;
    if(map[x][y]==1)
		return 0;
	return 1;
}
bool check1(struct zt a)
{
	return hash[a.x][a.y][a.b[0]][a.b[1]][a.b[2]][a.b[3]][a.b[4]][a.b[5]][a.b[6]];
}
bool checkend(int x,int y)
{
	if(x==1&&y==1)
		return 1;
	return 0;
}

int main()
{
	int i,j,k,k1,t1,t2,bg,ed,tag,cnt2;
	cnt2=1;
	while(scanf("%d%d%d",&n,&m,&l)!=EOF)
	{
		if(n==0&&m==0&&l==0)
			break;
       for(i=0;i<l;i++)
		   scanf("%d%d",&szb[i].x,&szb[i].y);
	   memset(map,0,sizeof(map));
        scanf("%d",&k1);
		for(i=0;i<k1;i++)
		{
			scanf("%d%d",&t1,&t2);
		    map[t1][t2]=1;
		}
        memset(hash,0,sizeof(hash));
		tag=0;
		tmp1.x=szb[0].x;
		tmp1.y=szb[0].y;
		if(szb[0].x==1&&szb[0].y==1)
		{
			printf("0\n");
			continue;
		}
		for(i=0;i<l-1;i++)
		{
			if(szb[i+1].x==szb[i].x)
			{
                if(szb[i+1].y>szb[i].y)
					tmp1.b[i]=3;
				else
					tmp1.b[i]=2;
			}
			else if(szb[i+1].y==szb[i].y)
              	{
                if(szb[i+1].x>szb[i].x)
					tmp1.b[i]=1;
				else
					tmp1.b[i]=0;
			}
		}
		for(i=l-1;i<7;i++)
			tmp1.b[i]=0;
		tmp1.cnt=0;
		in1(dl[0],tmp1);
		in(tmp1);
		dl[0].cnt=0;
       bg=0;
	   ed=1;
while(bg!=ed)
{
	in1(tmp2,dl[bg]);
	tmp2.cnt=dl[bg].cnt;
	fj(tmp2);
	if(check(tmp2.x+1,tmp2.y))
	{
       tmp3.x=tmp2.x+1;
       tmp3.y=tmp2.y;
	   tmp3.b[0]=0;
	   for(i=1;i<l-1;i++)
		   tmp3.b[i]=tmp2.b[i-1];
	   for(i=l-1;i<7;i++)
		   tmp3.b[i]=0;
	   if(!check1(tmp3))
	   {
		   in1(dl[ed],tmp3);
		   dl[ed].cnt=tmp2.cnt+1;
		   in(tmp3);
		    if(checkend(tmp3.x,tmp3.y))
		   {
			   tag=1;
			   break;
		   }
		   ed=(ed+1)%1400000;
		  
	   }
		 
	}
	if(check(tmp2.x-1,tmp2.y))
	{
       tmp3.x=tmp2.x-1;
       tmp3.y=tmp2.y;
	   tmp3.b[0]=1;
	   for(i=1;i<l-1;i++)
		   tmp3.b[i]=tmp2.b[i-1];
       for(i=l-1;i<7;i++)
		   tmp3.b[i]=0;
	   if(!check1(tmp3))
	   {
		   in1(dl[ed],tmp3);
		   dl[ed].cnt=tmp2.cnt+1;
		   in(tmp3);
		   if(checkend(tmp3.x,tmp3.y))
		   {
			   tag=1;
			   break;
		   }
		   ed=(ed+1)%1400000;
		   
	   }
		 
	}
	if(check(tmp2.x,tmp2.y+1))
	{
       tmp3.x=tmp2.x;
       tmp3.y=tmp2.y+1;
	   tmp3.b[0]=2;
	   for(i=1;i<l-1;i++)
		   tmp3.b[i]=tmp2.b[i-1];
       for(i=l-1;i<7;i++)
		   tmp3.b[i]=0;
	   if(!check1(tmp3))
	   {
		   in1(dl[ed],tmp3);
		   dl[ed].cnt=tmp2.cnt+1;
		   in(tmp3);
		    if(checkend(tmp3.x,tmp3.y))
		   {
			   tag=1;
			   break;
		   }
		   ed=(ed+1)%1400000;
		  
	   }
		 
	}
		if(check(tmp2.x,tmp2.y-1))
	{
       tmp3.x=tmp2.x;
       tmp3.y=tmp2.y-1;
	   tmp3.b[0]=3;
	   for(i=1;i<l-1;i++)
		   tmp3.b[i]=tmp2.b[i-1];
       for(i=l-1;i<7;i++)
		   tmp3.b[i]=0;
	   if(!check1(tmp3))
	   {
		   in1(dl[ed],tmp3);
		   dl[ed].cnt=tmp2.cnt+1;
		   in(tmp3);
		   if(checkend(tmp3.x,tmp3.y))
		   {
			   tag=1;
			   break;
		   }
		   ed=(ed+1)%1400000;
		   
	   }
		 
	}
		ffj(tmp2);
		bg=(bg+1)%1400000;
}
/* for(i=0;i<ed;i++)
     printf("%d\n",dl[i].cnt);*/
	 printf("Case %d: ",cnt2); 
if(tag)
printf("%d\n",dl[ed].cnt);
else
printf("-1\n"); 
cnt2++;
	}
	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