#include using namespace std; bool endPositionIsPossible(int i_start, int j_start, int i_end, int j_end){ int row_diff = abs(i_start - i_end); return row_diff % 2 == 0 && (row_diff / 2) % 2 == abs(j_start - j_end) % 2; //row indexes must be 2 appart, column indexes diff can be odd or even the same as the number of rows } bool nextMoveIsValid(int n, int i, int j, vector pastPositions){ if(i >= 0 && j >= 0 && i < n && j < n && std::find(pastPositions.begin(), pastPositions.end(), i * 10 + j) == pastPositions.end()){ return true; } return false; } vector findShortestPath(int n, int i, int j, int i_end, int j_end, vectorpastPositions, string move_name, vector solution){ int i_next, j_next; pastPositions.push_back(i * 10 + j); //store current position if(move_name.size() != 0) { solution.push_back(move_name); } if(i == i_end && j == j_end){ //solution found return solution; } vector min_solution; vector possible_solution; if(solution.size() > n) { // entropy return min_solution; } i_next = i - 2; j_next = j - 1; if(nextMoveIsValid(n, i_next, j_next, pastPositions)){ min_solution = findShortestPath(n, i_next, j_next, i_end, j_end, pastPositions, "UL", solution); } i_next = i - 2; j_next = j + 1; if(nextMoveIsValid(n, i_next, j_next, pastPositions)){ possible_solution = findShortestPath(n, i_next, j_next, i_end, j_end, pastPositions, "UR", solution); if((possible_solution.size() != 0 && possible_solution.size() < min_solution.size()) || min_solution.size() == 0){ min_solution = possible_solution; } } i_next = i; j_next = j + 2; if(nextMoveIsValid(n, i_next, j_next, pastPositions)){ possible_solution = findShortestPath(n, i_next, j_next, i_end, j_end, pastPositions, "R", solution); if((possible_solution.size() != 0 && possible_solution.size() < min_solution.size()) || min_solution.size() == 0){ min_solution = possible_solution; } } i_next = i + 2; j_next = j + 1; if(nextMoveIsValid(n, i_next, j_next, pastPositions)){ possible_solution = findShortestPath(n, i_next, j_next, i_end, j_end, pastPositions, "LR", solution); if((possible_solution.size() != 0 && possible_solution.size() < min_solution.size()) || min_solution.size() == 0){ min_solution = possible_solution; } } i_next = i + 2; j_next = j - 1; if(nextMoveIsValid(n, i_next, j_next, pastPositions)){ possible_solution = findShortestPath(n, i_next, j_next, i_end, j_end, pastPositions, "LL", solution); if((possible_solution.size() != 0 && possible_solution.size() < min_solution.size()) || min_solution.size() == 0){ min_solution = possible_solution; } } i_next = i; j_next = j - 2; if(nextMoveIsValid(n, i_next, j_next, pastPositions)){ possible_solution = findShortestPath(n, i_next, j_next, i_end, j_end, pastPositions, "L", solution); if((possible_solution.size() != 0 && possible_solution.size() < min_solution.size()) || min_solution.size() == 0){ min_solution = possible_solution; } } return min_solution; } 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 pastPositions; vector path; if(endPositionIsPossible(i_start, j_start, i_end, j_end)){ path = findShortestPath(n, i_start, j_start, i_end, j_end, pastPositions, "", path); cout << path.size() << endl; for(vector::iterator it = path.begin() ; it != path.end() ; it++){ cout << *it << " "; } } else { cout << "Impossible"; } } 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; }