sicily 1781 Knight

Description

Your task is to write a program to calculate the minimum number of moves needed for a knight to reach one point from another. The possible knight moves are shown in Figure 1.

Figure 1 Possible knight moves on the board

Input

The first line contains an integer T (≤10), indicating the number of test cases.

In every case, the first line contains an integer N (≤500), indicating the size of the chess board (the entire board has size N × N). The second and third line contain pair of integers (srcR, srcC), and (dstR, dstC), specifying the starting and ending position of the knight on the board (0 ≤ srcR, srcC, dstR, dstC ≤ N – 1).

Output

For every case, output the minimum distance on a single line. If starting point and ending point are equal, distance is 0. If the knight can’t reach the ending point, distance is -1.

Sample Input

Sample Output

0
6

分析：

简单的BFS查找，注意判断状态是否合法即可。

代码：

 1 // Problem#: 1781
 2 // Submission#: 1896080
 3 // The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License
 4 // URI: http://creativecommons.org/licenses/by-nc-sa/3.0/
 5 // All Copyright reserved by Informatic Lab of Sun Yat-sen University
 6 #include <iostream>
 7 #include <queue>
 8 #include <cstring>
 9 using namespace std;
10 
11 #define MAX 500
12 
13 struct node{
14     int x, y, z;
15     node(int r, int s, int t){
16         x = r;
17         y = s;
18         z = t;
19     }
20 };
21 
22 int n, a, b, c, d;
23 bool visit[MAX][MAX];
24 int move[8][2] = {{-2, -1}, {-1, -2}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {1, -2}, {2, -1}};
25 
26 inline bool judge(int x, int y){
27     return x >= 0 && x < n && y >= 0 && y < n;
28 }
29 
30 int bfs(){
31     queue<node> buffer;
32     memset(visit, false, sizeof(visit));
33     buffer.push(node(a, b, 0));
34     visit[a][b] = true;
35     while (!buffer.empty()) {
36         node tmp = buffer.front();
37         if (tmp.x == c && tmp.y == d) 
38             return tmp.z;
39         buffer.pop();
40         for (int i = 0 ; i < 8 ; ++i) {
41             int tx = tmp.x + move[i][0];
42             int ty = tmp.y + move[i][1];
43             int tz = tmp.z + 1;
44             if (judge(tx, ty) && !visit[tx][ty]){
45                 buffer.push(node(tx, ty, tz));
46                 visit[tx][ty] = true;
47             }
48         }
49     }
50     return -1;
51 }
52 
53 int main() {
54     int t;
55     cin >> t;
56     while (t--) {
57         cin >> n;
58         cin >> a >> b >> c >> d;
59         cout << bfs() << endl;
60     }
61     return 0;
62 }