#include #include #include using namespace std; struct myNode{ int x; int y; int n; int heuristic; string routeInfo; }; int calcHeuristic(int x, int y, myNode end); void genMoves(set& vistedNodes, priority_queue,greater::value_type>>& pq, myNode fromNode, myNode end ); bool equalNodes(myNode node1, myNode node2); bool validnode(myNode node); 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. myNode endNode = {i_end,j_end,n,0,""}; myNode startNode = {i_start,j_start,n, calcHeuristic(i_start,j_start,endNode),""}; priority_queue,greater::value_type>> astarQ; set vistedNodes; queue route; astarQ.push(startNode); bool success = false; while(!astarQ.empty()){ myNode currentNode = astarQ.top(); astarQ.pop(); route.push(currentNode); vistedNodes.insert(currentNode); if(equalNodes(currentNode,endNode)){ success = true; break; } else{ genMoves(vistedNodes,astarQ,currentNode,endNode); } } if(success){ route.pop(); cout << route.size() << endl; while(!route.empty()){ cout << route.front().routeInfo << " "; route.pop(); } } else{ cout << "Impossible"; } } int calcHeuristic(int x, int y, myNode end){ int result = abs(x - end.x) + abs(y - end.y); return result; } void genMoves(set& vistedNodes, priority_queue,greater::value_type>>& pq, myNode fromNode, myNode end ){ myNode nodeList[6] = { {fromNode.x-2,fromNode.y-1,fromNode.n,calcHeuristic(fromNode.x-2,fromNode.y-1,end),"UL"}, {fromNode.x-2,fromNode.y+1,fromNode.n,calcHeuristic(fromNode.x-2,fromNode.y+1,end),"UR"}, {fromNode.x,fromNode.y+2,fromNode.n,calcHeuristic(fromNode.x,fromNode.y+2,end),"R"}, {fromNode.x+2,fromNode.y+1,fromNode.n,calcHeuristic(fromNode.x+2,fromNode.y+1,end),"LR"}, {fromNode.x+2,fromNode.y-1,fromNode.n,calcHeuristic(fromNode.x+2,fromNode.y-1,end),"LL"}, {fromNode.x,fromNode.y-2,fromNode.n,calcHeuristic(fromNode.x,fromNode.y-2,end),"L"} }; for(myNode theNode : nodeList){ if(validnode(theNode) && !vistedNodes.count(theNode)){ pq.push(theNode); } } } bool operator> (const myNode& node1, const myNode& node2){ return node1.heuristic > node2.heuristic; } bool validnode(myNode node){ if(node.x < 0 || node.y < 0 || node.x > (node.n-1) || node.y > (node.n-1)){ return false; } return true; } bool equalNodes(myNode node1, myNode node2){ int frst = (node1.x*node1.n)+node1.y; int scnd = (node2.x*node2.n)+node2.y; return frst == scnd; } bool operator<(const myNode& node1, const myNode& node2){ int frst = (node1.x*node1.n)+node1.y; int scnd = (node2.x*node2.n)+node2.y; return frst < scnd; } 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; }