#include #include #include #include #include #include #include using namespace std; struct Point { int i, j, dist; vector moves; bool const operator==(const Point & other) const { return i == other.i && j == other.j; } bool operator<(const Point &other) const { return i < other.i || (i == other.i && j < other.j); } }; // i, j pairs in terms of relative movement to the current position // i is the row, j is the col Point ALLOWED_MOVES[6] = { {-2, -1}, // UL: Up 2, left 1 {-2, 1}, // UR: Up 2, right 1 {0, 2}, // R: Up/down 0, right 2 {2, 1}, // LR: Down 2, right 1 {2, -1}, // LL: Down 2, left 1 {0, -2}, // L: Up/down 0, left 2 }; std::string MOVE_STRINGS[6] = { "UL", "UR", "R", "LR", "LL", "L" }; float distanceSq(int i, int j, int targ_i, int targ_j) { return std::pow(targ_i - i, 2) + std::pow(targ_j - j, 2); } bool isMoveValid(Point move_to, int n) { int i = move_to.i; int j = move_to.j; if (i < 0 || j < 0 || i >= n || j >= n) { return false; } return true; } 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. map visited; queue q; q.push({ i_start, j_start }); while (!q.empty()) { Point current = q.front(); q.pop(); int i_current = current.i; int j_current = current.j; int dist = current.dist; auto moves = current.moves; if (i_current == i_end && j_current == j_end) { // reached our destination! cout << dist << endl; for (auto move : moves) { cout << MOVE_STRINGS[move].c_str() << " "; } return; } if (!visited.count(current)) { visited[current] = true; for (int i = 0; i < 6; i++) { auto offset = ALLOWED_MOVES[i]; int new_i = i_current + offset.i; int new_j = j_current + offset.j; if (isMoveValid({ new_i, new_j }, n)) { Point new_p = { new_i, new_j, dist + 1 }; new_p.moves = moves; new_p.moves.push_back(i); q.push(new_p); } } } } // movement not possible std::cout << "Impossible" << std::endl; } 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; }