一道很好的广搜题,不过我做得很坑爹的说,而且时间,空间都用到了极致,是做愚蠢的做法……悲哀啊……
#include<iostream>
using namespace std;
int m,n,l,r[4][2]={-1,0,0,-1,0,1,1,0};
bool vis[21][21][1<<14],map[21][21];
struct T
{
int x[8],y[8],step;
};
T t1,t2,q[20*20*(1<<14)];
int bfs()
{
int i,j,b,s,x0,x1,x2,y0,y1,y2,head,tail;
head=tail=0;
q[tail++]=t1;
while(head!=tail)
{
t1=q[head++];
if(t1.x[0]==1&&t1.y[0]==1)return t1.step;
for(i=0;i<4;i++)
{
x0=x1=t1.x[0]+r[i][0];
y0=y1=t1.y[0]+r[i][1];
for(j=0;j<l;j++)
if(x0==t1.x[j]&&y0==t1.y[j])break;
if((x0<1||x0>n||y0<1||y0>m)||map[x0][y0]||j!=l)continue;
t2.x[0]=x1;
t2.y[0]=y1;
s=0;
for(j=0;j<l-1;j++)
{
x2=t2.x[j+1]=t1.x[j];
y2=t2.y[j+1]=t1.y[j];
if(y1==y2)
{
if(x1>x2)b=0;
else b=2;
}
else
{
if(y1>y2)b=1;
else b=3;
}
s+=b*(1<<(2*j));
x1=x2;
y1=y2;
}
if(!vis[x0][y0][s])
{
vis[x0][y0][s]=1;
t2.step=t1.step+1;
q[tail++]=t2;
}
}
}
return -1;
}
int main()
{
//freopen("a.txt","r",stdin);
int i,k,x,y,c=1;
while(scanf("%d%d%d",&n,&m,&l)&&(n||m||l))
{
memset(vis,0,sizeof(vis));
memset(map,0,sizeof(map));
for(i=0;i<l;i++)scanf("%d%d",&t1.x[i],&t1.y[i]);
t1.step=0;
scanf("%d",&k);
for(i=0;i<k;i++)
{
scanf("%d%d",&x,&y);
map[x][y]=1;
}
printf("Case %d: ",c++);
printf("%d\n",bfs());
}
return 0;
}