紫书上称这个方式为路径寻找问题，实际上，这个就是一个BFS和一个节点查找表的结合
这里先采用STL中的set来实现查找表。
在这道题中学到的东西主要是：
memxxxx等一系列内存管理函数的使用
首先是memxxx(a,b,size)
a是一个地址，b也是一个地址，size就是从这几个地址开始的几个字节
memcmp()函数，当对比成功后，返回0 所以特别的奇葩
memcpy()函数，比一个一个赋值快多了
然后是一个地址+一个常数，这个得看前面这个地址是什么数据类型的地址，最主要可以使用的地方是二维数组
假设有一个数组a[][],那么&a[0][0] + i,就是这个二维数组的第i个元素（从0开始）
另外，当发生内存冲突的时候，一般是发生了数组溢出或者用一个负数当作数组下标去访问数组
这个题目还涉及了使用数组来完成动态分配，这样，入队的时候，就可以只入队数组指针了
下面是实现的代码：
//总体思路就是，将每一个状态保存下来，然后由于每一个状态只有有限的选择，那么可以使用类似回溯法的思路，但是这类问题是没有明显的步骤数的 //其实就是一个bfs #include<cstdio> #include<iostream> #include<queue> #include<set> #include<cstring> using namespace std; struct state { int board[3][3]; }; const int maxn = 1000000; state st[maxn]; int fa[maxn]; int dis[maxn]; int cnt = 0; int start,goal; set<int>Set; int newstate() { ++cnt; memset(&st[cnt],0,sizeof(st[cnt]));//内存管理函数的参数必须是地址 if(cnt == 999999) printf("越界了！！！"); return cnt; } bool is_valid(int x) { int v = 0; for(int i = 0;i < 9;i++) { //cout<<&st[x].board[0][0]<<endl; //cout<<&st[x].board[0][0] + i<<endl; v = v * 10 + *(&st[x].board[0][0] + i); } if(Set.count(v)) return false; else { Set.insert(v); return true; } } int dc[] = {-1,1,0,0}; int dr[] = {0,0,1,-1}; int BFS() { queue<int>Q; Q.push(start); while(!Q.empty()) { int u = Q.front(); Q.pop(); if(memcmp(&st[u],&st[goal],36) == 0)//这函数怎么这么奇葩啊，不过后面的size参数确实是明白了 { return u; } int row,col; int find = 0; for(row = 0;row < 3;row++) { for(col = 0;col < 3;col++) { if(st[u].board[row][col] == 0) { find = 1; break; } } if(find) break; } for(int i = 0;i < 4;i++) { int r = row + dr[i]; int c = col + dc[i]; if(r < 3 && r >= 0 && c < 3 && c >= 0) { int v = newstate(); memcpy(&st[v],&st[u],sizeof(st[u])); st[v].board[r][c] = 0; st[v].board[row][col] = st[u].board[r][c]; if(is_valid(v)) { Q.push(v); fa[v] = u; dis[v] = dis[u] + 1; } } } } return 0; } bool read_input() { start = newstate(); for(int i = 0;i < 9;i++) { scanf("%d",&st[start].board[0][0] + i); } dis[start] = 0; goal = newstate(); for(int i = 0;i < 9;i++) { scanf("%d",&st[goal].board[0][0] + i); } return true; } int main() { freopen("input.txt","r",stdin); int ans; while(read_input()) { ans = BFS(); } return 0; }
原文：https://www.cnblogs.com/TorettoRui/p/10472737.html