Problem D
Dancing Digits
题目意思：
给你{1,2,3,4,5,6,7,8}的一个排列，其中每个数带负号或带正号，通过插入的方法将这些数按绝对值从小到大排序，输出插入的最小步数，如果不可能完成输出-1，能否插入的要求是：你要根据其余的一个数嵌入其左边或右边，这个数跟你要插入的数不同符号，且绝对值相加必须得是素数，所以根据一个数为中心你可以插入其左或其右。
解题思路：
#BFS+Hash# 哈希选择了康托展开，用队列存储每一个状态，且用visit[对应哈希值]表示是否已访问过。思路清晰 了就好办，主要是看状态转移的时候是怎样一个转移法，首先要顾及每一个数共需要两个for循环，把每两个数都判断一遍，判断的要求就是一正一负，绝对值相加是素数，然后还要分情况放左边还是右边，我花的时间主要是在写插入函数那里，具体思路看代码实现（画图找规律是王道啊）。一开始你得判断几个特殊情况。
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define MAXN 40322
#define SIZE 8
using namespace std; typedef int State[SIZE];
typedef struct Status{
State value;
}Status; queue<Status>queuing; int st[MAXN];
bool visit[MAXN];
bool Prime[*SIZE];
int factory[] = {, , , , , , , , };
int start = -;
int dir[] = {, -};
int input[SIZE]; void getPrime()
{//存储需要的素数
memset(Prime, false, sizeof(Prime));
for(int i=; i<*SIZE; ++i)
{
if(!Prime[i])
{
for(int j=i+i; j<*SIZE; j += i)
Prime[j] = true;
}
}
return;
} int try_to_insert(int s[])
{//返回对应的康托展开
int sum = ;
for(int i=; i<SIZE; ++i)
{
int cnt = ;
for(int j=i+; j<SIZE; ++j)
if(fabs(s[i])>fabs(s[j])) ++cnt;
sum += cnt*factory[SIZE-i-];
}
return sum;
} bool isExchange(int a, int b)
{//判断两个对应的数能否插入，可以返回true否则false if((a> && b<) || (a< && b>))
{
if(a>) b = -b;
else a = -a;
if(!Prime[a+b]) return true;
}
return false;
} void Translate(int s[], int to, int from, int kind)
{//插入的函数，kind = -1 表示from位置的数插入到to位置的左边，kind = 1 表示插入到to位置的右边
State p;
int temp_to = s[to], temp_from = s[from];
bool flag = false;
s[to] = s[from] = ;
if(kind == -)
{
for(int i=SIZE-, j=SIZE-; i>=; )
{
if(s[j] != ) p[i--] = s[j--];
else if(flag == false)
{
if(to > from)
{
p[i--] = temp_to;
p[i--] = temp_from;
}
j--;
flag = true;
}
else
{
if(to < from)
{
p[i--] = temp_to;
p[i--] = temp_from;
}
j--;
}
}
}
else
{
for(int i=, j=; i<SIZE; )
{
if(s[j] != ) p[i++] = s[j++];
else if(flag == false)
{
if(to < from)
{
p[i++] = temp_to;
p[i++] = temp_from;
}
j++;
flag = true;
}
else
{
if(to > from)
{
p[i++] = temp_to;
p[i++] = temp_from;
}
j++;
}
}
}
memcpy(s, p, sizeof(p));
return;
} bool Traverse()
{
memset(visit, false, sizeof(visit));
visit[start] = true;
st[start] = ;
Status init;
memcpy(init.value, input, sizeof(input));
queuing.push(init);
while(!queuing.empty())
{
Status ss = queuing.front();
State& s = ss.value;
int elem = try_to_insert(s);
queuing.pop();
//两个for循环加上两种插入的情况
for(int i=; i<SIZE; ++i)
{
for(int j=; j<SIZE; ++j)
{
if(isExchange(s[i], s[j]))
{
Status tt;
State& t = tt.value;
for(int z=; z<; ++z)
{
memcpy(t, s, sizeof(t));
if(i+dir[z] != j)
{
Translate(t, i, j, dir[z]);
int step = try_to_insert(t);
if(!visit[step])
{
visit[step] = true;
st[step] = st[elem]+;
queuing.push(tt);
if(step == )
{//step == 0 表示到达了已排序的状态则返回
return true;
}
}
}
}
}
}
}
}
return false;
} int main()
{
#ifndef ONLINE_JUDGE
freopen("F:\\test\\input.txt", "r", stdin);
#endif
getPrime();
int T = ;
while(cin>>input[] && input[])
{
int flag = ;
if(input[] > ) flag++; for(int i=; i<SIZE; ++i)
{
cin>>input[i];
if(input[i] > ) flag++;
}
start = try_to_insert(input);
cout<<"Case "<<++T<<": ";
if (start == )
{
cout<<""<<endl;
continue;
}
if (flag == SIZE || !flag)
{
cout<<"-1"<<endl;
continue;
}
if(Traverse()) cout<<st[]<<endl;
else cout<<"-1"<<endl; while(!queuing.empty()) queuing.pop();
}
return ;
}