#include using namespace std; #define ll long long #define slld(x) scanf("%lld", &x) #define plld(x) printf("%lld\n", x) #define nl putchar('\n') #define ft first #define sd second #define mp make_pair #define pb push_back const ll MAX = (ll)(1e5+8); const ll MOD = (ll)(1e9 + 7); const ll inf = (ll)(1e15); //UL, UR, R, LR, LL, L char move_typ[6][4] = {"UL", "UR", "R", "LR", "LL", "L"}; ll dist[202][202], n; pair tmp, s, e; pair< pair, ll> par[203][203]; pair moves[6] = {mp(-2, -1), mp(-2, 1), mp(0, 2), mp(2, 1), mp(2, -1), mp(0, -2)}; inline bool is_val(ll x, ll y){ if(x>=0 && x=0 && y a, pair b){ return dist[a.ft][a.sd] > dist[b.ft][b.sd]; } priority_queue< pair > q; void dijkstra(pair x){ ll i, j, k; ll dx, dy; dist[x.ft][x.sd] = 0; for(i=0; i<6; i++){ dx = moves[i].ft, dy = moves[i].sd; dx = dx+x.ft, dy = dy+x.sd; if(is_val(dx, dy) && dist[dx][dy] > dist[x.ft][x.sd]+1){ dist[dx][dy] = dist[x.ft][x.sd]+1; q.push(mp(dx, dy)); par[dx][dy] = mp(mp(x.ft, x.sd), i); } } q.push(x); while(!q.empty()){ tmp = q.top(); q.pop(); //printf("%lld %lld\n", tmp.ft, tmp.sd); for(i=0; i<6; i++){ dx = moves[i].ft, dy = moves[i].sd; dx = dx+tmp.ft, dy = dy+tmp.sd; if(is_val(dx, dy) && dist[dx][dy] > dist[tmp.ft][tmp.sd]+1){ dist[dx][dy] = dist[tmp.ft][tmp.sd]+1; q.push(mp(dx, dy)); par[dx][dy] = mp(mp(tmp.ft, tmp.sd), i); } } } } vector< ll > stk; void get_moves(){ tmp = e; while(tmp != s){ stk.pb(par[tmp.ft][tmp.sd].sd); tmp = par[tmp.ft][tmp.sd].ft; } sort(stk.begin(), stk.end()); } void print_moves(){ ll i; for(i=0; i