AcWing 845. 八数码
原题链接
中等
作者:
萌新米线
,
2021-05-14 21:48:56
,
所有人可见
,
阅读 274
题目描述
样例
算法1
(BFS) $O()$
C++ 代码
#include<iostream>
#include<algorithm>
#include<queue>
#include<unordered_map>
using namespace std;
int bfs(string start){
string end = "12345678x";
//队列与unordered_map容器记录的状态要区分开
queue<string> q;
unordered_map<string,int> d;//记录某一个状态与初始状态的距离
int dx[4] = {0,1,0,-1},dy[] = {1,0,-1,0};
q.push(start);
d[start] = 0;//初始状态到初始状态的距离是0
while( q.size() ){
auto t = q.front();
q.pop();
int distance = d[t];//记录状态t与初始状态的距离
if( t == end ) return distance;
//状态转移
int k = t.find('x');//记录x所在的一维位置
int x = k / 3,y = k % 3;//计算x所在的坐标
for( int i = 0; i < 4; ++i ){
int a = x + dx[i], b = y + dy[i];
if( a < 3 && a >= 0 && b < 3&& b >= 0 ){
swap(t[k],t[a*3+b]);
if( !d.count(t)){//当前更新的状态在之前没有搜到过
d[t] = distance + 1;
q.push(t);
}
swap( t[k],t[a*3+b]);
}
}
}
return -1;
}
int main(){
char c;
string start;
for( int i = 0; i< 9; ++i){
cin>>c;
start += c;
}
cout<<bfs(start)<<endl;
return 0;
}
兄弟有时间填个邀请码hhhhhhhhh(可以得AC币,邀请码在学生认证那填) 我的邀请码是:GUDFH