八数码
链接:
https://www.acwing.com/problem/content/847/
来源:
acwing
思路:
bfs题,用x记下每一次的"x",给定边界条件,上下左右各走一次,全部入队列,用unordered_map 储存每一次走的整个字符串,与b字符串相等直接结束。
ps:切记一定要用unordered_map(unordered_map / unordered_set 比map/set 快,不带排序功能)
#include <bits/stdc++.h>
using namespace std;
string a;
string b="12345678x";
unordered_map<string,int> m;//比 set 快,不带排序功能
string bk;
int c[5]= {1,3,-1,-3};
queue<string> q;
int main()
{ for(int i = 1 ; i <= 9 ; i++)
{
char r;
cin >> r;
a=a+r;
}
q.push(a);
m[a] = 0;
while(q.size())
{
string u = q.front();
q.pop();
if(u==b) {cout << m[u];return 0;}
int x;
for(int i = 0 ; i<u.size() ; i++){
if(u[i]=='x') {//寻找“x”
x = i;
}
}
for(int i = 0 ; i<4 ;i++){
if((x==0||x==3||x==6)&&i==2) continue;//边界条件
if((x==2||x==5||x==8)&&i==0) continue;//边界条件
int xx = x+c[i];
if(xx<0||xx>8)continue;//边界条件
bk = u;
swap(bk[xx],bk[x]);
if(m.find(bk)!=m.end())continue;//map记录过直接返回
m[bk]=m[u]+1;
q.push(bk);
}
}
cout << -1;
return 0;
}