AcWing 1107. 魔板
原题链接
简单
作者:
Vertex
,
2023-02-13 22:10:37
,
所有人可见
,
阅读 144
#include <iostream>
#include <string>
#include <unordered_map>
#include <queue>
#include <algorithm>
using namespace std;
string base = "12348765";
string ma(string x) {
string ret(x);
for(int i = 0;i<4;i++) {
char xx = ret[i];
ret[i] = ret[i + 4];
ret[i + 4] = xx;
}
return ret;
}
string mb(string x) {
string ret(x);
char th3 = x[3];
char th7 = x[7];
for(int i = 3;i>=1;i--) {
ret[i] = ret[i - 1];
ret[i + 4] = ret[i + 3];
}
ret[0] = th3;
ret[4] = th7;
return ret;
}
string mc(string x) {
string ret(x);
char tmp = ret[6];
ret[6] = ret[2];
ret[2] = tmp;
tmp = ret[5];
ret[5] = ret[2];
ret[2] = tmp;
ret[2] = ret[1];
ret[1] = tmp;
return ret;
}
string start = "12348765";
unordered_map<string,pair<string,char> > mp;
queue<string> q;
int main() {
char x[100];
for(int i = 0;i<8;i++){
cin>>x[i];
start[i] = x[i];
}
string tmp = start;
start = base;
base = tmp;
reverse(base.begin()+4,base.end());
mp.insert({start,{"xx",0}});
q.push(start);
while(q.size()) {
string t = q.front();
q.pop();
string stra = ma(t);
string strb = mb(t);
string strc = mc(t);
if(mp.find(stra) == mp.end()) {
mp[stra] = {t,'A'};
q.push(stra);
if(stra == base) break;
}
if(mp.find(strb) == mp.end()) {
mp[strb] = {t,'B'};
q.push(strb);
if(strb == base) break;
}
if(mp.find(strc) == mp.end()) {
mp[strc] = {t ,'C'};
q.push(strc);
if(strc == base) break;
}
}
string cur(base);
string res = "";
while(mp[cur].first != "xx") {
pair<string,char> u = mp[cur];
res.insert(res.begin(),1,u.second);
cur = mp[cur].first;
}
cout<<res.size()<<"\n";
cout<<res;
return 0;
}