-Knight Parade-

Title description

The horse moves in Chinese chess according to the Japanese glyph rule, given a chessboard of n*m size, as well as the initial position (x, y) and target position (s, t) of the horse, it is required not to repeatedly pass the same one on the chessboardPoint, calculate how many steps the horse can take to reach the target position at least, and all chessboards ensure that there must be a path from the initial position to the end position.

Enter

The test data contains one row, which is six integers, which are the size of the chessboard and the initial position coordinate nmxyst.(1≤x, s≤n≤5, 1≤y, t≤m≤5)

Output

Contains one line, an integer that represents the minimum number of steps the horse can take to reach the target position.

Sample input

3 3 1 1 1 3

Sample output

2

Reference code:

#include
using namespace std;
int n,m;
int q[5000][2],x,y,s,t,hh,tt,kx,ky,l,gx,gy;
int dx[]={1,1,-1,-1,2,2,-2,-2};
int dy[]={2,-2,2,-2,1,-1,1,-1};
int d[50][50];
void bfs(){
while(hh!=tt){
kx=q[hh][1];
ky=q[hh][0];
hh++;
for(int i=0;i<8;i++){
int xx=kx+dx[i];
int yy=ky+dy[i];
if(xx>=0&&xx=0&&yy tt++;
q[tt-1][0]=yy;
q[tt-1][1]=xx;
d[yy][xx]=d[ky][kx]+1;
    
cin>>n>>m>>y>>x>>t>>s;
tt++;
d[y][x]=1;
q[0][1]=x-1;
q[0][0]=y-1;
bfs();
cout< return 0;
}