#include using namespace std; int ROW,COL; int mat[203][203]; //to store matrix cell cordinates struct Point { int x; int y; }; Point parent[203][203]; // An Data Structure for queue used in BFS struct queueNode { Point pt; // The cordinates of a cell int dist; // cell's distance of from the source }; // check whether given cell (row, col) is a valid // cell or not. string dete(pair a,pair b) { int ax=a.first,ay=a.second,bx=b.first,by=b.second; if(ax-bx==-2&&ay-by==-1) return "UL"; else if(ax-bx==-2&&ay-by==1) return "UR"; else if(ax-bx==0&&ay-by==2) return "R"; else if(ax-bx==2&&ay-by==1) return "LR"; else if(ax-bx==2&&ay-by==-1) return "LL"; else if(ax-bx==0&&ay-by==-2) return "L"; return ""; } bool isValid(int row, int col) { // return true if row number and column number // is in range return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL); } // These arrays are used to get row and column // numbers of 4 neighbours of a given cell int rowNum[] = {-2,-2,0,2,2,0}; int colNum[] = {-1,1,2,1,-1,-2}; // function to find the shortest path between // a given source cell to a destination cell. int BFS( Point src, Point dest) { // check source and destination cell // of the matrix have value 1 if (!mat[src.x][src.y] || !mat[dest.x][dest.y]) return INT_MAX; bool visited[ROW][COL]; memset(visited, false, sizeof visited); // Mark the source cell as visited visited[src.x][src.y] = true; // Create a queue for BFS queue q; // distance of source cell is 0 queueNode s = {src, 0}; q.push(s); // Enqueue source cell // Do a BFS starting from source cell while (!q.empty()) { queueNode curr = q.front(); Point pt = curr.pt; // If we have reached the destination cell, // we are done if (pt.x == dest.x && pt.y == dest.y) return curr.dist; // Otherwise dequeue the front cell in the queue // and enqueue its adjacent cells q.pop(); for (int i = 0; i < 6; i++) { int row = pt.x + rowNum[i]; int col = pt.y + colNum[i]; // if adjacent cell is valid, has path and // not visited yet, enqueue it. if (isValid(row, col) && mat[row][col] && !visited[row][col]) { // mark cell as visited and enqueue it visited[row][col] = true; queueNode Adjcell = { {row, col}, curr.dist + 1 }; q.push(Adjcell); parent[row][col]={pt.x,pt.y}; } } } //return -1 if destination cannot be reached return INT_MAX; } // Driver program to test above function int main() { cin>>ROW; COL=ROW; for(int i=0;i<203;++i) for(int j=0;j<203;++j) mat[i][j]=1; int a,b,c,d;cin>>a>>b>>c>>d; Point source = {a,b}; Point dest = {c,d}; int dist = BFS( source, dest); if (dist != INT_MAX) { cout << dist< > s; while(sx!=a||sy!=b) { s.push({sx,sy}); int xw=parent[sx][sy].x; int xe=parent[sx][sy].y; sx=xw; sy=xe; } // cout< prev={a,b}; while(!s.empty()) { pair to=s.top(); // cout<