題目分析

來(lái)源：acwing

分析：
最小步數(shù)模型常用哈希
按照ABC的順序來(lái)搜，得到的是字典序最小的.

這里整幅“圖”是一個(gè)狀態(tài)， 裝進(jìn)一個(gè)字符串中，然后一個(gè)狀態(tài)改變到另一個(gè)狀態(tài)，相當(dāng)于一幅圖到另一幅圖。

這里需要兩個(gè)函數(shù)，set1()，把字符串設(shè)置到g[][]數(shù)組；get()從數(shù)組g[][]獲取字符串，該字符串表達(dá)狀態(tài)。

需要記錄從初始狀態(tài)轉(zhuǎn)變到結(jié)果狀態(tài)的最小步數(shù)，因此需要一個(gè)pre數(shù)組，來(lái)存前一狀態(tài)和執(zhí)行了什么狀態(tài)，需要用pair來(lái)存<操作，狀態(tài)>。然后整體是hash表的結(jié)果。具體請(qǐng)看代碼。

ac代碼

#include<bits/stdc++.h> using namespace std; typedef pair<int,int> PII; unordered_map<string,int> dist; // <到該狀態(tài)，步數(shù)> unordered_map<string, pair<char, string> > pre; // <狀態(tài)，<什么操作，上一狀態(tài)>> queue<string> q; char g[2][4]; // 把string變回 g[][]數(shù)組 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[][]數(shù)組變成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次擴(kuò)展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;// 狀態(tài)s 由誰(shuí)變過(guò)來(lái)的：<操作，狀態(tài)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; }

題目來(lái)源

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

總結(jié)

以上是生活随笔為你收集整理的算法提高课-搜索-最小步数模型-AcWing 1107. 魔板：bfs、复杂、八数码类似的题目的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。