#include #include #include #include #include #include using namespace std; struct LengthStep { int length; string step; LengthStep() {} LengthStep(int length, const string& step) { this->length = length; this->step = step; } bool operator<(const LengthStep& other) { return (length < other.length || (length == other.length && step < other.step)); } }; unordered_map step_map; unordered_map number_map; unordered_map coord_map; queue > coord_queue; bool isValid(int x, int y, int n) { if (x < 0 || x >= n || y < 0 || y >= n) { return false; } return true; } void process(const pair& coord,int n) { LengthStep& actual = coord_map[(coord.first<<16)+coord.second]; int next_x; int next_y; next_x = coord.first - 1; next_y = coord.second - 2; if (isValid(next_x, next_y, n)) { auto it = coord_map.find((next_x << 16) + next_y); if(it!=end(coord_map)) { LengthStep& next = it->second; LengthStep updatednext(actual.length + 1, actual.step + step_map["UL"]); if (updatednext < next) { coord_map[(next_x << 16) + next_y] = updatednext; coord_queue.push(pair(next_x, next_y)); } } else { coord_map[(next_x << 16) + next_y] = LengthStep(actual.length + 1, actual.step + step_map["UL"]); coord_queue.push(pair(next_x, next_y)); } } next_x = coord.first + 1; next_y = coord.second - 2; if (isValid(next_x, next_y, n)) { auto it = coord_map.find((next_x << 16) + next_y); if (it != end(coord_map)) { LengthStep& next = it->second; LengthStep updatednext(actual.length + 1, actual.step + step_map["UR"]); if (updatednext < next) { coord_map[(next_x << 16) + next_y] = updatednext; coord_queue.push(pair(next_x, next_y)); } } else { coord_map[(next_x << 16) + next_y] = LengthStep(actual.length + 1, actual.step + step_map["UR"]); coord_queue.push(pair(next_x, next_y)); } } next_x = coord.first + 2; next_y = coord.second ; if (isValid(next_x, next_y, n)) { auto it = coord_map.find((next_x << 16) + next_y); if (it != end(coord_map)) { LengthStep& next = it->second; LengthStep updatednext(actual.length + 1, actual.step + step_map["R"]); if (updatednext < next) { coord_map[(next_x << 16) + next_y] = updatednext; coord_queue.push(pair(next_x, next_y)); } } else { coord_map[(next_x << 16) + next_y] = LengthStep(actual.length + 1, actual.step + step_map["R"]); coord_queue.push(pair(next_x, next_y)); } } next_x = coord.first + 1; next_y = coord.second+2; if (isValid(next_x, next_y, n)) { auto it = coord_map.find((next_x << 16) + next_y); if (it != end(coord_map)) { LengthStep& next = it->second; LengthStep updatednext(actual.length + 1, actual.step + step_map["LR"]); if (updatednext < next) { coord_map[(next_x << 16) + next_y] = updatednext; coord_queue.push(pair(next_x, next_y)); } } else { coord_map[(next_x << 16) + next_y] = LengthStep(actual.length + 1, actual.step + step_map["LR"]); coord_queue.push(pair(next_x, next_y)); } } next_x = coord.first - 1; next_y = coord.second + 2; if (isValid(next_x, next_y, n)) { auto it = coord_map.find((next_x << 16) + next_y); if (it != end(coord_map)) { LengthStep& next = it->second; LengthStep updatednext(actual.length + 1, actual.step + step_map["LL"]); if (updatednext < next) { coord_map[(next_x << 16) + next_y] = updatednext; coord_queue.push(pair(next_x, next_y)); } } else { coord_map[(next_x << 16) + next_y] = LengthStep(actual.length + 1, actual.step + step_map["LL"]); coord_queue.push(pair(next_x, next_y)); } } next_x = coord.first -2; next_y = coord.second ; if (isValid(next_x, next_y, n)) { auto it = coord_map.find((next_x << 16) + next_y); if (it != end(coord_map)) { LengthStep& next = it->second; LengthStep updatednext(actual.length + 1, actual.step + step_map["L"]); if (updatednext < next) { coord_map[(next_x << 16) + next_y] = updatednext; coord_queue.push(pair(next_x, next_y)); } } else { coord_map[(next_x << 16) + next_y] = LengthStep(actual.length + 1, actual.step + step_map["L"]); coord_queue.push(pair(next_x, next_y)); } } } 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. coord_queue.push(pair(j_start,i_start)); coord_map[(j_start << 16) + i_start] = LengthStep(0,""); while (!coord_queue.empty()) { pair& first = coord_queue.front(); if (first.first == j_end && first.second == i_end) { LengthStep& shortest = coord_map[(j_end<<16)+i_end]; cout<> n; int i_start; int j_start; int i_end; int j_end; in >> i_start >> j_start >> i_end >> j_end; printShortestPath(n, i_start, j_start, i_end, j_end); return 0; }