一操作拼接基于交换公式自动推导 中的代码V6更新了struct Opt的代码使得操作和操作可以自然的拼接起来。#include iostream #include string_view #include vector #include queue #include set #include map #include algorithm using namespace std; templatetypename T class GetSingleId { public: int id(T x) { auto it m.find(x); if (it ! m.end())return it-second; return m[x] n; } int num() { return n; } T getData(int id) { for (auto mi : m)if (mi.second id)return mi.first; return T{}; } private: mapT, intm; int n 0; }; templatetypename T class GetCombineId { public: vectorint combineId(vectorT x) { if (v.empty())v.resize(x.size()); vectorintans(x.size()); for (int i 0; i x.size(); i)ans[i] v[i].id(x[i]); return ans; } int id(vectorT x) { return v2.id(combineId(x)); } int num() { return v2.num(); } vectorT getData(int id) { vectorintids v2.getData(id); vectorTans(v.size()); for (int i 0; i v.size(); i)ans[i] v[i].getData(ids[i]); return ans; } private: vectorGetSingleIdTv; GetSingleIdvectorintv2; }; struct CubeBlock { int typeId;//角块棱块等分组id vectorintv;//一组块 CubeBlock() {} CubeBlock(int id, int n) { typeId id; v.resize(n); for (int i 0; i n; i)v[i] i;//每一组的块都按从0开始编号 } int changeNum() { int ans 0; for (int i 0; i v.size(); i) { if (v[i] ! i)ans; } return ans; } bool operator(const CubeBlock blocks)const { for (int i 0; i v.size() i blocks.v.size(); i) { if (v[i] blocks.v[i])return true; if (blocks.v[i] v[i])return false; } return false; } }; struct Opt { vectorvectorintv; string s; Opt operator(const Opt opt) { Opt ans; ans.v.resize(v.size()); for (int i 0; i v.size(); i) { ans.v[i].resize(v[i].size()); for (int j 0; j v[i].size(); j)ans.v[i][j] v[i][opt.v[i][j]]; } ans.s s opt.s; return ans; } void show() { for (int i 0; i v.size(); i) { for (int j 0; j v[i].size(); j)cout v[i][j] ,; cout \n; } cout 操作名 s \n; } }; class CubeOpt { public: CubeOpt(vectorCubeBlock b, Opt opt) :b{ b }, v{ opt.v }, s{ opt.s } {}//若干组块及其变换 CubeOpt operator (const CubeOpt opt) { b opt.b, v opt.v; return *this; } void change() { for (int i 0; i v.size(); i) { change(b[i], v[i]); } } void reback() { for (int i 0; i v.size(); i) { reback(b[i], v[i]); } } string getName() { return s; } private: void change(CubeBlock b, vectorint v)//一组块及一个变换如v[1]2表示把2号块移到1号块的位置 { vectorintbv b.v; for (int i 0; i v.size(); i) { b.v[i] bv[v[i]]; } } void reback(CubeBlock b, vectorint v) { vectorintbv b.v; for (int i 0; i v.size(); i) { b.v[v[i]] bv[i]; } } vectorvectorint v; vectorCubeBlock b; string s; }; mapint, stringmans; class Cube { public: Cube(vectorCubeBlock b, vectorCubeOpt opts) :b{ b }, opts{ opts } {} int bfs(int targetId, int difNumLow, int difNumHigh)//推导出一个公式 { queuevectorCubeBlockq; q.push(b); int k 0; while (!q.empty()) { k; // if (k % 10000 0)cout k q.size() ; b q.front(); q.pop(); if (ok(b, targetId, difNumLow, difNumHigh)) { for (auto bi : b) { for (int i 0; i bi.v.size(); i)cout bi.v[i] ,; cout \n; } showAns(m.id(b)); cout \n; } int id m.id(b); for (int i 0; i opts.size(); i) { auto opt opts[i]; opt.change(); int y m.num() - 1; if (m.id(b) y) { if (q.size() 100000) { q.push(b), fa[m.id(b)] id; } } opt.reback(); //if (q.size() % 10000 0)cout q.size() ; } } cout k k endl; return 0; } vectorvectorCubeBlock getAns(int id) { vectorvectorCubeBlockv; while (id) { v.insert(v.begin(), m.getData(id)); id fa[id]; } v.insert(v.begin(), m.getData(id)); return v; } void showAns(int ansId) { vectorvectorCubeBlock v getAns(ansId); for (int i 1; i v.size(); i) { for (int j 0; j opts.size(); j) { auto v1 v[i - 1], v2 v[i]; b v1; opts[j].change(); bool same true; for (int k 0; k v2.size(); k)if (v2[k] b[k] || b[k] v2[k])same false; if (same) { cout j mans[j] ; break; } if (j opts.size() - 1)cout ? ; } } cout endl; } private: bool ok(vectorCubeBlock b, int targetId, int difNumLow, int difNumHigh) { for (int i 0; i b.size(); i) { int c b[i].changeNum(); if (i ! targetId) { if (c)return false; } else { if (c difNumLow || c difNumHigh)return false; } } return true; } vectorCubeBlock b; vectorCubeOpt opts; GetCombineIdCubeBlockm; mapint, intfa; }; Opt Splice(const vectorOpt v, const vectorintid) { Opt ans v[id[0]]; for (int i 1; i id.size(); i)ans ans v[id[i]]; return ans; }Splice函数取代原来的test用于把一个长操作序列拼接起来。用法示例五阶齿轮魔方int main() { CubeBlock block1(0, 24);//24侧边区侧棱 CubeBlock block2(1, 24);//24中心区棱块 Opt opt1{ {{4,5,6,7,0,1,2,3,11,8,9,10,12,13,14,15,16,17,18,19,20,21,22,23}, {2,3,0,1,4,5,6,7,20,9,10,11,16,13,14,15,8,17,18,19,12,21,22,23} } ,op1 }; Opt opt2{ {{0,1,2,3,4,5,6,7,8,9,10,11,13,14,15,12,20,21,22,23,16,17,18,19}, {0,1,2,3,6,7,4,5,8,9,18,11,12,13,22,15,16,17,14,19,20,21,10,23} } ,op2 }; Opt opt3{ {{0,1,2,6,21,20,22,7,8,14,13,11,12,10,9,15,16,17,18,3,5,4,19,23} , {0,1,17,3,4,5,23,7,10,11,8,9,12,13,14,15,16,6,18,19,20,21,22,2} } ,op3 }; Splice({ opt1,opt2,opt3 }, { 0,0,0,1,2,0,0,1,1,2,0,0,2,2,0,1 }).show(); return 0; }输出0,1,2,3,4,5,6,7,13,12,15,14,9,8,11,10,16,17,18,19,20,21,22,23,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,18,17,16,19,22,21,20,23,操作名op1op1op1op2op3op1op1op2op2op3op1op1op3op3op1op2和test({ v1[1], v2[1],v3[1] }, { 0,0,0,1,2,0,0,1,1,2,0,0,2,2 ,0,1});的输出内容一致。