976
uva 11198 - Dancing Digits 隱式圖 bfs
求最少次數，一般就是bfs或者dfs或者數學公式，這題用bfs加上hash很好寫。
因為比較懶，就用了string類型，於是多出char和string的轉換，浪費了很多時間，1.416s才過。
寫hash時不要忘記加絕對值
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#define INF 1E9
using namespace std;
string t;
bool prim[16]={0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0};
int vis[40321];
bool used[10];
const int fac[8]={5040,720,120,24,6,2,1,1};
string now,ne;
inline int abs(int a){return a>0?a:-a;}
int hash(string s)
{
memset(used,0,sizeof(used));
int hh=0,i,j,t;
for(i=0;i<7;i++)
{
s[i]=abs(s[i]);
t=0;
used[s[i]]=1;
for(j=1;j<s[i];j++)
if(!used[j])t++;
hh+=t*fac[i];
}
return hh;
}
queue<string> q;
char next[10];
int bfs()
{
while(!q.empty())q.pop();
q.push(now);
vis[hash(now)]=1;
int i,j,k,t,tt;
while(!q.empty()&&!vis[0])
{
now=q.front();q.pop();
next[8]=now[8]+1;
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{
if(now[i]*now[j]>0)continue;
if(!prim[abs(now[i])+abs(now[j])])continue;
for(k=t=0;t<8;t++)
{
if(t==i)continue;
if(t==j)
{
tt=k;
next[k++]=now[i];
}
next[k++]=now[t];
}
ne=next;
t=hash(ne);
if(!vis[t])
{
vis[t]=ne[8];
q.push(ne);
}
swap(next[tt],next[tt+1]);
ne=next;
t=hash(ne);
if(!vis[t])
{
vis[t]=ne[8];
q.push(ne);
}
}
}
}
return vis[0]-1;
}
char N[10];
int main()
{
int C=0,i,t;
while(scanf("%d",&t)&&t)
{
N[0]=t;
memset(vis,0,sizeof(vis));
for(i=1;i<8;i++)
{
scanf("%d",&t);
N[i]=t;
}
N[8]=1;
now=N;
printf("Case %d: %d\n",++C,bfs());
}
}
最後更新：2017-04-04 07:03:44