// // main.cpp // Red Knight's Shortest Path // // Created by Abhishek Kumar Shakya on 16/12/17. // Copyright © 2017 Abhishek Kumar Shakya. All rights reserved. // #include #include #include using namespace std; long long num; // QItem for current location and distance // from source location class QItem { public: int row; int col; int dist; int a; QItem(int x, int y, int w, int z) : row(x), col(y), dist(w), a(z) { } }; int minDistance(int N,int M,int si,int sj,int di,int dj) { QItem source(0, 0, 0, 0); // To keep track of visited QItems. Marking // blocked cells as visited. bool visited[N][M]; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) visited[i][j] = false; } source.row = si; source.col = sj; // applying BFS on matrix cells starting from source queue q; q.push(source); visited[source.row][source.col] = true; while (!q.empty()) { QItem p = q.front(); q.pop(); // Destination found; if (p.row == di && p.col == dj){ num = p.a; return p.dist; } // moving UL if (p.row - 2 >= 0 && p.col - 1 >=0 && visited[p.row - 2][p.col - 1] == false) { q.push(QItem(p.row - 2, p.col - 1, p.dist + 1, p.a*10+1)); visited[p.row - 2][p.col - 1] = true; } // moving UR if (p.row - 2 >= 0 && p.col + 1 =0 && visited[p.row + 2][p.col - 1] == false) { q.push(QItem(p.row + 2, p.col - 1, p.dist + 1,p.a*10+5)); visited[p.row + 2][p.col - 1] = true; } // moving L if (p.col - 2 >=0 && visited[p.row][p.col - 2] == false) { q.push(QItem(p.row, p.col - 2, p.dist + 1,p.a*10+6)); visited[p.row][p.col - 2] = true; } } return -1; } // Driver code int main() { vector arr; int n,si,sj,di,dj; cin>>n; cin>>si>>sj>>di>>dj; int res = minDistance(n,n,si,sj,di,dj); if(res>0){ while(num>0){ int no = num%10; if(no == 1) arr.push_back("UL"); else if(no == 2) arr.push_back("UR"); else if(no == 3) arr.push_back("R"); else if(no == 4) arr.push_back("LR"); else if(no == 5) arr.push_back("LL"); else if(no == 6) arr.push_back("L"); num = num/10; } cout<=0;i--) cout<