#include #include #include #include #include using namespace std; struct rcPos{ int r, c; rcPos(){ r=-1; c=-1; } rcPos(int i,int j){ r=i; c=j; } }; bool isFound(int r,int c,int n){ return (r>=0 && c>=0 && r>&parent,vector&path,int r,int c){ if(parent[r][c].r!=-1){ pathF(parent,path,parent[r][c].r,parent[r][c].c); } path.push_back(rcPos(r,c)); } int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ int n; cin>>n; vector>visited(n,vector(n,false)); vector>parent(n,vector(n)); vector>distance(n,vector(n,-1)); int sr,sc,fr,fc; cin>>sr>>sc>>fr>>fc; distance[sr][sc]=0; visited[sr][sc]=true; parent[sr][sc]=rcPos(-1,-1); queueq; q.push(rcPos(sr,sc)); while(!q.empty()){ int r,c,rr,cc; r=q.front().r; c=q.front().c; q.pop(); rr=r-2;cc=c-1; if(isFound(rr,cc,n) && !visited[rr][cc]){ visited[rr][cc]=true; parent[rr][cc]=rcPos(r,c); distance[rr][cc]=1+distance[r][c]; q.push(rcPos(rr,cc)); } rr=r-2;cc=c+1; if(isFound(rr,cc,n) && !visited[rr][cc]){ visited[rr][cc]=true; parent[rr][cc]=rcPos(r,c); distance[rr][cc]=1+distance[r][c]; q.push(rcPos(rr,cc)); } rr=r;cc=c+2; if(isFound(rr,cc,n) && !visited[rr][cc]){ visited[rr][cc]=true; parent[rr][cc]=rcPos(r,c); distance[rr][cc]=1+distance[r][c]; q.push(rcPos(rr,cc)); } rr=r+2;cc=c+1; if(isFound(rr,cc,n) && !visited[rr][cc]){ visited[rr][cc]=true; parent[rr][cc]=rcPos(r,c); distance[rr][cc]=1+distance[r][c]; q.push(rcPos(rr,cc)); } rr=r+2;cc=c-1; if(isFound(rr,cc,n) && !visited[rr][cc]){ visited[rr][cc]=true; parent[rr][cc]=rcPos(r,c); distance[rr][cc]=1+distance[r][c]; q.push(rcPos(rr,cc)); } rr=r;cc=c-2; if(isFound(rr,cc,n) && !visited[rr][cc]){ visited[rr][cc]=true; parent[rr][cc]=rcPos(r,c); distance[rr][cc]=1+distance[r][c]; q.push(rcPos(rr,cc)); } } //cout<path; pathF(parent,path,fr,fc); cout<