首页 > 代码库 > VIjos 晴天小猪历险记之Number (搜索+链表hash)

VIjos 晴天小猪历险记之Number (搜索+链表hash)

背景

话说上一回,晴天小猪不畏千难万险、千辛万苦、千磨万难……终于爬上了那座深山,来到了那位隐者的小屋中,但它不知道,有一个问题正等待着它……
晴天小猪一推开门,就发现那里……空无一人?但在屋中央有一个石桌,上面有一些字(强吧),最大的几个:如要见我,先过了这道关再说!
晴天小猪定睛一看,终于发现桌上密密麻麻布满了字,费了九天二猪之力,终于将题目看完,大意是:为了维护世界的和平……我们需要让九位勇士组成一个3*3的阵型去屠龙,但是这个阵型的要求很奇特,要九个人按照强弱依次编号1~9,且阵型中每行、每列、每条长对角线上的数字和都为15,这样才能使龙对勇士和阵型收到的损害最小,但九位勇士光是争夺名次就开始翻脸,各位**(任君想象)忙得不可开交,但晴天小猪也急得不可开交(-_-|||),只好向你求助。

描述

现在假设九位勇士已编好了号(感觉好像有人盯着我……)并站好了位置,例如:
7 8 9
1 2 3
4 5 6
每一次交换都可以将相邻的两位勇士(也就是编号……)交换位置,例如:
7 9 8
1 2 3 (8与9交换)
4 5 6

7 8 9
4 2 3 (4与1交换)
1 5 6
但不能
7 8 9
5 2 3 (1与5交换)
4 1 6
求最少的交换次数,使得九位勇士能在最短的时间内(当然是他们争完后……)以最安全的阵型去屠龙。

P.S:由于不能预测未来,各位设想了许多的阵型(-_-||),所以给了你10组阵型(测试点),每组50个……

格式

输入格式

输入数据一共3*50行,每个数据中用3*3的9个不同的1~9的数字表示初始状态。

(样例就只给几个阵型了^_^)

输出格式

每行一个数,即对应的初始阵型到所需阵型所需最少的交换次数,如果无解,输出-1。

样例1

样例输入1

7 8 91 2 34 5 66 1 87 5 32 9 41 2 83 5 46 7 9
Copy

样例输出1

805
Copy

限制

各个测试点5s

提示

欲知后事如何,请做出此题^_^。

来源

Sunnypig

 

技术分享
  1 /*  2     链表hash  3     应该都能懂   4     我们的目标序列有八个  5     把这个矩阵按顺序展开之后  6     其实就是一个1-9的全排列  7     直接将八个目标状态丢进队列中  8     让他扩展完将所有情况的最小距离的找出来  9     只要手写一个数组模拟链表hash就好了 10 */ 11 #include<queue> 12 #include<cstdio> 13 #include<iostream> 14 #define MAXN 100010 15 #define MOD 30000007 16  17 using namespace std; 18  19 int a[3][3]; 20  21 struct node { 22     int to; 23     int step; 24     int next; 25 }; 26 node e[MOD]; 27  28 int head[MOD],tot; 29  30 int step=-1; 31  32 queue<node> q; 33  34 inline void hash_make(int x) { 35     int k=x%MOD; 36     e[++tot].to=x; 37     e[tot].step=step+1; 38     e[tot].next=head[k]; 39     head[k]=tot; 40     q.push(e[tot]); 41 } 42  43 inline void init() { 44     q.push((node){816357492,0,-1});q.push((node){438951276,0,-1}); 45     q.push((node){294753618,0,-1});q.push((node){672159834,0,-1}); 46     q.push((node){618753294,0,-1});q.push((node){276951438,0,-1}); 47     q.push((node){492357816,0,-1});q.push((node){834159672,0,-1}); 48     fill(head,head+MOD+1,-1); 49     hash_make(816357492);hash_make(294753618);hash_make(618753294);hash_make(492357816);  50     hash_make(438951276);hash_make(672159834);hash_make(276951438);hash_make(834159672); 51 } 52  53 inline void translation(int x) { 54     for(int i=2;i>=0;i--) 55       for(int j=2;j>=0;j--) { 56           a[i][j]=x%10; 57           x/=10; 58       } 59     return; 60 } 61  62 inline int digit() { 63     int ans=0; 64     for(int i=0;i<3;i++) 65       for(int j=0;j<3;j++) { 66           ans=ans*10+a[i][j]; 67       } 68     return ans; 69 } 70  71 inline int hash_find(int x) { 72     int k=x%MOD; 73     for(int i=head[k];i!=-1;i=e[i].next)  74         if(e[i].to==x) return e[i].step; 75     return -1; 76 } 77  78 inline void move(int x,int y,int xx,int yy) { 79     swap(a[x][y],a[xx][yy]); 80     int t=digit(); 81     if(hash_find(t)==-1)  82       hash_make(t); 83     swap(a[x][y],a[xx][yy]); 84 } 85  86 inline void bfs() { 87     while(!q.empty()) { 88         node p=q.front(); 89         q.pop(); 90         translation(p.to); 91         step=p.step; 92         for(int i=0;i<3;i++) 93           for(int j=0;j<3;j++) { 94               if(i!=2) move(i,j,i+1,j); 95               if(j!=2) move(i,j,i,j+1); 96           } 97     } 98 } 99 100 inline void _printf() {101     int ans=0,x;102     while(scanf("%d",&ans)!=EOF) {103         for(int i=1;i<=8;i++) {104             scanf("%d",&x);105             ans=ans*10+x;106         }107         printf("%d\n",hash_find(ans));108     }109     return;110 }111 112 int main() {113     init();114     bfs();115     _printf();116     return 0;117 }
代码

 

VIjos 晴天小猪历险记之Number (搜索+链表hash)