Informatics Olympiad All-in-One (1257: Knight Moves)

1257: Knight Moves

Time Limit: 1000 ms Memory Limit: 65536 KB
Commits: 6149 Passes: 3100

【Title Description】

Enter nn to represent an n×n chessboard, enter the coordinates of the start position and the coordinates of the end position, and ask a knight to move the horse in the eight directions of the chessboardstep, how many steps can be passed from the start coordinate to the end coordinate.

[Enter]

First enter a nn, which represents the number of test samples.

There are three lines per test case.

The first line is the size L of the chessboard (4≤L≤300);

The second and third lines represent the starting and destination positions of the horse (0..L−1), respectively.

【Output】

The minimum number of steps the horse can move, output 00 when the starting position and the target position are the same.

【Sample input】

380 07 01000 030 50101 11 1

【Example of output】

5280

【Analysis】

Horse walking day, 8 directions, direction array (1,2),(1,-2),(-1,2),(-1,-2),(2,1),(2,-1),(-2,1),(-2,-1).

【Reference Code】

#include#include#includeusing namespace std;const int N=310;struct node{int x,y;int t;};int sx,sy; //Starting point coordinatesint ex,ey; //End point coordinatesint l; //chessboard sizeint dx[]={1,1,-1,-1,2,2,-2,-2}; //direction arrayint dy[]={2,-2,2,-2,1,-1,1,-1};bool vis[N][N]; //Access the arrayvoid bfs(){queue  q; //application queuenode st;st.x=sx;st.y=sy;st.t=0;q.push(st); //The starting point joins the queuewhile(!q.empty()){node nt=q.front();if(nt.x==ex && nt.y==ey){cout<=0 && nx=0 && ny>t;while(t--){memset(vis,false,sizeof(vis));cin>>l;cin>>sx>>sy>>ex>>ey;vis[sx][sy]=true;bfs();}}

http://ybt.ssoier.cn:8088/problem_show.php?pid=1257

a>