Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <string>
- #include <map>
- #include <queue>
- #include <cassert>
- #include <array>
- struct State {
- char ful, fur, fdl, fdr;
- char lul, lur, ldl, ldr;
- char bul, bur, bdl, bdr;
- char rul, rur, rdl, rdr;
- char uul, uur, udl, udr;
- char dul, dur, ddl, ddr;
- State rotateFCW() const {
- State res = *this;
- res.fur = ful;
- res.fdr = fur;
- res.fdl = fdr;
- res.ful = fdl;
- res.rul = udl;
- res.rdl = udr;
- res.dul = rdl;
- res.dur = rul;
- res.lur = dul;
- res.ldr = dur;
- res.udl = ldr;
- res.udr = lur;
- return res;
- }
- State rotateFCCW() const {
- State res = *this;
- res.ful = fur;
- res.fur = fdr;
- res.fdr = fdl;
- res.fdl = ful;
- res.udl = rul;
- res.udr = rdl;
- res.rdl = dul;
- res.rul = dur;
- res.dul = lur;
- res.dur = ldr;
- res.ldr = udl;
- res.lur = udr;
- // assert(res.rotateFCW() == *this)
- return res;
- }
- State rotateLCW() const {
- State res = *this;
- res.lur = lul;
- res.ldr = lur;
- res.ldl = ldr;
- res.lul = ldl;
- res.ful = uul;
- res.fdl = udl;
- res.dul = ful;
- res.ddl = fdl;
- res.bdr = dul;
- res.bur = ddl;
- res.uul = bdr;
- res.udl = bur;
- //assert(res.rotateLCCW() == *this);
- return res;
- }
- State rotateLCCW() const {
- State res = *this;
- res.lul = lur;
- res.lur = ldr;
- res.ldr = ldl;
- res.ldl = lul;
- res.uul = ful;
- res.udl = fdl;
- res.ful = dul;
- res.fdl = ddl;
- res.dul = bdr;
- res.ddl = bur;
- res.bdr = uul;
- res.bur = udl;
- // assert(res.rotateLCW() == *this);
- return res;
- }
- State rotateUCW() const {
- State res = *this;
- //assert(res.rotateUCCW() == *this);
- res.uur = uul;
- res.udr = uur;
- res.udl = udr;
- res.uul = udl;
- res.ful = rul;
- res.fur = rur;
- res.lul = ful;
- res.lur = fur;
- res.bul = lul;
- res.bur = lur;
- res.rul = bul;
- res.rur = bur;
- return res;
- }
- State rotateUCCW() const {
- State res = *this;
- res.uul = uur;
- res.uur = udr;
- res.udr = udl;
- res.udl = uul;
- res.rul = ful;
- res.rur = fur;
- res.ful = lul;
- res.fur = lur;
- res.lul = bul;
- res.lur = bur;
- res.bul = rul;
- res.bur = rur;
- //assert(res.rotateUCW() == *this);
- return res;
- }
- static State read() {
- State p;
- scanf(" %c%c %c%c %c%c %c%c %c%c %c%c", &p.ful, &p.fur, &p.lul, &p.lur, &p.bul, &p.bur, &p.rul, &p.rur, &p.uul, &p.uur, &p.dul, &p.dur);
- scanf(" %c%c %c%c %c%c %c%c %c%c %c%c", &p.fdl, &p.fdr, &p.ldl, &p.ldr, &p.bdl, &p.bdr, &p.rdl, &p.rdr, &p.udl, &p.udr, &p.ddl, &p.ddr);
- return p;
- }
- std::string to_string() const {
- char buf[25] = {};
- sprintf(buf, "%c%c%c%c%c%c%c%c%c%c%c%c", ful, fur, lul, lur, bul, bur, rul, rur, uul, uur, dul, dur);
- sprintf(buf+12, "%c%c%c%c%c%c%c%c%c%c%c%c", fdl, fdr, ldl, ldr, bdl, bdr, rdl, rdr, udl, udr, ddl, ddr);
- return buf;
- }
- bool isSolved() const {
- return
- ful == fur && ful == fdl && ful == fdr &&
- lul == lur && lul == ldl && lul == ldr &&
- bul == bur && bul == bdl && bul == bdr &&
- rul == rur && rul == rdl && rul == rdr &&
- uul == uur && uul == udl && uul == udr &&
- dul == dur && dul == ddl && dul == ddr;
- }
- };
- bool operator<(const State& left, const State& right) {
- if (left.ful < right.ful) return true;
- if (left.ful > right.ful) return false;
- if (left.fur < right.fur) return true;
- if (left.fur > right.fur) return false;
- if (left.fdl < right.fdl) return true;
- if (left.fdl > right.fdl) return false;
- if (left.fdr < right.fdr) return true;
- if (left.fdr > right.fdr) return false;
- if (left.lul < right.lul) return true;
- if (left.lul > right.lul) return false;
- if (left.lur < right.lur) return true;
- if (left.lur > right.lur) return false;
- if (left.ldl < right.ldl) return true;
- if (left.ldl > right.ldl) return false;
- if (left.ldr < right.ldr) return true;
- if (left.ldr > right.ldr) return false;
- if (left.bul < right.bul) return true;
- if (left.bul > right.bul) return false;
- if (left.bur < right.bur) return true;
- if (left.bur > right.bur) return false;
- if (left.bdl < right.bdl) return true;
- if (left.bdl > right.bdl) return false;
- if (left.bdr < right.bdr) return true;
- if (left.bdr > right.bdr) return false;
- if (left.rul < right.rul) return true;
- if (left.rul > right.rul) return false;
- if (left.rur < right.rur) return true;
- if (left.rur > right.rur) return false;
- if (left.rdl < right.rdl) return true;
- if (left.rdl > right.rdl) return false;
- if (left.rdr < right.rdr) return true;
- if (left.rdr > right.rdr) return false;
- if (left.uul < right.uul) return true;
- if (left.uul > right.uul) return false;
- if (left.uur < right.uur) return true;
- if (left.uur > right.uur) return false;
- if (left.udl < right.udl) return true;
- if (left.udl > right.udl) return false;
- if (left.udr < right.udr) return true;
- if (left.udr > right.udr) return false;
- if (left.dul < right.dul) return true;
- if (left.dul > right.dul) return false;
- if (left.dur < right.dur) return true;
- if (left.dur > right.dur) return false;
- if (left.ddl < right.ddl) return true;
- if (left.ddl > right.ddl) return false;
- if (left.ddr < right.ddr) return true;
- if (left.ddr > right.ddr) return false;
- return false;
- }
- bool operator>(const State& a, const State& b) {
- return b < a;
- }
- bool operator==(const State& a, const State& b) {
- return !(a < b || a > b);
- }
- bool operator!=(const State& a, const State& b) {
- return !(a == b);
- }
- int main() {
- //freopen("input.txt", "rt", stdin);
- std::map<State, State> from;
- State start = State::read();
- from[start] = start;
- std::queue<State> queue;
- queue.push(start);
- State t = start;
- //int count = 0;
- while (!queue.empty()) {
- State curr = queue.front(); queue.pop();
- if (++count % 10000 == 0) {
- printf("runned: %d\n", count);
- }
- /*
- if (curr.isSolved()) {
- t = curr;
- break;
- } */
- for (auto& next : {curr.rotateFCW(),
- curr.rotateFCCW(),
- curr.rotateUCW(),
- curr.rotateUCCW(),
- curr.rotateLCW(),
- curr.rotateLCCW()})
- {
- if (from.find(next) == from.end()) {
- from[next] = curr;
- queue.push(next);
- }
- }
- }
- printf("size = %d\n", (int)from.size());
- return 0;
- std::string answer = "";
- while (t != from[t]) {
- auto p = from[t];
- if (p.rotateFCW() == t) {
- answer = "F" + answer;
- } else if (p.rotateFCCW() == t) {
- answer = "F'" + answer;
- } else if (p.rotateUCW() == t) {
- answer = "U" + answer;
- } else if (p.rotateUCCW() == t) {
- answer = "U'" + answer;
- } else if (p.rotateLCW() == t) {
- answer = "L" + answer;
- } else if (p.rotateLCCW() == t) {
- answer = "L'" + answer;
- } else {
- throw std::runtime_error("Can not find rotation!");
- }
- t = p;
- }
- printf("%s", answer == "" ? "Solved" : answer.c_str());
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement