#include #include #include #include #include #include #include #include struct Path { // Initial -1 means "not visited" Path() : Path(-1, "") {} Path(int steps, std::string directions) : steps_{steps}, directions_{std::move(directions)} {} int steps_; std::string directions_; }; struct Position { bool operator==(const Position& rhs) const { return (i == rhs.i) && (j == rhs.j); } int i; int j; }; inline bool IsInBoard(Position cell, int board_width) { return (cell.i >= 0) && (cell.i < board_width) && (cell.j >= 0) && (cell.j < board_width); } inline bool IsVisited(Position cell, const std::vector> &paths) { return paths[cell.i][cell.j].steps_ > -1; } std::array GetNextCells(Position knight_position) { // Return in priority order (UL to L) return {{ Position{ knight_position.i - 2, knight_position.j - 1 }, Position{ knight_position.i - 2, knight_position.j + 1 }, Position{ knight_position.i, knight_position.j + 2 }, Position{ knight_position.i + 2, knight_position.j + 1 }, Position{ knight_position.i + 2, knight_position.j - 1 }, Position{ knight_position.i, knight_position.j - 2 } }}; } Path SolveBoard(int board_width, Position knight, Position goal) { // Store the number of steps and priority path to each cell in the board std::vector> paths(board_width); for (auto &row : paths) row.resize(board_width); // Initialize info at knight's position paths[knight.i][knight.j] = Path(0, ""); std::queue cells_to_check; cells_to_check.push(knight); // Use a breadth-first approach while (!cells_to_check.empty()) { const auto current_cell = cells_to_check.front(); cells_to_check.pop(); const auto next_cells = GetNextCells(current_cell); const std::array directions{{ "UL", "UR", "R", "LR", "LL", "L" }}; assert(next_cells.size() == directions.size()); for (int ii = 0; ii < next_cells.size(); ++ii) { // Fill path infor and add cell to check list if it hasn't been visited yet const auto &next_cell = next_cells[ii]; if (IsInBoard(next_cell, board_width) && !IsVisited(next_cell, paths)) { const auto& current_path = paths[current_cell.i][current_cell.j]; paths[next_cell.i][next_cell.j] = Path(current_path.steps_ + 1, current_path.directions_ + directions[ii] + " "); cells_to_check.push(next_cell); // If this cell is the goal, return the path info immediately if (next_cell == goal) { return paths[next_cell.i][next_cell.j]; } } } } return Path(-1, "Impossible"); } int main() { int board_width{0}; Position knight; Position goal; std::cin >> board_width >> knight.i >> knight.j >> goal.i >> goal.j; const auto solution = SolveBoard(board_width, knight, goal); if (solution.steps_ > -1) std::cout << solution.steps_ << std::endl; std::cout << solution.directions_ << std::endl; return 0; }