## sicily 1781 Knight 原

Ciel

### 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

``````2
1
0 0
0 0
10
0 1
8 9``````

### Sample Output

``````0
6``````

## 代码：

``````// Problem#: 1781
// Submission#: 1896080
// All Copyright reserved by Informatic Lab of Sun Yat-sen University
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

#define MAX 500

struct node{
int x, y, z;
node(int r, int s, int t){
x = r;
y = s;
z = t;
}
};

int n, a, b, c, d;
bool visit[MAX][MAX];
int move[8][2] = {{-2, -1}, {-1, -2}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {1, -2}, {2, -1}};

inline bool judge(int x, int y){
return x >= 0 && x < n && y >= 0 && y < n;
}

int bfs(){
queue<node> buffer;
memset(visit, false, sizeof(visit));
buffer.push(node(a, b, 0));
visit[a][b] = true;
while (!buffer.empty()) {
node tmp = buffer.front();
if (tmp.x == c && tmp.y == d)
return tmp.z;
buffer.pop();
for (int i = 0 ; i < 8 ; ++i) {
int tx = tmp.x + move[i][0];
int ty = tmp.y + move[i][1];
int tz = tmp.z + 1;
if (judge(tx, ty) && !visit[tx][ty]){
buffer.push(node(tx, ty, tz));
visit[tx][ty] = true;
}
}
}
return -1;
}

int main() {
int t;
cin >> t;
while (t--) {
cin >> n;
cin >> a >> b >> c >> d;
cout << bfs() << endl;
}
return 0;
}``````

### Ciel

--============Oracle ADG搭建============== --==========准备阶段========= 1.检查primary为archivelog模式。 select log_mode from v\$database; 如果为noarchivelog模式，切换到archivelo......

UltraSQL
2018/07/23
0
0
java程序CPU消耗分析之找出最耗CPU线程

java程序CPU消耗过高一般有两种情况： 1、us过高，应用占用CPU资源过高，需找出具体占用CPU的线程所执行的代码，分析定位问题原因。 分析步骤如下： (1) 使用top命令找出占用cpu最高的JAVA进...

2015/09/24
788
0
poj 2488 A Knight's Journey

dfs 注意字典序输出 1 12 34 3 Sample Output Scenario #1:A1 Scenario #2:impossible Scenario #3:A1B3C1A2B4C2A3B1C3A4B2C4 Source [Submit] [Go Back] [Status] [Discuss] /*============......

locusxt
2013/12/19
136
0
acm题目及我的程序（2）——Knight Moves (骑士跳跃)

acm题目，来源 http://acm.zju.edu.cn/show_problem.php?pid=1091 problem statement A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find th......

2012/03/09
1K
0
(webservice+cxf+mybatis+mysql+springmvc) webservice + cxf 能够跑起来的cxf ，来这里，，

curiousby
2015/10/16
0
0

Mybatis Plus删除

/** @author beth @data 2019-10-17 00:30 */ @RunWith(SpringRunner.class) @SpringBootTest public class DeleteTest { @Autowired private UserInfoMapper userInfoMapper; /** 根据id删除......

4
0

BobwithB

5
0
java内存模型

ls_cherish

4
0

5
0
js中实现页面跳转（返回前一页、后一页）

5
0