#include using namespace std; #define maxn 202 vector > > parent(maxn,vector< pair >(maxn)); vector< vector > parent_move(maxn,vector(maxn,-1)); vector > dp(maxn,vector(maxn,-1)); int e_x,e_y; string list_moves[6] = {"UL", "UR", "R", "LR", "LL", "L"}; bool is_safe(int x,int y, int x_max,int y_max) { return (x >= 0 && x < x_max && y >= 0 && y < y_max); } int dx[6]= {-2, -2, +0, +2, +2, +0}; int dy[6]= {-1, +1, +2, +1, -1, -2}; int vis[maxn][maxn]; long long int dpf(int n,int s_x,int s_y){ // cout << s_x << s_y << endl; if(s_x==e_x && s_y==e_y){ vis[s_x][s_y]=2; // cout << "final state" << endl; return (dp[s_x][s_y]=0); } if(dp[s_x][s_y]!=-1){ return dp[s_x][s_y]; } vis[s_x][s_y]=1; long long int min_path=LLONG_MAX; // cout <<"mp=" << min_path << endl; pair parent_t; int parent_move_t; long long int temp=LLONG_MAX; for(int i=0;i<6;i++){ int x_new = s_x + dx[i]; int y_new = s_y + dy[i]; // cout << s_x << s_y << "new ---- xy= "<< x_new << y_new << endl; // cout << vis[x_new][y_new] << endl; //back edge if(is_safe(x_new,y_new,n,n) && vis[x_new][y_new]!=1) { temp= dpf(n,x_new,y_new); // if(s_x==0 && s_y==3){ // cout << "xy= "<< x_new << y_new << endl; // cout << s_x << s_y << " temp=" << temp << endl; // } if(temp!=LLONG_MAX){ if(temp current_pair=make_pair(s_x,s_y); while(!(current_pair.first == e_x && current_pair.second==e_y)){ moves.push_back( parent_move[current_pair.first][current_pair.second] ); // cout << list_moves[parent_move[current_pair.first][current_pair.second]] << " "; current_pair = parent[current_pair.first][current_pair.second]; // cout << "xy= "<< current_pair.first << current_pair.second << endl; } sort(moves.begin(),moves.end()); for(auto x: moves){ cout << list_moves[x] << " "; } } return 0; }