#include using namespace std; struct direction{ int di; int dj; string name;//UL, UR, R, LR, LL, L } direc[7] = {{0,0, ""},{-2, -1, "UL"},{-2, 1, "UR"},{0, 2, "R"},{2, 1, "LR"},{2, -1, "LL"},{0, -2, "L"}}; struct record{ int i; int j; int d; }; bool findPath(vector> &chess, int i_start, int j_start, int i_end, int j_end){ int size = chess.size(); queue trav; trav.push(record{i_start, j_start, 0}); while(!trav.empty()){ int tsize = trav.size(); for(int k=0; k=size||cur.j<0||cur.j>=size) continue; if(chess[cur.i][cur.j]>=0)continue; chess[cur.i][cur.j] = cur.d; if(cur.i==i_end&&cur.j==j_end){ return true; } for(int i=1; i<=6; ++i){ trav.push(record{cur.i+direc[i].di, cur.j+direc[i].dj, i}); } } } return false; } 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. vector> chess(n, vector(n, -1)); vector path; if(findPath(chess, i_start, j_start, i_end, j_end)){ while(chess[i_end][j_end]!=0){ int index = chess[i_end][j_end]; path.push_back(index); i_end -= direc[index].di; j_end -= direc[index].dj; } cout<> 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; }