AcWing 1107. 魔板
原题链接
简单
作者:
十六
,
2021-01-14 17:09:49
,
所有人可见
,
阅读 275
#include<bits/stdc++.h>
using namespace std;
typedef pair<string, pair<string, int>> PII; //魔板-步骤-次数
string a, b;
int t, g[10];
set<string> st;
queue<PII> q;
void setg(string t){
for(int i=0; i<8; i++) g[i] = t[i]-'0';
}
string getg(){
string t = "";
for(int i=0; i<8; i++) t += g[i] + '0';
return t;
}
PII opA(PII t){
setg(t.first);
for(int i=0; i<4; i++) swap(g[i], g[7-i]);
return {getg(), {t.second.first+'A', t.second.second+1}};
}
PII opB(PII t){
setg(t.first);
for(int i=3; i>0; i--) swap(g[i], g[i-1]), swap(g[7-i], g[7-i+1]);
return {getg(), {t.second.first+'B', t.second.second+1}};
}
PII opC(PII t){
setg(t.first);
int tmp = g[1];
g[1] = g[6], g[6] = g[5], g[5] = g[2], g[2] = tmp;
return {getg(), {t.second.first+'C', t.second.second+1}};
}
PII bfs(){
q.push({a, {"", 0}});
st.insert(a);
while(q.size()){
PII t = q.front();
q.pop();
PII nt[3];
nt[0] = opA(t);
nt[1] = opB(t);
nt[2] = opC(t);
for(int i=0; i<3; i++){
if(nt[i].first==b) return nt[i];
if(st.count(nt[i].first)) continue;
st.insert(nt[i].first);
q.push(nt[i]);
}
}
return {"", {"", -1}};
}
int main(){
a = "12345678";
for(int i=0; i<8; i++){
scanf("%d", &t);
b += t+'0';
}
if(a==b) cout<< "0"<< endl;
else{
PII ans = bfs();
cout<< ans.second.second<< endl<< ans.second.first<< endl;
}
return 0;
}