八数码拼图（更新中）
题目描述
在 3\times 3 的棋盘上，摆有八个棋子，每个棋子上标有 1 至 8 的某一数字。棋盘中留有一个空格，空格用 0 来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为 123456780），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
类似题目：P1379 八数码难题 - 洛谷
我的解法
使用BFS找到出最短的路径并用map记录上一个状态
#include <bits/stdc++.h>
using namespace std;
#define M 100005
#define N 1005
#define MOD (1e9+7)
#define lowbit(x) (x & (-x))
int dx[8] = {0, 0, 1, -1, 1, -1, 1, -1};
int dy[8] = {1, -1, 0, 0, -1, 1, 1, -1};
#define int long long
vector<int> random() { //随机生成一组测试样例
vector<int> mp;
bool vis[11]={false};
while (mp.size()<9) {
std::random_device rd;
std::mt19937 generator(rd());
int r = generator();
r%=9;
if (vis[r]==0) {
mp.push_back(r);
vis[r]=true;
}
}
return mp;
}
void out1(string &v) {
// cout<<v<<"\n";
for (int i=0;i<v.size();i++) {
cout<<v[i]<<" ";
if ((i+1) %3==0) {
cout<<"\n";
}
}
cout<<"\n";
}
void out2(vector<int> &v) {
for (int i=0;i<v.size();i++) {
cout<<v[i]<<" ";
if ((i+1) %3==0) {
cout<<"\n";
}
}
}
bool check(vector<int> &v) { //检查
int sum=0;
for (int i=0;i<v.size();i++) {
for (int j=i+1;j<v.size();j++) {
if (v[i]>v[j]) {
sum++;
}
}
}
if (sum%2==1) return true;
return false;
}
bool ok(vector<int>&v) {
if (v.size()!=9) return false;
for (int i=0;i<v.size()-1;i++) {
if (v[i]!=i+1) return false;
}
if (v[v.size()-1]!=0) return false;
return true;
}
unordered_map<string,string> str;
int bfs(string st) {
string ed="123456780";//目标状态
queue<string> q;
unordered_map<string,int> mp;
q.push(st);
mp[st]=0;
str.clear();
while (!q.empty()) {
auto t=q.front();
auto be=t;
q.pop();
// cout<<t<<"\n";
int d=mp[t];
if (t==ed) {
return d;
}
int z=t.find('0');
int x=z/3,y=z%3;
for (int i=0;i<4;i++) {
int a=x+dx[i];
int b=y+dy[i];
if (a>=0&&a<3&&b>=0&&b<3) {
// string next=t;
swap(t[z],t[a*3+b]);
if (!mp.count(t)) {
mp[t]=d+1;
q.push(t);
str[t]=be;
}
swap(t[z],t[a*3+b]);
}
}
}
return -1;
}
string tostring(vector<int> v) {
string s;
for (int i=0;i<v.size();i++) {
s+=to_string(v[i]);
}
return s;
}
void solve() {
vector<int> v=random();
out2(v);
cout<<endl;
string s="123456780";
int d = bfs(tostring(v));
if (d==-1) {
cout << "NO" << endl;
return;
}else {
cout << "YES" << endl;
// return;
}
stack<string> st;
while (s!=tostring(v)) {//从原状态到目标状态 搜索路径并入栈
st.push(s);
s=str[s];
}
int n=st.size();
while (!st.empty()) { //输出路径
cout<<n-st.size()+1<<endl;
out1(st.top());
cout<< endl;
st.pop();
}
cout << d << endl;
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
int t = 1;
// std::cin >> t;
while (t--) {
solve();
}
return 0;
}
随机用例
7 4 6
0 8 5
1 2 3
YES
1
7 4 6
1 8 5
0 2 3
2
7 4 6
1 8 5
2 0 3
3
7 4 6
1 8 5
2 3 0
4
7 4 6
1 8 0
2 3 5
5
7 4 6
1 0 8
2 3 5
6
7 4 6
0 1 8
2 3 5
7
0 4 6
7 1 8
2 3 5
8
4 0 6
7 1 8
2 3 5
9
4 1 6
7 0 8
2 3 5
10
4 1 6
7 3 8
2 0 5
11
4 1 6
7 3 8
0 2 5
12
4 1 6
0 3 8
7 2 5
13
0 1 6
4 3 8
7 2 5
14
1 0 6
4 3 8
7 2 5
15
1 3 6
4 0 8
7 2 5
16
1 3 6
4 2 8
7 0 5
17
1 3 6
4 2 8
7 5 0
18
1 3 6
4 2 0
7 5 8
19
1 3 0
4 2 6
7 5 8
20
1 0 3
4 2 6
7 5 8
21
1 2 3
4 0 6
7 5 8
22
1 2 3
4 5 6
7 0 8
23
1 2 3
4 5 6
7 8 0
23