#include template void PrintStack(std::stack> tmp) { std::cout << "Stack contents:"; while (0 != tmp.size()) { const auto el = tmp.top(); std::cout << " (" << el.first << "," << el.second << ")"; tmp.pop(); } std::cout << std::endl; } void PrintBoard(const std::vector>& board) { std::cout << "-------Board contents-------" << std::endl; for (const auto& r : board) { for (const auto& e : r) if (INT_MAX == e) std::cout << " -"; else std::cout << " " << e; std::cout << std::endl; } std::cout << "----------------------------" << std::endl; } bool ProcessOneMoreLevel(int n, std::stack>& current_level, std::stack>& next_level, int level, std::vector>& board) { //std::cout << "Process a level: " << level << std::endl; //PrintStack(current_level); //PrintBoard(board); bool target_reached = false; if (0 == current_level.size()) return false; while(0 != current_level.size()) { std::pair tmp = current_level.top(); current_level.pop(); int i = tmp.first; int j = tmp.second; //std::cout << "--" << i << " " << j << std::endl; if (((j+1) < n) && ((i-2) >= 0) && (INT_MAX == board[i-2][j+1])) { board[i-2][j+1] = level; next_level.push(std::make_pair(i-2, j+1)); } if (((j+2) < n) && (INT_MAX == board[i][j+2])) { board[i][j+2] = level; next_level.push(std::make_pair(i, j+2)); } if (((i+2) < n) && ((j+1) < n) && (INT_MAX == board[i+2][j+1])) { board[i+2][j+1] = level; next_level.push(std::make_pair(i+2, j+1)); } if (((i+2) < n) && ((j-1) >= 0) && (INT_MAX == board[i+2][j-1])) { board[i+2][j-1] = level; next_level.push(std::make_pair(i+2, j-1)); } if (((j-2) >= 0) && (INT_MAX == board[i][j-2])) { board[i][j-2] = level; next_level.push(std::make_pair(i, j-2)); } if (((i-2) >= 0) && ((j-1) >= 0) && (INT_MAX == board[i-2][j-1])) { board[i-2][j-1] = level; next_level.push(std::make_pair(i-2, j-1)); } } if (target_reached) return false; else return true; } void PrintPath(int n, int i, int j, const std::vector>& board) { /* if (((j+1) < n) && ((i-2) >= 0) && (INT_MAX != board[i-2][j+1])) { std::cout << " UR" << std::endl; PrintPath(n, i-2, j+1, board); } else if (((j+2) < n) &&(INT_MAX != board[i][j+2])) { std::cout << " R" << std::endl; PrintPath(n, i, j+2, board); } else if (((i+2) < n) && ((j+1) < n) && (INT_MAX != board[i+2][j+1])) { std::cout << " LR" << std::endl; PrintPath(n, i+2, j+1, board); } else if (((i+2) < n) && ((j-1) >= 0) && (INT_MAX != board[i+2][j-1])) { std::cout << " LL" << std::endl; PrintPath(n, i+2, j-1, board); } else if (((j-2) >= 0) && (INT_MAX != board[i][j-2])) { std::cout << " L" << std::endl; PrintPath(n, i, j-2, board); } else if (((i-2) >= 0) && ((j-1) >= 0) && (INT_MAX != board[i-2][j-1])) { std::cout << " UL" << std::endl; PrintPath(n, i-2, j-1, board); } else { // Something wrong exit(-1); } */ int min_dis = INT_MAX; std::string min_dir = ""; int new_i = 0; int new_j = 0; if (((i-2) >= 0) && ((j-1) >= 0) && (INT_MAX != board[i-2][j-1]) && (board[i-2][j-1] < min_dis)) { min_dis = board[i-2][j-1]; min_dir = "UL"; new_i = i - 2; new_j = j - 1; } if (((j+1) < n) && ((i-2) >= 0) && (INT_MAX != board[i-2][j+1]) && (board[i-2][j+1] < min_dis)) { min_dis = board[i-2][j+1]; min_dir = "UR"; new_i = i-2; new_j = j + 1; } if (((j+2) < n) &&(INT_MAX != board[i][j+2]) && (board[i][j+2] < min_dis)) { min_dis = board[i][j+2]; min_dir = "R"; new_i = i; new_j = j + 2; } if (((i+2) < n) && ((j+1) < n) && (INT_MAX != board[i+2][j+1]) && (board[i+2][j+1] < min_dis)) { min_dis = board[i+2][j+1]; min_dir = "LR"; new_i = i + 2; new_j = j + 1; } if (((i+2) < n) && ((j-1) >= 0) && (INT_MAX != board[i+2][j-1]) && (board[i+2][j-1] < min_dis)) { min_dis = board[i+2][j-1]; min_dir = "LL"; new_i = i + 2; new_j = j - 1; } if (((j-2) >= 0) && (INT_MAX != board[i][j-2]) && (board[i][j-2] < min_dis)) { min_dis = board[i][j-2]; min_dir = "L"; new_i = i; new_j = j - 2; } if ((-1 == new_i) && (-1 == new_j)) { // Something wrong exit(-1); } else { std::cout << min_dir; if (0 == min_dis) return; else std::cout << " "; PrintPath(n, new_i, new_j, board); } } 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. std::vector> board(n, std::vector(n, INT_MAX)); board[i_end][j_end] = 0; int level = 1; std::stack> current_level; std::stack> next_level; current_level.push(std::make_pair(i_end, j_end)); while (ProcessOneMoreLevel(n, current_level, next_level, level, board)) { current_level = std::move(next_level); level++; } if (INT_MAX == board[i_start][j_start]) std::cout << "Impossible" << std::endl; else { std::cout << board[i_start][j_start] << std::endl; PrintPath(n, i_start, j_start, board); } } int main() { int n; std::cin >> n; int i_start; int j_start; int i_end; int j_end; std::cin >> i_start >> j_start >> i_end >> j_end; printShortestPath(n, i_start, j_start, i_end, j_end); return 0; }