#pragma GCC optimize ("O3") #pragma GCC target ("avx") #include "bits/stdc++.h" // define macro "/D__MAI" using namespace std; typedef long long int ll; #define xprintf(fmt,...) fprintf(stderr,fmt,__VA_ARGS__) #define debugv(v) {printf("L%d %s > ",__LINE__,#v);for(auto e:v){cout< ",__LINE__,#m);for(int x=0;x<(w);x++){cout<<(m)[x]<<" ";}cout<\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[y][x]<<" ";}cout< ostream& operator <<(ostream &o, const pair p) { o << "(" << p.first << ":" << p.second << ")"; return o; } template inline size_t argmin(iterator begin, iterator end) { return distance(begin, min_element(begin, end)); } template inline size_t argmax(iterator begin, iterator end) { return distance(begin, max_element(begin, end)); } template T& maxset(T& to, const T& val) { return to = max(to, val); } template T& minset(T& to, const T& val) { return to = min(to, val); } mt19937_64 randdev(8901016); inline ll rand_range(ll l, ll h) { return uniform_int_distribution(l, h)(randdev); } #define TIME chrono::system_clock::now() #define MILLISEC(t) (chrono::duration_cast(t).count()) struct State { int field[16]; inline int& operator()(int y, int x) { return field[y * 4 + x]; } inline int operator()(int y, int x) const { return field[y * 4 + x]; } inline bool is_satisfy() const { return is_sorted(field, field + 16); } int heuristic() const ; inline ll hash() const { ll h = 0; repeat(i, 16) h = (h << 4ll) | (ll)field[i]; return h; } void input() { repeat(i, 4) { string str; cin >> str; repeat(j, 4) field[4*i + j] = str[j] - 'A'; } } private: inline int at(int y, int x) { return field[y * 4 + x]; } }; struct Command { // R = 0, C= 1 int dir; int pos; int step; Command(int d, int p, int s) :dir(d), pos(p), step(s) { } Command(int h = 0) :dir(h >> 8), pos((h >> 4) & 15), step(h & 15) { } void apply(State& s) { if (dir == 0) { if (step == 1) swap(s(pos, 3), s(pos, 2)), swap(s(pos, 2), s(pos, 1)), swap(s(pos, 1), s(pos, 0)); if (step == 2) swap(s(pos, 0), s(pos, 2)), swap(s(pos, 1), s(pos, 3)); if (step == 3) swap(s(pos, 0), s(pos, 1)), swap(s(pos, 1), s(pos, 2)), swap(s(pos, 2), s(pos, 3)); } else { if (step == 1) swap(s(3, pos), s(2, pos)), swap(s(2, pos), s(1, pos)), swap(s(1, pos), s(0, pos)); if (step == 2) swap(s(0, pos), s(2, pos)), swap(s(1, pos), s(3, pos)); if (step == 3) swap(s(0, pos), s(1, pos)), swap(s(1, pos), s(2, pos)), swap(s(2, pos), s(3, pos)); } } void print() { if (dir == 0) printf("R"); else printf("C"); printf(" %d %d\n", pos, step); } inline int hash() const { return (dir << 8) | (pos << 4) | step; } }; int State::heuristic() const { int score = 0; repeat(i, 16) { // yoko score += (i / 4 * 4 <= field[i] && field[i] < i / 4 * 4 + 4); // tate score += (i%4 == field[i]%4); } return 0; } const int maxturn = 90; unordered_set mem_hash; int main() { State first_state; first_state.input(); if (first_state.is_satisfy()) cout << 0 << endl, exit(0); vector states; vector> previnfo; // prev_stateid, prev_command vector>> beams(maxturn); states.push_back(first_state); previnfo.emplace_back(0, 0); beams[0].emplace(0, 0); function finalize = [&](int stateid) { stack commands; while (stateid != 0) { auto p = previnfo[stateid]; commands.emplace(p.second); stateid = p.first; } printf("%d\n", (int)commands.size()); while (!commands.empty()) { commands.top().print(); commands.pop(); } }; for (auto btime = TIME; MILLISEC(TIME - btime) < 1990;) { for (int turn = 0; turn < maxturn; ++turn) { for (int beamidx = 0; beamidx < 5 && !beams[turn].empty(); ++beamidx) { int stateidx = beams[turn].top().second; beams[turn].pop(); State state = states[stateidx]; repeat(dir, 2) repeat( pos, 4) iterate(step, 1, 4) { Command command(dir, pos, step); State new_state = state; command.apply(new_state); ll h = new_state.hash(); if (mem_hash.count(h)) continue; mem_hash.insert(h); int new_stateid = states.size(); previnfo.emplace_back(stateidx, command.hash()); states.push_back(new_state); if (new_state.is_satisfy()) finalize(new_stateid), exit(0); if (turn + 1 < maxturn) beams[turn + 1].emplace(new_state.heuristic(), new_stateid); } } } } cout << "akan" << endl; return 0; }