南阳理工OJ 592 spiral grid 蛇形填数，素数迷宫，宽度搜索

#include<stdio.h>
#include<string.h>
bool sushu[10010];
int map[110][110];
bool ves[110][110];
int fang[4][2]={1,0,-1,0,0,1,0,-1};
struct node
{
	int x,y,step;
}a,b,queue[10000];
int base,top;
void f()
{
	int i=1,j=1,term=10000;
	memset(map,0,sizeof(map));
	while(term>1)
	{
		while(map[i][j+1]==0&&j<100)map[i][j++]=term--;
		while(map[i+1][j]==0&&i<100)map[i++][j]=term--;
		while(map[i][j-1]==0&&j>1)  map[i][j--]=term--;
		while(map[i-1][j]==0&&i>1)  map[i--][j]=term--;
	}
	map[i][j]=1;
	return;
}
void g()
{
	memset(sushu,1,sizeof(sushu));
	sushu[1]=0;
	for(int i=2;i<=100;i++)
		if(sushu[i])
			for(int j=i*i;j<=10000;j+=i)
				sushu[j]=0;
}
bool _is(int x,int y)
{
	if(map[x][y]!=0&&(!sushu[map[x][y]])&&(!ves[x][y]))return true;
	return false;
}
int main()
{
	f();
	g();
	bool flag;
	int i,j,num=1,x,y;
	while(~scanf("%d%d",&x,&y))//测试数据有问题，x是素数时，也要求出结果，y是素数时，不应该求出结果
	{
		memset(ves,0,sizeof(ves));
		printf("Case %d: ",num++);
	/*	if(sushu[y]||sushu[x])  //一加这句话就错，真坑
		{
			printf("impossible\n");
			continue;
		}*/
		if(x==y)
		{
			printf("0\n");
			continue;
		}
		for(i=1,flag=false;i<=100;i++)
		{
			for(j=1;j<=100;j++)
				if(map[i][j]==x)
				{
					a.x=i;
					a.y=j;
					a.step=0;
					flag=1;
					break;
				}
			if(flag)break;
		}
		base=top=0;
		queue[top++]=a;
		ves[a.x][a.y]=true;
		flag=0;
		while(base!=top)
		{
			a=queue[base++];
			for(i=0;i<4;i++)
			{
				b.x=a.x+fang[i][0];
				b.y=a.y+fang[i][1];
				if(_is(b.x,b.y))
				{
					ves[b.x][b.y]=true;
					b.step=a.step+1;
					if(map[b.x][b.y]==y)
					{
						flag=true;
						break;
					}
					queue[top++]=b;
				}
			}
			if(flag)break;
		}
		if(flag)printf("%d\n",b.step);
		else printf("impossible\n");
	}
	return(0);
}

 

 

/*
第二种方法，优化了时间
*/
#include<stdio.h>
#include<math.h>
#include<string.h>
int shang,xia,zuo,you,queue[10010],mm[10010],base,top,result,num,fushu,zhengshu;
bool sushu[10010];
void f(int n)//求n的上下左右四个数
{
	if(n<0)n=-n;
	if(n==1){shang=4;xia=8;zuo=6;you=2;return;}
	if(n==4){shang=15;xia=1;zuo=5;you=3;return;}
	int m=(int)sqrt((double)n),jvli=n-m*m;
	if(jvli==0){shang=n-4*m+5;xia=n+4*m+3;zuo=n-1;you=n+1;}
	else if(jvli==1){shang=n+1;xia=n+4*m+3;zuo=n-1;you=n+4*m+5;}
	else if(jvli>1&&jvli<=m){shang=n+1;xia=n-1;zuo=n-4*m+3;you=n+4*m+5;}
	else if(jvli==m+1){shang=n+4*m+7;xia=n-1;zuo=n+1;you=n+4*m+5;}
	else {shang=n+4*m+7;xia=n-4*m+1;zuo=n+1;you=n-1;}
	if(m%2==0)
	{
		shang^=xia^=shang^=xia;
		zuo^=you^=zuo^=you;
	}
}
void g()//求素数
{
	memset(sushu,1,sizeof(sushu));
	sushu[1]=0;
	for(int i=2;i<=100;i++)
		if(sushu[i])
			for(int j=i*i;j<10010;j+=i)
				sushu[j]=0;
}
bool r(int x)//入队，判断，求结果
{            //我用给的两点同时入队遍历，为了区分，一个入队正数，一个入队负数
	if(x>10000)return(false);
	if(sushu[x])return(false);
	if(mm[x]==0)//如果没有标记
	{
		if(queue[base]<0)
		{
			mm[x]=mm[-queue[base]]-1;//标记，记步数
			queue[top++]=-x;//入队
			fushu++;//如果队列里面没有负数了，就说明它在一个圈里出不来
		//	printf("mm[%d]=%d\t",x,mm[x]);
		}
		else 
		{
			mm[x]=mm[queue[base]]+1;
			queue[top++]=x;
			zhengshu++;  // 同上
		//	printf("mm[%d]=%d\t",x,mm[x]);
		}
	}
	else//如果这个点标记过
	{
		if(queue[base]<0&&mm[x]>0)//如果符号不相同的就说明路通了，输出结果
		{
			result=mm[x]-mm[-queue[base]]-1;
			return(true);
		}
		else if(queue[base]>0&&mm[x]<0)
		{
			result=mm[queue[base]]-mm[x]-1;
			return(true);
		}
	}
	return(false);//如果符号相同，就不操作
}
int main()
{
/*	g();               //画的图，可以看看f（）函数写的对不对
	int i,j;
	f(100);
	int term=shang;
	for(i=0;i<10;i++)
	{
		f(term);
		term=xia;
		for(j=0,you=term;j<10;j++)
		{
			if(sushu[you])printf("%5d",you);
			else printf("     ");
			f(you);
		}
		putchar(10);
	}
*/




	int x,y,qq;
	g();//求出1w以内的素数
	while(~scanf("%d%d",&x,&y))
	{
		printf("Case %d: ",++num);
		if(x==0||y==0)break;
		if(sushu[y])
		{
			printf("impossible\n");
			continue;
		}
		if(x==y)
		{
			printf("0\n");
			continue;
		}
		qq=0;
		if(sushu[x])qq=1,sushu[x]=0;  //为了迎合测试数据的错误，只能这样了。。。
		memset(mm,0,sizeof(mm));
		result=0;
		top=base=0;
		queue[top++]=x;
		queue[top++]=-y;//队列里面正的是从x开始搜，负的是从y开始搜
		mm[x]=1;mm[y]=-1;//标记步数
		fushu=zhengshu=1;//初始化
		while(top!=base)
		{
			f(queue[base]);//求出上下左右四个数
			if(r(shang)||r(xia)||r(zuo)||r(you))break;//一个一个判断入队，如果找到通路，就跳出
			if(queue[base]<0)fushu--;//看看出队的是负数还是正数，标记一下
			else zhengshu--;
			if(fushu<=0||zhengshu<=0)break;
			base++;
		}
		if(result)printf("%d\n",result);//如果result不为0，就输出
		else printf("impossible\n");
		if(qq)sushu[x]=1;
	}
	return(0);
}
/*
就因为那错误的测试数据，让我想了一天，调试了一天。
AC的时候，当场飙泪！有种被欺负的感觉....
*/