八数码难题

题目

题解：

在一个棋盘中，有一个空白位置0，其他地方放了不同了数字1~9，在说明的部分中可以看出，可以通过移动0的位置，改变棋局位置。在答案中，可以把二维棋盘变成一维数组，便于判断是否和要求答案相同，也可以方便就行移位操作，这个就是状态压缩 

 同时搭配哈希表来记录数据减少了运行时间和空间，哈希表的作用就相当于一个存储数组，能够快速存储答案，而且可以快速查找的作用。

 使用 unordered_map 来存储字符串（状态）和整数（步数或其他信息）时，字符串和整数必须是一一对应的。

在使用unordered_map时，它只能存储两个数据一个key（键，状态，类似于本题的字符串），一个value（值，可以是一个数组，一个数，一个结构体）。

而键不能放二维数组，这也就是为什么题目要求压缩状态，让二维数组转换成一个字符串。

dist.count(t)的作用是检测t是否存在，如果存在，输出1，否则0。

我们如何通过字符串知道它对应的value,可以通过dist[t]来知道。

那我们知道key和value是一一对应的，那我们可以通过value来知道key吗？

答案是不行的。在题目中我们是这样定义的

unordered_map<string,int> dist;

这表明map中string正向映射int的。key对value是有单向映射性的。我们不能反向通过int来知道它对应的string。除非在定义时同时定义一个反向映射map，来反向读取另一个值

题解：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_map>
#include <queue>
#include <string>using namespace std;string s;
unordered_map<string,int> dist;
queue<string> q;int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};int bfs(string s){string end1 = "123804765";dist[s]=0;q.push(s);while(q.size()){auto t = q.front();q.pop();if(t == end1){return dist[t];}int distance = dist[t];int a = t.find('0');int x1 = a/3,y1=a%3;for(int i = 0;i<4;i++){int x2 = x1+dx[i];int y2 = y1+dy[i];if(x2<0 || x2>=3 || y2<0 || y2>=3) continue;int tmp = x2*3+y2;swap(t[a],t[tmp]);if(!dist.count(t)){dist[t] = distance + 1;q.push(t);}swap(t[a],t[tmp]);//恢复现场}}return -1;
}int main()
{cin >> s;int res = bfs(s);cout << res;return 0;
}