uva11198 Dancing Digits

本文主要是介绍uva11198 Dancing Digits，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

简单题，直接暴力，而且不需要太多剪枝就能过。

忘了写insert函数的返回值导致wa一次，怎么感觉oj上的编译器和我电脑上的g++不一样

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define HASHSIZE 40000
#define MAX 50000
using namespace std;char prime[16]={0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0};//0 to 15
int input[8],head[HASHSIZE],next[MAX],s[MAX][8],steps[MAX],front,rear,flag,all;int isprime(int index)
{if(index-1>=0&&s[rear][index-1]*s[rear][index]<0&&prime[abs(s[rear][index-1])+abs(s[rear][index])]==1)return 1;if(index+1<8&&s[rear][index+1]*s[rear][index]<0&&prime[abs(s[rear][index+1])+abs(s[rear][index])]==1)return 1;return 0;
}int hash(int cur)
{int value=0,i;for(i=0;i<8;i++)value=(value*10+abs(s[rear][i]))%HASHSIZE;//abs放错了位置return value;
}int insert(int cur)
{int hashvalue=hash(cur);int u=head[hashvalue];while(u!=-1){if(memcmp(s[cur],s[u],8*4)==0)return 0;u=next[u];}next[cur]=head[hashvalue];head[hashvalue]=cur;return 1;//返回值忘了写
}void toget()
{int i,j,t,a,b,help;for(i=0;i<8;i++)//起始{for(j=0;j<8;j++)//目标{if(j==i)continue;memcpy(s[rear],s[front],8*4);help=s[rear][i];if(j<i){for(t=i;t>=j+1;t--)s[rear][t]=s[rear][t-1];s[rear][j]=help;}else if(j>i){for(t=i;t<=j-1;t++)s[rear][t]=s[rear][t+1];s[rear][j]=help;}if(isprime(j)){if(insert(rear)){steps[rear]=steps[front]+1;rear++;}}}}
}void bfs()
{int i,j;front=0,rear=1,flag=0;memcpy(s[front],input,8*4);steps[front]=0;memset(head,-1,HASHSIZE*4);while(front<rear){if((abs(s[front][0])==1)&&(abs(s[front][1])==2)&&(abs(s[front][2])==3)&&(abs(s[front][3])==4)&&(abs(s[front][4])==5)&&(abs(s[front][5])==6)&&(abs(s[front][6])==7)&&(abs(s[front][7])==8)){flag=1;all=steps[front];break;}toget();front++;}if(flag==0)printf("-1\n");elseprintf("%d\n",all);
}int main()
{int i,j,count=1;while(scanf("%d",&input[0])&&input[0]){for(i=1;i<8;i++)scanf("%d",&input[i]);printf("Case %d: ",count++);bfs();}return 0;
}

这篇关于uva11198 Dancing Digits的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---