#include #include #include #include #include #include #include #include using namespace std; class BoardField{ public: bool visited; int distance; pair prev; BoardField(){ visited = false; distance =0; prev = {-1,-1}; } static pair END; }; pair BoardField::END = {-1, -1}; class Solution { public: BoardField board[201][201]; int n; vector> moves = {{-2, -1}, {-2, 1}, {0, 2}, {2, 1}, {2, -1}, {0, -2}}; map, string> movesNamesMap = {{{-2, -1}, "UL"}, {{-2, 1}, "UR"}, {{0, 2}, "R"}, {{2, 1}, "LR"}, {{2, -1}, "LL"}, {{0, -2}, "L"}}; Solution(int n) : n(n) { } bool isLegalMove(pair pos, pair move){ int newY = pos.first + move.first; int newX = pos.second + move.second; return (newY >=0 && newY < n && newX >=0 && newX < n && !board[newY][newX].visited); } void BFS(pair start, pair end){ queue> Q; board[start.first][start.second].visited = true; board[start.first][start.second].distance = 0; Q.push(start); pair currentField; while(!Q.empty()){ currentField = Q.front(); Q.pop(); //cout << "BFS: " << currentField.first << " " << currentField.second << endl; for(auto move : moves){ if(isLegalMove(currentField, move)){ pair nextField = {currentField.first + move.first, currentField.second + move.second}; board[nextField.first][nextField.second].visited = true; board[nextField.first][nextField.second].prev = currentField; board[nextField.first][nextField.second].distance = board[currentField.first][currentField.second].distance + 1; if(nextField == end){ //cout << "THEEND " < start, pair end){ if(!board[end.first][end.second].visited){ cout << "Impossible" << "\n"; return; } vector path; BoardField currentField = board[end.first][end.second]; cout << currentField.distance << "\n"; pair currentPos = end; while(currentField.prev != BoardField::END){ int moveY = currentPos.first - currentField.prev.first; int moveX = currentPos.second - currentField.prev.second; path.push_back(movesNamesMap[{moveY, moveX}]); currentPos = currentField.prev; currentField = board[currentField.prev.first][currentField.prev.second]; } for(int i = path.size() - 1; i >=0 ; i--){ cout << path[i] << " "; } cout << "\n"; } void handleRequest(pair start, pair end){ BFS(start, end); printAnswer(start, end); } }; int main() { int n, startY, startX, endY, endX; cin >> n >> startY >> startX >> endY >> endX; Solution solution(n); solution.handleRequest({startY, startX},{endY, endX}); return 0; }