#include #include using namespace std; struct point { int i{}; int j{}; int w{}; }; static bool operator<(const point& p1, const point& p2) { return p1.w > p2.w;}; std::list genadjs(int n, const point &p) { std::list ret; //UL, UR, R, LR, LL, L. point ul = {p.i - 2, p.j - 1, 1}; point ur = {p.i - 2, p.j + 1, 2}; point r = {p.i, p.j + 2, 3}; point lr = {p.i + 2, p.j + 1, 4}; point ll = {p.i + 2, p.j - 1, 5 }; point l = {p.i, p.j - 2 , 6}; int i = 0; for(auto &point: {ul, ur, r, lr, ll, l}) { if(point.i >= 0 and point.j >=0 and point.i < n and point.j < n) { ret.push_back(point); } } return ret; } 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. //n x n //i - row //j - column int visited[n][n] {}; point prev[n][n]{}; visited[i_start][j_start] = true; std::priority_queue queue; queue.push(point{i_start, j_start, -1}); bool found = false; while(!queue.empty() and not found) { auto front = queue.top(); // std::cout << front.i << " " << front.j << "wei" << front.w << std::endl; queue.pop(); for(auto &adj : genadjs(n, front)) { if(adj.i == i_end and adj.j == j_end) { prev[adj.i][adj.j] = {front.i, front.j, front.w}; visited[adj.i][adj.j] = adj.w; found = true; } if(not visited[adj.i][adj.j]) { prev[adj.i][adj.j] = {front.i, front.j, front.w}; visited[adj.i][adj.j] = adj.w; queue.push(adj); } } } /* for(int i=0;i history; history.push_front(visited[i_end][j_end]); auto &pr = prev[i_end][j_end]; do { // std::cout << pr.i << " " << pr.j << " w " << visited[pr.i][pr.j] << "\n"; history.push_front(visited[pr.i][pr.j]); pr = prev[pr.i][pr.j]; } while (not (pr.i == i_start and pr.j == j_start)); std::cout << history.size() << std::endl; history.sort(); for(auto &a: history) { if(a == 1) { std::cout << "UL "; } else if(a == 2) { std::cout << "UR "; } else if(a == 3) { std::cout << "R "; } else if(a == 4) { std::cout << "LR "; } else if(a == 5) { std::cout << "LL "; } else { std::cout << "L "; } } } 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; }