A - 移动的骑士
Time Limit: 1000/1000MS (C++/Others) Memory Limit: 65536/65536KB (C++/Others)
Problem Description
Somurolov先生是一个国际象棋高手，他声称在棋盘上将骑士棋子从一点移动到另外一点，没有人比他快，你敢挑战他吗？
你的任务是编程计算出将一个骑士棋子从一点移动到另外一点，最少需要移动的步数。显而易见，这样你就有赢得Somurolov先生的机会。国际象棋中的骑士在棋盘上可移动的范围如下图：Input
首先输入测试样例的个数n。接下来是n组输入数据，每组测试数据由三行整数组成：第一行是棋盘的边长l (4 <= l <= 300)，整个棋盘的面积也就是 l*l；第二行和第三行分别是骑士棋子的初始位置和目标位置，表示为整数对形式{0, …, l-1}*{0, …, l-1}。保证棋子的初始和目标位置是棋盘上的合法位置。
Output
对于每一个输入的测试样例，请你算出骑士从初始位置移动到目标位置最小移动步数。如果初始位置和目标位置相同，那么骑士移动的距离就是0。最后单独一行输出所求距离。
Sample Input
3 8 0 0 7 0 100 0 0 30 50 10 1 1 1 1Sample Output
5 28 0
#include<cstdio> #include<cstring> #include<queue> using namespace std; const int maxn = 305; bool mp[maxn][maxn]; // 表示当前点是否被走过 int sx, sy, tx, ty, l; // s表示初始坐标，t表示目标位置 int tox[] = {1, 2, 2, 1, -1, -2, -2, -1}; int toy[] = {2, 1, -1, -2, -2, -1, 1, 2}; // 通过下标关联，表示马的八个走向 struct Node { // 结构体，表示当前点的坐标和到达步数 int x, y, s; }; bool judge(Node n){ // 用于判断一个坐标(x, y)是否在图内，并且没有被走过 if(n.x >=0 && n.x < l && n.y >= 0 && n.y < l && !mp[n.x][n.y]) return true; return false; } int bfs(){ Node now, nxt; queue<Node > q; now.x = sx; now.y = sy; now.s = 0; // 起始点的初始化 q.push(now); // 将起始点加入队列 mp[now.x][now.y] = true; // 起始点已经走过了 while(!q.empty()){ now = q.front(); q.pop(); if(now.x == tx && now.y == ty) return now.s; //到达目标点 for(int i=0; i<8; i++){ // 枚举马的八种走法 nxt.x = now.x + tox[i]; nxt.y = now.y + toy[i]; nxt.s = now.s + 1; if(judge(nxt)){ // 下一个位置在图内且可以走 q.push(nxt); // 加入队列 mp[nxt.x][nxt.y] = true; } } } return -1; } int main() { int n; scanf("%d", &n); while(n--){ memset(mp, false, sizeof(mp)); scanf("%d", &l); scanf("%d%d", &sx, &sy); scanf("%d%d", &tx, &ty); int ans = bfs(); printf("%d\n", ans); } return 0; }