#include #include #include #include #include #include #include #include #include using namespace std; enum class MoveType: uint8_t { None = 0, UpperLeft = 1, UpperRight = 2, Right = 3, LowerRight = 4, LowerLeft = 5, Left = 6 }; const char* toString(MoveType type) { switch (type) { default : return ""; case MoveType::None : return ""; case MoveType::UpperLeft : return "UL"; case MoveType::UpperRight : return "UR"; case MoveType::Right : return "R"; case MoveType::LowerRight : return "LR"; case MoveType::LowerLeft : return "LL"; case MoveType::Left : return "L"; }; } struct Index { int row; int col; bool operator == (const Index& idx) const { return row == idx.row && col == idx.col; } Index move(MoveType type) const { switch (type) { default : return *this; case MoveType::UpperLeft : return Index{row - 2, col - 1}; case MoveType::UpperRight : return Index{row - 2, col + 1}; case MoveType::Right : return Index{row, col + 2}; case MoveType::LowerRight : return Index{row + 2, col + 1}; case MoveType::LowerLeft : return Index{row + 2, col -1}; case MoveType::Left : return Index{row, col - 2}; }; } Index reverse(MoveType type) const { switch (type) { default : return *this; case MoveType::UpperLeft : return move(MoveType::LowerRight); case MoveType::UpperRight : return move(MoveType::LowerLeft); case MoveType::Right : return move(MoveType::Left); case MoveType::LowerRight : return move(MoveType::UpperLeft); case MoveType::LowerLeft : return move(MoveType::UpperRight); case MoveType::Left : return move(MoveType::Right); }; } }; struct Visited: vector { Visited(int n): vector(n * n, MoveType::None), n(n) {} MoveType operator [](const Index& idx) const { return ((const vector&)(*this))[idx.row * n + idx.col]; } MoveType& operator [](const Index& idx) { return ((vector&)(*this))[idx.row * n + idx.col]; } const int n; }; int main() { string line; getline(cin, line); const int n = atoi(line.c_str()); getline(cin, line); istringstream is( line ); vector vals{istream_iterator(is), istream_iterator()}; Index start{vals[0], vals[1]}, end{vals[2], vals[3]}; auto valid = [n](const Index& idx) -> bool { return idx.row >= 0 && idx.row < n && idx.col >= 0 && idx.col < n; }; vector lvl, nxtLvl; lvl.reserve(n * 4); nxtLvl.reserve(n * 4); lvl.push_back(start); array moves{MoveType::UpperLeft, MoveType::UpperRight, MoveType::Right, MoveType::LowerRight, MoveType::LowerLeft, MoveType::Left}; Visited visited(n); int nLevels = 0; auto printPath = [&start, &end, &moves, &nLevels, &visited]() { vector moves; moves.reserve(nLevels); Index idx = end; while (!(idx == start)) { auto type = visited[idx]; moves.push_back(type); idx = idx.reverse(type); } cout << moves.size() << endl; for (auto it = moves.rbegin(), end = moves.rend(); it != end; ++it) { cout << toString(*it) << " "; } }; while(!lvl.empty()) { for (const Index& idx: lvl) { for (auto moveType: moves) { Index nxtIdx = idx.move(moveType); if( valid(nxtIdx) && visited[nxtIdx] == MoveType::None) { visited[nxtIdx] = moveType; nxtLvl.push_back(nxtIdx); if (nxtIdx == end) { printPath(); return 0; } } } lvl.pop_back(); } lvl.swap(nxtLvl); nxtLvl.resize(0); ++nLevels; } cout << "Impossible"; /* Enter your code here. Read input from STDIN. Print output to STDOUT */ return 0; }