Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

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

Posted by timeloop at 2008-09-07 15:31:13 on Problem 1324

大牛们帮忙看看哪错了好吗?不然给组会出错的数据?
#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[1200000],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=1;i<l;i++)
{
	map[tmp9[i].x][tmp9[i].y]=1;
}
}
void ffj(struct zt a)
{
	int i;
for(i=1;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;
	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)%1200000;
		  
	   }
		 
	}
	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)%1200000;
		   
	   }
		 
	}
	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)%1200000;
		  
	   }
		 
	}
		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)%1200000;
		   
	   }
		 
	}
		ffj(tmp2);
		bg++;
}
/* for(i=0;i<ed;i++)
     printf("%d\n",dl[i].cnt);*/
if(tag)
printf("%d\n",dl[ed].cnt);
else
printf("-1\n"); 
	}
	return 0;
}

Followed by:

Re:救命啊,老是哇,检查半天都看不出错. (4332) timeloop 2008-09-07 20:49:39
- 头在1,1的case考虑了吗? (4854) rush_again 2008-09-07 21:21:13
- Re:救命啊,老是哇,检查半天都看不出错. (4854) ayuanweiliang 2010-11-23 15:21:44
- Re:救命啊,老是哇,检查半天都看不出错. (4854) 00101307 2011-10-10 00:11:35
Re:救命啊,老是哇,检查半天都看不出错. (131) timeloop 2008-09-07 23:56:19

Post your reply here:

User ID:
Password:
Title:

Content:

> 大牛们帮忙看看哪错了好吗?不然给组会出错的数据?
> #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[1200000],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=1;i<l;i++)
> {
> 	map[tmp9[i].x][tmp9[i].y]=1;
> }
> }
> void ffj(struct zt a)
> {
> 	int i;
> for(i=1;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;
> 	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)%1200000;
> 		  
> 	   }
> 		 
> 	}
> 	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)%1200000;
> 		   
> 	   }
> 		 
> 	}
> 	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)%1200000;
> 		  
> 	   }
> 		 
> 	}
> 		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)%1200000;
> 		   
> 	   }
> 		 
> 	}
> 		ffj(tmp2);
> 		bg++;
> }
> /* for(i=0;i<ed;i++)
>      printf("%d\n",dl[i].cnt);*/
> if(tag)
> printf("%d\n",dl[ed].cnt);
> else
> printf("-1\n"); 
> 	}
> 	return 0;
> }

Home Page Go Back To top