八数码
8 题目 八数码
思路分析
实际上就是暴力枚举 看x的位置 分别去看它的上下左右四个方向有哪些合法 如果合法就进行交换 然后以交换后的结果作为一个分支 继续进行接下来的交换操作
直到某个时候 与目标状态匹配 就成功了 如果最终所有操作都完成 还没达到目标状态 则表示不能达到
起始状态： 为 1 2 3 x 4 6 7 5 8
交换一次：
x 与上方元素交换得到： x 2 3 1 4 6 7 5 8
x 与右方元素交换得到： 1 2 3 4 x 6 7 5 8
x 与下方元素交换得到： 1 2 3 7 4 6 x 5 8
交换两次得到：
2 x 3 1 4 6 7 5 8
1 x 3 4 2 6 7 5 8
1 2 3 4 6 x 7 5 8
1 2 3 4 5 6 7 x 8
1 2 3 7 4 6 5 x 8
交换三次得到：
2 3 x 1 4 6 7 5 8
.....
1 2 3 4 5 6 7 8 x
.....
得到了最终结果，输出 3.
问题主要在于 我们进行交换操作时是用二维数组的 而匹配时用一维的字符串要更方便
所以 关键就是 如何将二维和一维快速的进行转变
一维坐标映射到二维 -> (x / n, x % n )
二维映射一维 -> x * n + y
然后 在bfs里面 我们要求每个状态距离起点状态的距离（步数） 而现在的状态是string 而非某个xy坐标 用不了st数组或者dist数组 所以 可以使用哈希表 直接以string为键 做距离数组
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
string s;
unordered_map<string,int> dist;
queue<string> q;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
bool isVaild(int x,int y){
return x>=0 && x<=2 && y>=0 && y<=2;
}
void bfs(string s){
dist[s]=0;
q.push(s);
while(!q.empty()){
string cur=q.front();q.pop();
if(cur=="12345678x"){
cout<<dist[cur]<<endl;
return;
}
int pos=cur.find('x');
int ux=pos/3,uy=pos%3;
int last=dist[cur];
for(int i=0;i<4;i++){
int nx=ux+dx[i],ny=uy+dy[i];
if(isVaild(nx,ny)){
swap(cur[pos],cur[3*nx+ny]);
if(dist.find(cur)==dist.end()){//若存在 mp.find(x)!=mp.end() 不存在则反之为==
dist[cur]=last+1;
q.push(cur);
}
swap(cur[pos],cur[3*nx+ny]);//还原现场
}
}
}
cout<<-1<<endl;
return;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
for(int i=1;i<=9;i++){
char c; cin>>c;
s+=c;
}
bfs(s);
return 0;
}
💬 评论