#include using namespace std; bool notOutOfBounds(int i_move, int j_move, int n) { if ( (i_move > n || i_move < 0) || (j_move > n || j_move < 0)) return false; return true; } bool decreasedDistance (int i_move, int j_move, int i_start, int j_start, int i_dest, int j_dest) { int start_dist_i = abs(i_dest - i_start), start_dist_j = abs(j_dest - j_start), move_dist_i = abs(i_dest - i_move), move_dist_j = abs(j_dest - j_move); if(move_dist_i <= start_dist_i) { if(j_start == j_dest) //case where the dest and piece are on the same line { if (start_dist_i % 4 == 0) return true; else return false; } else if(move_dist_j <= start_dist_j) // normal case. both i j dist have to decrease return true; } return false; } void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { // Print the distance along with the sequence of moves. vector> possiblePaths; int i_initial = i_start, j_initial = j_start; for (int i = 0; i < 6; i++) // 6 for total possible moves { //cout << "new path" << endl; vector path; i_start = i_initial, j_start = j_initial; int UL_i = i_start - 2, UL_j = j_start - 1, UR_i = i_start - 2, UR_j = j_start + 1, R_i = i_start, R_j = j_start + 2, LR_i = i_start + 2, LR_j = j_start + 1, LL_i = i_start + 2, LL_j = j_start - 1, L_i = i_start, L_j = j_start - 2; // try every move as the first move switch(i) { case 0: i_start = UL_i; j_start = UL_j; path.push_back("UL "); break; case 1: i_start = UR_i; j_start = UR_j; path.push_back("UR "); break; case 2: i_start = R_i; j_start = R_j; path.push_back("R "); break; case 3: i_start = LR_i; j_start = LR_j; path.push_back("LR "); break; case 4: i_start = LL_i; j_start = LL_j; path.push_back("LL "); break; case 5: i_start = L_i; j_start = L_j; path.push_back("L "); break; } while (1) { UL_i = i_start - 2, UL_j = j_start - 1, UR_i = i_start - 2, UR_j = j_start + 1, R_i = i_start, R_j = j_start + 2, LR_i = i_start + 2, LR_j = j_start + 1, LL_i = i_start + 2, LL_j = j_start - 1, L_i = i_start, L_j = j_start - 2; if (i_start == i_end && j_start == j_end) { /*cout << "Winner Found" << endl; cout << i_start <<" " << j_start << " " << i_end<<" " << j_end<<" " << endl; for (int i = 0; i < path.size(); i++) { cout << path[i]; } cout<< endl;*/ possiblePaths.push_back(path); i_start = i_initial; j_start = j_initial; break; } else if (notOutOfBounds(UL_i, UL_j, n) && decreasedDistance(UL_i, UL_j, i_start, j_start, i_end, j_end)) { //cout << i_start <<" " << j_start << " " << i_end<<" " << j_end<<" " << endl; path.push_back("UL "); /*for (int i = 0; i < path.size(); i++) { cout << path[i]; } cout<< endl;*/ i_start = UL_i; j_start = UL_j; } else if (notOutOfBounds(UR_i, UR_j, n) && decreasedDistance(UR_i, UR_j, i_start, j_start, i_end, j_end)) { //cout << i_start <<" " << j_start << " " << i_end<<" " << j_end<<" " << endl; path.push_back("UR "); /*for (int i = 0; i < path.size(); i++) { cout << path[i]; } cout<< endl;*/ i_start = UR_i; j_start = UR_j; } else if (notOutOfBounds(R_i, R_j, n) && decreasedDistance(R_i, R_j, i_start, j_start, i_end, j_end)) { //cout << i_start <<" " << j_start << " " << i_end<<" " << j_end<<" " << endl; path.push_back("R "); /*for (int i = 0; i < path.size(); i++) { cout << path[i]; }*/ //cout<< endl; i_start = R_i; j_start = R_j; } else if (notOutOfBounds(LR_i, LR_j, n) && decreasedDistance(LR_i, LR_j, i_start, j_start, i_end, j_end)) { //cout << i_start <<" " << j_start << " " << i_end<<" " << j_end<<" " << endl; path.push_back("LR "); /*for (int i = 0; i < path.size(); i++) { cout << path[i]; } cout<< endl;*/ i_start = LR_i; j_start = LR_j; } else if (notOutOfBounds(LL_i, LL_j, n) && decreasedDistance(LL_i, LL_j, i_start, j_start, i_end, j_end)) { //cout << i_start <<" " << j_start << " " << i_end<<" " << j_end<<" " << endl; path.push_back("LL "); /*for (int i = 0; i < path.size(); i++) { cout << path[i]; }*/ //cout<< endl; i_start = LL_i; j_start = LL_j; } else if (notOutOfBounds(L_i, L_j, n) && decreasedDistance(L_i, L_j, i_start, j_start, i_end, j_end)) { //cout << i_start <<" " << j_start << " " << i_end<<" " << j_end<<" " << endl; path.push_back("L "); for (int i = 0; i < path.size(); i++) /*{ cout << path[i]; }*/ //cout<< endl; i_start = L_i; j_start = L_j; } else { i_start = i_initial; j_start = j_initial; break; } } } // end for //cout << "exit for" << possiblePaths.size()< path = possiblePaths[min]; cout << path.size() << endl; for (int i = 0; i < path.size(); i++) { cout << path[i]; } } } int main() { int n; cin >> n; int i_start; int j_start; int i_end; int j_end; cin >> i_start >> j_start >> i_end >> j_end; printShortestPath(n, i_start, j_start, i_end, j_end); return 0; }