又是骰子。。最近见到骰子的状态就头痛。。更要命的是这个骰子还带滚的。。
其实可以把转的步数做状态来动归，但考虑到要输出路径，本菜还是觉得用搜索比较实在。
先可以把所有的6个面的数字编号做个预处理(允许重复）have[a1][b1][c1][d1][e1][f1]表示该骰子（不管是否合法，就算6个面都是前面也算）在第几个状态
v[i][6]表示第i个骰子的各个面的数字编号v[3][2]=4就表示第三个骰子的右面是原来前面。（我的顺序是左、右、上、前、下、后）。
从第一个开始搜索，第一状态肯定是have[1][2][3][4][5][6]，按照4个方向滚一遍，添加新的状态入队。
这里可以有个类似spfa的优化，做一个标记数组表示该状态是否在队列里，为0表示不在，不为0就是在，这是bj的值就是该状态在队列中的位置。
对于一个没有到达过的状态，直接入队，如果到达过，能更新最小值就更新入队（如果不在队列中）。
关于路径的问题很容易，如果有状态入队了，那么它的前驱pri就是当前的head，如果更新已在队列中的状态的最小值，那么根据bj找到状态的位置，将这个位置的前驱标记为head。
每当到了目标点时，更新最小值，如果更新了，就额外用一个变量记录目标点的前驱。
搜索完了以后，根据记录的目标点的前驱递归输出路径。
#include<stdio.h>
typedef struct duitype
{
long x,y,z;
}duitype;
duitype dui[10000];
long pre[10000];
long jl[7][7][7][7][7][7];
long temp[7];
long vv[7];
long v[46657][7];
long bj[9][9][46657];
long have[9][9][46657];
long aa,a1,b1,c1,d1,e1,f1,a2,b2,head,last,x,y,z,top,i,ans,k,j,place,zz;
void cha(long a,long b,long c,long d)
{
long t;
t=temp[a];
temp[a]=temp[b];
temp[b]=temp[c];
temp[c]=temp[d];
temp[d]=t;
}
long change(long z,char c)
{
long i;
for (i=1;i<=6;i++)
temp[i]=v[z][i];
switch(c)
{
case 'l':cha(6,3,4,5);break;
case 'r':cha(4,3,6,5);break;
case 'u':cha(1,5,2,3);break;
case 'd':cha(1,3,2,5);break;
}
return jl[temp[1]][temp[2]][temp[3]][temp[4]][temp[5]][temp[6]];
}
void ind(long x,long y,long z,long all,char c)
{
long ne;
if (x<=0 || x>8 || y<=0 || y>8)
return;
ne=change(z,c);
if (bj[x][y][ne]==0 && have[x][y][ne]>all+v[ne][5])//不在队列中
{
last++;
dui[last].x=x;
dui[last].y=y;
dui[last].z=ne;
pre[last]=head;
have[x][y][ne]=all+vv[v[ne][5]];
bj[x][y][ne]=last;
}
else
{
if (have[x][y][ne]>all+vv[v[ne][5]])//在队列中判能否更新最小值
{
have[x][y][ne]=all+vv[v[ne][5]];
pre[bj[x][y][ne]]=head;
}
}
if (x==a2 && y==b2)//到了目标点 用place额外记录前驱
if (ans>have[x][y][ne])
{
ans=have[x][y][ne];
place=head;
}
}
void getprint(long head)
{
if (dui[head].x==a1 && dui[head].y==b1 && dui[head].z==zz)
{
printf("%c%c ",a1+96,b1+48);
return;
}
getprint(pre[head]);
printf("%c%c ",dui[head].x+96,dui[head].y+48);
}
int main()
{
for (a1=1;a1<=6;a1++)
for (b1=1;b1<=6;b1++)
for (c1=1;c1<=6;c1++)
for (d1=1;d1<=6;d1++)
for (e1=1;e1<=6;e1++)
for (f1=1;f1<=6;f1++)
{
top++;jl[a1][b1][c1][d1][e1][f1]=top;
v[top][1]=a1;v[top][2]=b1;v[top][3]=c1;v[top][4]=d1;v[top][5]=e1;v[top][6]=f1;
} //预处理
for (i=1;i<=8;i++)
for (j=1;j<=8;j++)
for (k=1;k<=46656;k++)
have[i][j][k]=10000000;
ans=10000000;
scanf("%c%c%c%c%c",&a1,&b1,&aa,&a2,&b2);
a1-=96;a2-=96;b1-=48;b2-=48;
for (i=1;i<=6;i++)
scanf("%d",&vv[i]);
z=zz=jl[1][2][3][4][5][6];
head=0;last=1;dui[1].x=a1;dui[1].y=b1;dui[1].z=z;
bj[a1][b1][z]=1;have[a1][b1][z]=vv[v[z][5]];//状态为X,Y坐标，第Z个骰子状态
while (head<last)
{
head++;
x=dui[head].x;y=dui[head].y;z=dui[head].z;
bj[x][y][z]=0;//该状态离队
ind(x+1,y,z,have[x][y][z],'r');
ind(x-1,y,z,have[x][y][z],'l');
ind(x,y+1,z,have[x][y][z],'u');
ind(x,y-1,z,have[x][y][z],'d');
}
printf("%ld ",ans);
getprint(place);
printf("%c%c",a2+96,b2+48);
}
posted on 2011-06-27 18:34
梦转千寻 阅读(121)
评论(0) 编辑 收藏 引用