#include #include #include #include #include #import using namespace std; string moves[6] {"UL", "UR", "R", "LR", "LL", "L"}; vector made_moves; vector correct_path; int i, j, i_e, j_e, n, min_path_length = INT_MAX; bool** visited; inline bool isInBorders(int x, int y){ return x < n && x >=0 && y < n && y >= 0; } inline bool isVisited(int x, int y){ return visited[x][y]; } void visitIJ(){ visited[i][j] = true; } void unvisitIJ(){ visited[i][j] = false; } bool make_move(string direction, bool forward){ int ip, jp; if (direction == "UL"){ ip = -2; jp = -1; } else if (direction == "UR"){ ip = -2; jp = 1; } else if (direction == "R"){ ip = 0; jp = 2; } else if (direction == "LR"){ ip = 2; jp = 1; } else if (direction == "LL"){ ip = 2; jp = -1; } else if (direction == "L"){ ip = 0; jp = -2; } else { cout << "Impossible. direction = " << direction << endl; throw "Impossible"; } if (forward){ if (isInBorders(i+ip, j+jp) && !isVisited(i+ip, j+jp)){ i+=ip; j+=jp; visitIJ(); return true; } return false; } else { if (isInBorders(i-ip, j-jp)){ unvisitIJ(); i-=ip; j-=jp; return true; } return false; } } inline bool foundIt(){ return i == i_e && j == j_e; } void print_path(vector &path){ cout << path.size() << endl; cout << moves[path[0]]; for (int i = 1; i < path.size(); i++){ cout << " " << moves[path[i]]; } } void startGame(){ made_moves.push_back(0); while(made_moves[0] != 6){ if (foundIt() && made_moves.size()-1 < min_path_length){ made_moves.pop_back(); min_path_length = made_moves.size(); correct_path = made_moves; make_move(moves[made_moves.back()], false); made_moves.back()++; } else if( made_moves.back()==6 || made_moves.size()-1 >= min_path_length ){ made_moves.pop_back(); make_move(moves[made_moves.back()], false); made_moves.back()++; } else if(make_move(moves[made_moves.back()], true)){ made_moves.push_back(0); } else { made_moves.back()++; } } if (correct_path.empty()){ cout << "Impossible" << endl; }else{ print_path(correct_path); } } int main() { cin>>n>>i>>j>>i_e>>j_e; visited = new bool*[n]; for(int i = 0; i < n; i++) visited[i] = new bool[n](); visitIJ(); startGame(); return 0; }