Dancing Digits
Digits like to dance. One day, 1, 2, 3, 4, 5, 6, 7 and 8 stand in a line to have a wonderful party. Each time, a male digit can ask a female digit to dance with him, or a female digit can ask a male digit to dance with her, as long as their sum is a prime.
Before every dance, exactly one digit goes to who he/she wants to dance with - either to its immediate left or immediate right.
For simplicity, we denote a male digit x by itself x, and denote a female digit x by -x. Suppose the digits are in order {1, 2, 4, 5, 6, -7, -3, 8}. If -3 wants to dance with 4, she must go either to 4's left, resulting {1,
2, -3, 4, 5, 6, -7, 8} or his right, resulting {1, 2, 4, -3, 5, 6, -7, 8}. Note that -3 cannot dance with 5, since their sum 3+5=8 is not a prime; 2 cannot dance with 5, since they're both male.
Given the initial ordering of the digits, find the minimal number of dances needed for them to sort in increasing order (ignoring signs of course).
Input
The input consists of at most 20 test cases. Each case contains exactly 8 integers in a single line. The absolute values of these integers form a permutation of {1, 2, 3, 4, 5, 6, 7, 8}. The last case is followed by a single zero, which should not be processed.
Output
For each test case, print the case number and the minimal number of dances needed. If they can never be sorted in increasing order, print -1.
Sample Input
1 2 4 5 6 -7 -3 8 1 2 3 4 5 6 7 8 1 2 3 5 -4 6 7 8 1 2 3 5 4 6 7 8 2 -8 -4 5 6 7 3 -1 0
Output for the Sample Input
Case 1: 1 Case 2: 0 Case 3: 1 Case 4: -1 Case 5: 3
隐式图 + hash
//BFS + HASH
//UVA 0.509MS
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX 1000000
int num[8], g[8], dist[MAX], isprime[65] ;
int st[MAX][8];
bool cmp(int a, int b)
{
return abs(a) < abs(b);
}
int Isprime(int num)
{
for(int i = 2; i*i <= num; i++)
if(num%i == 0)
return 0;
return 1;
}
int head[MAX], nextSt[MAX];
void initCheck() {memset(head, 0, sizeof(head)); memset(nextSt, 0, sizeof(nextSt));};
int getHash(int s[])
{
int v = 0;
for(int i = 0; i < 8; i++)
v = 10*v+abs(s[i]);
return v % MAX;
}
int checkVis(int s)
{
int h = getHash(st[s]);
int u = head[h];
while(u)
{
if(!memcmp(st[u], st[s], sizeof(st[u])))
return 1; //存在访问记录
u = nextSt[u];
}
nextSt[s] = head[h];
head[h] = s;
return 0;
}
int bfs()
{
initCheck();
memset(dist, 0, sizeof(dist));
int front = 1, tail = 2;
while(front < tail)
{
int *s = st[front];
if(memcmp(s, g, sizeof(g))==0) //找到了
return dist[front];
for(int i = 0; i < 8; i++)
{
for(int j = 0; j < 8; j++)
{
if(i==j)
continue;
if(s[i]*s[j]<0 && isprime[abs(s[i])+abs(s[j])])
{
int keyi = s[i], k;
//s[i]往左移动
if(i>j)
{
//i到j的左边
//扩展新节点st[tail]
dist[tail] = dist[front] + 1;
memcpy(st[tail], s, sizeof(st[tail]));
for(k = i-1; k >= j; k--)
st[tail][k+1] = st[tail][k];
st[tail][k+1] = keyi;
if(!checkVis(tail))
tail++; //压入队列
//i到j的右边
if(i == j+1)
continue;
dist[tail] = dist[front] + 1;
memcpy(st[tail], s, sizeof(st[tail]));
for(k = i-1; k > j; k--)
st[tail][k+1] = st[tail][k];
st[tail][k+1] = keyi;
if(!checkVis(tail))
tail++; //压入队列
}
else if(i < j) //s[i]往右移动
{
//i到j的左边
if(j == i+1)
continue;
dist[tail] = dist[front] + 1;
memcpy(st[tail], s, sizeof(st[tail]));
for(k = i+1; k < j; k++)
st[tail][k-1] = st[tail][k];
st[tail][k-1] = keyi;
if(!checkVis(tail))
tail++;
//i到j的右边
dist[tail] = dist[front] + 1;
memcpy(st[tail], s, sizeof(st[tail]));
for(k = i+1; k <= j; k++)
st[tail][k-1] = st[tail][k];
st[tail][k-1] = keyi;
if(!checkVis(tail))
tail++;
}
}
}
}
front++;
}
return -1;
}
int main()
{
int times = 0;
for(int i = 2; i < 65; i++)
isprime[i] = Isprime(i);
while(scanf("%d", num) && num[0])
{
for(int i = 1; i < 8; i++)
scanf("%d", num+i);
memcpy(g, num, sizeof(num));
memcpy(st[1], num, sizeof(st[1]));
sort(g, g+8, cmp);
int ans = bfs();
printf("Case %d: %d\n", ++times, ans);
}
return 0;
}