折磨題
必須自己手暴HASH，否則STL得太慢 然後一大堆轉移控制
//
// GGGGGGGGGGGGG CCCCCCCCCCCCC AAA
// GGG::::::::::::G CCC::::::::::::C A:::A
// GG:::::::::::::::G CC:::::::::::::::C A:::::A
// G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::::A
// G:::::G GGGGGG C:::::C CCCCCC A:::::::::A
//G:::::G C:::::C A:::::A:::::A
//G:::::G C:::::C A:::::A A:::::A
//G:::::G GGGGGGGGGGC:::::C A:::::A A:::::A
//G:::::G G::::::::GC:::::C A:::::A A:::::A
//G:::::G GGGGG::::GC:::::C A:::::AAAAAAAAA:::::A
//G:::::G G::::GC:::::C A:::::::::::::::::::::A
// G:::::G G::::G C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A
// G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::A A:::::A
// GG:::::::::::::::G CC:::::::::::::::C A:::::A A:::::A
// GGG::::::GGG:::G CCC::::::::::::C A:::::A A:::::A
// GGGGGG GGGG CCCCCCCCCCCCCAAAAAAA AAAAAAA
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
#include <set>
#include <queue>
#include <cctype>
#include <utility>
#include <ctime>
using namespace std;
#ifdef DEBUG
#define debug(...) printf("DEBUG: "),printf(__VA_ARGS__)
#define gettime() end_time=clock();printf("now running time is %.7f\n",(float)(end_time - start_time)/CLOCKS_PER_SEC);
#else
#define debug(...)
#define gettime()
#endif
typedef unsigned int uint;
typedef long long int Int;
#define Set(a,s) memset(a,s,sizeof(a))
#define Write(w) freopen(w,"w",stdout)
#define Read(r) freopen(r,"r",stdin)
#define Pln() printf("\n")
#define I_de(x,n)for(int i=0;i<n;i++)printf("%d ",x[i]);Pln()
#define De(x)printf(#x"%d\n",x)
#define For(i,x)for(int i=0;i<x;i++)
#define CON(x,y) x##y
#define Pmz(dp,nx,ny)for(int hty=0;hty<ny;hty++){for(int htx=0;htx<nx;htx++){\
printf("%d ",dp[htx][hty]);}Pln();}
#define M 55
#define PII pair<int,int>
#define PB push_back
#define oo INT_MAX
#define Set_oo 0x3f
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define eps 1e-6
clock_t start_time=clock(), end_time;
bool xdy(double x,double y){return x>y+eps;}
bool xddy(double x,double y){return x>y-eps;}
bool xcy(double x,double y){return x<y-eps;}
bool xcdy(double x,double y){return x<y+eps;}
int min3(int x,int y,int z){
int tmp=min(x,y);
return min(tmp,z);
}
int max3(int x,int y,int z){
int tmp=max(x,y);
return max(tmp,z);
}
const int mod=1000003;
struct nodes{
char str[10];
bool minus[10];
int step;
}q[mod];
int head[mod],_next[mod];
int isprime[] = {0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1};
int mz[10][10];
inline void inithash(){
Set(head,-1);
Set(_next,-1);
}
inline int _hash(int x){
int ans;
sscanf(q[x].str,"%d",&ans);
// debug("%d\n",ans);
return ans%mod;
}
inline bool insert(int ins){
int hashcode=_hash(ins);
int i,h=head[hashcode];
for(i=h;i!=-1;i=_next[i]){
if(!strcmp(q[i].str,q[ins].str))return false;
}
if(i==-1){
_next[ins]=h;
head[hashcode]=ins;
return true;
}
return false;
}
int x[10];
void buildgraph(){
Set(mz,0);
for(int i=0;i<8;i++){
for(int j=i+1;j<8;j++){
if(x[i]*x[j]<0&&isprime[abs(x[i])+abs(x[j])]){
mz[i][j]=mz[j][i]=1;
debug("mz %d %d\n",i,j);
}
}
}
}
bool dancer(nodes &now,int x,int y){
if(x+1==y)return false;
if(x-1==y){
swap(now.str[x],now.str[y]);
swap(now.minus[x],now.minus[y]);
}
else{
char tmp=now.str[y];
bool btmp=now.minus[y];
if(y>x){
for(int i=y;i>=x+2;i--){
now.str[i]=now.str[i-1];
now.minus[i]=now.minus[i-1];
}
now.str[x+1]=tmp;
now.minus[x+1]=btmp;
}else{
for(int i=y;i<x;i++){
now.str[i]=now.str[i+1];
now.minus[i]=now.minus[i+1];
}
now.str[x]=tmp;
now.minus[x]=btmp;
}
}
return true;
}
bool dancel(nodes &now,int x,int y){
if(x-1==y)return false;
if(x+1==y){
swap(now.str[x],now.str[y]);
swap(now.minus[x],now.minus[y]);
}
else{
char tmp=now.str[y];
bool btmp=now.minus[y];
if(y>x){
for(int i=y;i>=x+1;i--){
now.str[i]=now.str[i-1];
now.minus[i]=now.minus[i-1];
}
now.str[x]=tmp;
now.minus[x]=btmp;
}else{
for(int i=y;i<x-1;i++){
now.str[i]=now.str[i+1];
now.minus[i]=now.minus[i+1];
}
now.str[x-1]=tmp;
now.minus[x-1]=btmp;
}
}
return true;
}
bool isok(int x){
for(int i=1;i<8;i++){
if(q[x].str[i]!=q[x].str[i-1]+1)return false;
}
return true;
}
void bfs(){
inithash();
for(int i=0;i<8;i++)q[0].str[i]=abs(x[i])+'0';
for(int i=0;i<8;i++)q[0].minus[i]=(x[i]<0)?1:0;
q[0].str[8]='';
q[0].step=0;
insert(0);
int front=1,rear=0;
// debug("%s\n",q[0].str);
int ans=-1;
while(front>rear){
nodes now=q[rear];
// debug("%s %d\n",now.str,now.step);
if(isok(rear)){
ans=now.step;
break;
}
for(int i=0;i<8;i++){
for(int j=0;j<8;j++){
if(i==j||(now.minus[i]&&now.minus[j])||(!now.minus[i]&&!now.minus[j])||(!isprime[(now.str[i]-'0')+(now.str[j]-'0')]))continue;
nodes tmp=now;
// if(!mz[i][j]||i==j)continue;
dancer(tmp,i,j);
q[front]=tmp;
if(insert(front)){
// debug("ch %d %d\n %s\n",i,j,q[front].str);
q[front].step=now.step+1;front++;
}
tmp=now;
dancel(tmp,i,j);
q[front]=tmp;
if(insert(front)){
// debug("ch1 %d %d\n %s\n",i,j,q[front].str);
q[front].step=now.step+1;front++;
}
}
}
rear++;
// if(rear>=50)break;
}
printf("%d\n",ans);
}
int main() {
ios_base::sync_with_stdio(0);
int ff=0;
while(~scanf("%d",&x[0])&&x[0]){
for(int i=1;i<8;i++)scanf("%d",&x[i]);
printf("Case %d: ",++ff);
bfs();
}
}
留言
張貼留言