算法提高课-搜索-最小步数模型-AcWing 1107. 魔板：bfs、复杂、八数码类似的题目

题目分析

来源：acwing

分析：
最小步数模型常用哈希
按照ABC的顺序来搜，得到的是字典序最小的.

这里整幅“图”是一个状态， 装进一个字符串中，然后一个状态改变到另一个状态，相当于一幅图到另一幅图。

这里需要两个函数，set1()，把字符串设置到g[][]数组；get()从数组g[][]获取字符串，该字符串表达状态。

需要记录从初始状态转变到结果状态的最小步数，因此需要一个pre数组，来存前一状态和执行了什么状态，需要用pair来存<操作，状态>。然后整体是hash表的结果。具体请看代码。

ac代码

#include<bits/stdc++.h> using namespace std; typedef pair<int,int> PII; unordered_map<string,int> dist; // <到该状态，步数> unordered_map<string, pair<char, string> > pre; // <状态，<什么操作，上一状态>> queue<string> q; char g[2][4]; // 把string变回 g[][]数组 void set1(string state){for(int i = 0; i < 4; i ++) g[0][i] = state[i];for(int i = 3,j =4; i >= 0; i --,j++) g[1][i] = state[j]; }// 把g[][]数组变成string， string get(){string res;for(int i = 0; i < 4; i ++) res += g[0][i];for(int i =3; i >= 0; i --) res += g[1][i];return res; }string move0(string state){set1(state);for(int i = 0; i < 4; i ++) swap(g[0][i], g[1][i]); return get(); }string move1(string state){set1(state);char a = g[0][3], b = g[1][3];for(int i = 3; i >= 0; i --)for(int j = 0; j < 2; j++)g[j][i] = g[j][i-1];g[0][0] = a, g[1][0] = b;return get(); }string move2(string state){set1(state);char a= g[0][1];g[0][1] = g[1][1];g[1][1] = g[1][2];g[1][2] = g[0][2];g[0][2] = a;return get(); }void bfs(string start, string end){if(start == end) return;q.push(start);dist[start] = 0;while(q.size()){auto t = q.front();q.pop();string m[3]; // 3次扩展m[0] = move0(t);m[1] = move1(t);m[2] = move2(t);for(int i = 0; i < 3; i ++){string s = m[i];if(dist.count(s) == 0){dist[s] = dist[t] + 1;// 状态s 由谁变过来的：<操作，状态t>pre[s] = {(char)(i + 'A'), t};if(s == end) break;q.push(s);}}} }int main(){int x;string start, end;for(int i = 0; i < 8; i ++){cin >> x;end += (char)( x + '0');}for(int i = 1; i <= 8; i ++) start += (char)( i + '0');bfs(start, end);cout << dist[end] << endl;string res;while(end != start){res += pre[end].first;end = pre[end].second;}reverse(res.begin(), res.end());if(res.size() > 0) cout << res << endl; }

题目来源

https://www.acwing.com/problem/content/1109/

总结

以上是生活随笔为你收集整理的算法提高课-搜索-最小步数模型-AcWing 1107. 魔板：bfs、复杂、八数码类似的题目的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。