类似于拼图游戏,只能移动和空白格相同的四周的格子,从初始状态到目标状态的最少步数。
![](https://images2015.cnblogs.com/blog/891404/201702/891404-20170207163158854-2039322696.png)
很容易想到是bfs,至于具体怎么实现,关键点是状态的定义,定义的好事半功倍。
bfs里面有一个vis数组,如果你用一个vis[][][][][][][][][],9维的数组来标记,是不合理的,数组也开不下,99,
有hash可以帮忙,这里有两个方案,一个是自己写编码,解码的,其实和hash原理类似。具体的编码解码都只是一种策略。
记得数据结构考试的时候,有一道题目说是要怎么解决hash冲突,我就是写的加一个链表。后来听说不是这么做的,说什么直接加到后面一个单元,我觉得还不如加一个链表。
看了一下刘汝佳的写法,果然和我的思路相同,也是加一个链表。
然后最简单的方案就是stl里面的set了。
1 #include 2 3 using namespace std; 4 5 typedef int State[9]; 6 const int maxstadt = 1000000; 7 State st[maxstadt],goal; 8 9 int dist[maxstadt]; 10 11 const int dx[] = {-1,1,0,0}; 12 const int dy[] = { 0,0,-1,1}; 13 14 /* 15 int vis[362880],fact[9]; 16 17 void init_lookup_table() { 18 fact[0] = 1; 19 for(int i=1;i<9;i++) 20 fact[i] = fact[i-1]*i; 21 } 22 23 int try_to_insert(int s) { 24 int code = 0; 25 for(int i=0;i<9;i++) { 26 int cnt = 0; 27 for(int j=i+1;j<9;j++) 28 if(st[s][j]
vis; 39 void init_lookup_table() {vis.clear();} 40 int try_to_insert(int s) { 41 int v = 0; 42 for(int i=0;i<9;i++) 43 v = v*10 + st[s][i]; 44 if(vis.count(v)) return 0; 45 vis.insert(v); 46 return 1; 47 } 48 */ 49 50 const int hashsize = 1000003; 51 int head[hashsize],next[hashsize]; 52 void init_lookup_table() {memset(head,0,sizeof(head));} 53 int hash(State& s) { 54 int v; 55 for(int i=0;i<9;i++) 56 v = v*10 + s[i]; 57 return v % hashsize; 58 } 59 60 int try_to_insert(int s) { 61 int h = hash(st[s]); 62 63 int u = head[h]; 64 while(u) { 65 if(memcmp(st[u],st[s],sizeof(st[s]))==0) return 0; 66 u = next[u]; 67 } 68 next[s] = head[h]; 69 head[h] = s; 70 return 1; 71 } 72 73 74 75 int bfs() { 76 init_lookup_table(); 77 int front=1,rear =2; 78 while(front
=0&&newx<3&&newy>=0&&newy<3) { 93 State& t = st[rear]; 94 memcpy(&t,&s,sizeof(s)); 95 96 t[newz] = s[z]; 97 t[z] = s[newz]; 98 dist[rear] = dist[front]+1; 99 if(try_to_insert(rear)) rear++;100 }101 }102 front++;103 }104 return 0;105 }106 107 int main()108 {109 freopen("in.txt","r",stdin);110 for(int i=0;i<9;i++)111 scanf("%d",&st[1][i]);112 113 for(int i=0;i<9;i++)114 scanf("%d",&goal[i]);115 116 int ans = bfs();117 if(ans>0)118 printf("%d\n",dist[ans]);119 else printf("-1\n");120 121 return 0;122 } int insert(/*结点*/ s) { int h = hash(str(s)); //hash值 int u = head[h]; //这个hash值对应的最后一个*结点*,也可以说是表头或者表尾,我个人理解表尾 while(u) { //依次检查 查到return 0; u = next[u]; } next[s] = head[h]; // 结点 s 的下一个结点 head[h] = s; return 1;}