Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using ll = long long;
- using vll = vector<ll>;
- using pll = pair<ll,ll>;
- const int maxn=8;
- struct cube {
- ll a,b,c,d,e,f;
- cube() : a(0), b(0), c(0), d(0), e(0), f(0) {}
- cube(ll _a, ll _b, ll _c, ll _d, ll _e, ll _f) :
- a(_a), b(_b), c(_c), d(_d), e(_e), f(_f) {}
- bool operator < (const cube& other) const {
- if (a!=other.a) return a<other.a;
- if (b!=other.b) return b<other.b;
- if (c!=other.c) return c<other.c;
- if (d!=other.d) return d<other.d;
- if (e!=other.e) return e<other.e;
- if (f!=other.e) return f<other.f;
- return false;
- }
- cube colplus() {
- return {a,b,f,c,d,e};
- }
- cube colminus() {
- return {a,b,d,e,f,c};
- }
- cube rowminus() {
- return {c,e,b,d,a,f};
- }
- cube rowplus() {
- return {e,c,a,d,b,f};
- }
- };
- map<cube,ll> dp[8][8];
- using node = pair<pll,cube>;
- map<cube,node> pr[8][8];
- void dijkstra(ll ii, ll jj, cube c) {
- set<pair<ll,node>> st;
- dp[ii][jj][c] = c.e;
- pr[ii][jj][c] = {{ii,jj}, c};
- st.insert({c.e, {{ii,jj}, c}});
- // stop using c, i, j;
- while (!st.empty()) {
- pair<ll,node> item = *st.begin();
- st.erase(st.begin());
- pll p = item.second.first;
- ll d = item.first;
- c = item.second.second;
- if (dp[p.first][p.second][c] < d) continue;
- node thisnode = {p, c};
- node nextnode;
- cube c_next = c.colplus();
- nextnode.first.first = p.first;
- nextnode.first.second = p.second+1;
- nextnode.second = c_next;
- if (p.second < 7) { /////
- map<cube,ll> &mp = dp[p.first][p.second+1];
- if (mp.find(c_next) == mp.end() || mp[c_next] > d + c_next.e) {
- mp[c_next] = d + c_next.e;
- pr[p.first][p.second+1][c_next] = thisnode;
- st.insert({d+c_next.e,nextnode});
- }
- }
- c_next = c.colminus();
- nextnode.first.first = p.first;
- nextnode.first.second = p.second-1;
- nextnode.second = c_next;
- if (p.second > 0) { /////
- auto &mp = dp[p.first][p.second-1];
- if (mp.find(c_next) == mp.end() || mp[c_next] > d + c_next.e) {
- mp[c_next] = d + c_next.e;
- pr[p.first][p.second-1][c_next] = thisnode;
- st.insert({d+c_next.e,nextnode});
- }
- }
- c_next = c.rowplus();
- nextnode.first.first = p.first+1;
- nextnode.first.second = p.second;
- nextnode.second = c_next;
- if (p.first < 7) { /////
- auto &mp = dp[p.first+1][p.second];
- if (mp.find(c_next) == mp.end() || mp[c_next] > d + c_next.e) {
- mp[c_next] = d + c_next.e;
- pr[p.first+1][p.second][c_next] = thisnode;
- st.insert({d+c_next.e,nextnode});
- }
- }
- c_next = c.rowminus();
- nextnode.first.first = p.first-1;
- nextnode.first.second = p.second;
- nextnode.second = c_next;
- if (p.first > 0) { /////
- auto &mp = dp[p.first-1][p.second];
- if (mp.find(c_next) == mp.end() || mp[c_next] > d + c_next.e) {
- mp[c_next] = d + c_next.e;
- pr[p.first-1][p.second][c_next] = thisnode;
- st.insert({d+c_next.e,nextnode});
- }
- }
- }
- }
- vector<string> tr(vector<pll>& vl) {
- vector<string> ans;
- for (pll p: vl) {
- char r = p.first + '1';
- char c = p.second + 'a';
- string s; s.push_back(c); s.push_back(r);
- ans.push_back(s);
- }
- return ans;
- }
- int main() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- pll x,y; ll a,b,c,d,e,f;
- char cb;
- char ce;
- cin >> cb >> x.first >> ce >> y.first;
- cin >> a >> b >> c >> d >> e >> f;
- x.first--; y.first--;
- x.second = cb - 'a';
- y.second = ce - 'a';
- cube cc(a,b,c,d,e,f);
- dijkstra(x.first, x.second, cc);
- ll ans = 1e15;
- vector<pll> sol;
- pll pp;
- cube prevc;
- for (auto p: dp[y.first][y.second]) {
- if (p.second < ans) {
- ans = min(p.second, ans);
- prevc = p.first;
- }
- }
- pp.first = y.first; pp.second = y.second;
- while (pp.first != x.first || pp.second != x.second || prevc < cc || cc < prevc) {
- sol.push_back(pp);
- node myn = pr[pp.first][pp.second][prevc];
- prevc = myn.second;
- pp = myn.first;
- }
- sol.push_back(pp);
- reverse(sol.begin(), sol.end());
- vector<string> to_print = tr(sol);
- cout << ans;
- for (string s: to_print) cout << ' ' << s;
- cout << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement