queue
q.push(w);
while(!q.empty())
{
w=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int x,y,state;
x=w.B[0][0]+dir[i][0];
y=w.B[0][1]+dir[i][1];
if(x==1&&y==1)
return w.step+1;
if(!path(x,y,w.B))
continue;
v.step=w.step+1;
for(int j=L-1;j>0;j--)
{
v.B[j][0]=w.B[j-1][0];
v.B[j][1]=w.B[j-1][1];
}
v.B[0][0]=x;
v.B[0][1]=y;
state=getstate(v.B);
if(flag[x][y][state])
continue;
flag[x][y][state]=true;
q.push(v);
}
}
return -1;
}
int main()
{
int Case=1;
while(scanf("%d%d%d",&n,&m,&L),n+m+L)
{
memset(map,0,sizeof(map));
int mst=pow(4,L-1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=0;k
for(int i=0;i
scanf("%d%d",&w.B[i][0],&w.B[i][1]);
}
scanf("%d",&K);
for(int i=0;i
int row,col;
scanf("%d%d",&row,&col);
map[row][col]=1;
}
w.step=0;
printf("Case %d: %d\n",Case++,bfs());
}
return 0;
}
/*
4 4 4
3 2
3 1
2 1
2 2
6
1 2
1 3
1 4
2 3
2 4
4 1
*/
#include
#include
#include
#include
#include
#include
using namespace std;
struct st
{
int step;
int B[10][2];//蛇的位置
}w,v;
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int map[21][21];//0表示空地，1表示石头的位置
bool flag[21][21][16384];//用4进制压缩状态,最大为4^7-1
int n,m,L,K;
int location(int px,int py,int nx,int ny)//求两个节点的相对位置
{
if(px==nx)
{
if(py>ny)
return 0;
else
return 1;
}
else
{
if(px>nx)
return 2;
else
return 3;
}
}
int getstate(int B[][2])//压缩状态
{
int s=0;
for(int i=0;i
return s;
}
bool path(int x,int y,int B[][2])
{
if(x<1||x>n||y<1||y>m||map[x][y]!=0)
return false;
for(int i=0;i
return false;
return true;
}
int bfs()
{
if(w.B[0][0]==1&&w.B[0][1]==1)
return 0;
queue
q.push(w);
while(!q.empty())
{
w=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int x,y,state;
x=w.B[0][0]+dir[i][0];
y=w.B[0][1]+dir[i][1];
if(x==1&&y==1)
return w.step+1;
if(!path(x,y,w.B))
continue;
v.step=w.step+1;
for(int j=L-1;j>0;j--)
{
v.B[j][0]=w.B[j-1][0];
v.B[j][1]=w.B[j-1][1];
}
v.B[0][0]=x;
v.B[0][1]=y;
state=getstate(v.B);
if(flag[x][y][state])
continue;
flag[x][y][state]=true;
q.push(v);
}
}
return -1;
}
int main()
{
int Case=1;
while(scanf("%d%d%d",&n,&m,&L),n+m+L)
{
memset(map,0,sizeof(map));
int mst=pow(4,L-1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=0;k