給出起始狀态如:
問最少多少步操作可以變為:
每次操作隻能把一個數字放到某個空格,不能交換兩個數字的位置
hash判重模闆mark一個
#include "stdio.h"
#include "string.h"
#include "queue"
using namespace std;
const int mod=1000007;
int aim[4][8]=
{
{11,12,13,14,15,16,17},
{21,22,23,24,25,26,27},
{31,32,33,34,35,36,37},
{41,42,43,44,45,46,47}
};
struct node
{
int a[4][8],t;
}ncur;
int used[1000008];
int get_hash(node b)
{
int mark[70],i,j,k;
__int64 temp;
memset(mark,0,sizeof(mark));
k=0;
for (i=0;i<4;i++)
for (j=0;j<8;j++)
{
mark[k++]=b.a[i][j]/10;
mark[k++]=b.a[i][j]%10;
}
temp=0;
for (i=0;i<k;i++)
temp=temp*7+mark[i];
temp=temp&0x7fffffff;
temp%=mod;
return temp;
}
int ok(node b)
{
int i,j;
for (i=0;i<4;i++)
for (j=0;j<7;j++)
if (b.a[i][j]!=aim[i][j]) return 0;
return 1;
}
node change(node b,int w)
{
node key;
int i,j;
key=b;
for (i=0;i<4;i++)
for (j=0;j<=7;j++)
if (key.a[i][j]==w+1)
{
key.a[i][j]=0;
return key;
}
}
int BFS()
{
queue<node>q;
node cur,next;
int i,j,temp;
ncur.t=0;
q.push(ncur);
memset(used,0,sizeof(used));
temp=get_hash(ncur);
used[temp]=1;
while (!q.empty())
{
cur=q.front();
q.pop();
if (ok(cur)==1) return cur.t;
for (i=0;i<4;i++)
for (j=1;j<8;j++)
if (cur.a[i][j]==0 && cur.a[i][j-1]!=0 && cur.a[i][j-1]%10!=7)
{
next=change(cur,cur.a[i][j-1]);
next.a[i][j]=next.a[i][j-1]+1;
next.t=cur.t+1;
temp=get_hash(next);
if (used[temp]==0)
{
used[temp]=1;
q.push(next);
}
}
}
return -1;
}
int main()
{
int Case,i,j;
scanf("%d",&Case);
while (Case--)
{
for (i=0;i<4;i++)
for (j=1;j<=7;j++)
{
scanf("%d",&ncur.a[i][j]);
if (ncur.a[i][j]%10==1)
{
ncur.a[ncur.a[i][j]/10-1][0]=ncur.a[i][j];
ncur.a[i][j]=0;
}
}
printf("%d\n",BFS());
}
return 0;
}