#include #include #include #include #include #include #include using namespace std; struct cell { int x, y; int dis; cell() {} cell(int x, int y, int dis) : x(x), y(y), dis(dis) {} }; // Utility method returns true if (x, y) lies inside Board bool isInside(int x, int y, int N) { if (x >= 0 && x < N && y >= 0 && y < N) return true; return false; } // Method returns minimum step to reach target position int minStepToReachTarget(int knightPos[], int targetPos[], int N,vector &vec) { // x and y direction, where a knight can move string str[]={"UL","UR","R","LR","LL","L"}; int dx[] = {-2,-2,0,2,2,0}; int dy[] = {-1,1,2,1,-1,-2}; // queue for storing states of knight in board queue q; // push starting position of knight with 0 distance q.push(cell(knightPos[0], knightPos[1], 0)); vec.push_back("S"); cell t; int x, y; //bool visit[N][N]; map,bool >mapper; // make all cell unvisited /* for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) visit[i][j] = false; */ // visit starting state //visit[knightPos[0]][knightPos[1]] = true; mapper[make_pair(knightPos[0],knightPos[1])]=true; // loop untill we have one element in queue while (!q.empty()) { t = q.front(); q.pop(); //visit[t.x][t.y] = true; mapper[make_pair(t.x,t.y)]=true; // if current cell is equal to target cell, // return its distance if (t.x == targetPos[0] && t.y == targetPos[1]) return t.dis; // loop for all reahable states for (int i = 0; i < 6; i++) { x = t.x + dx[i]; y = t.y + dy[i]; if(isInside(x,y,N)) { vec.push_back(str[i]); if(!mapper.count(make_pair(x,y))) { q.push(cell(x,y,t.dis+1)); mapper[make_pair(x,y)]=true; } vec.pop_back(); } // If rechable state is not yet visited and // inside board, push that state into queue /*if (isInside(x, y, N) && (!mapper.count(make_pair(x,y))) ) { q.push(cell(x, y, t.dis + 1)); vec.push_back(str[i]); */ // } //vec.pop_back(); } //vec.pop_back(); } return -1; } int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ int N,x,y,a,b; cin>>N; cin>>x>>y>>a>>b; int knightPos[2]; int targetPos[2]; knightPos[0]=x; knightPos[1]=y; targetPos[0]=a; targetPos[1]=b; vectorvec; int move=minStepToReachTarget(knightPos, targetPos, N,vec); if(move!=-1) { cout<