我定义了一个305 * 305 的数组,所以就算等于l,pos[sx][sy]也没有越界。只是队列里多了一组数据而已,应该不会影响答案。为什么不可以等于l?
题目原题()
描述
背景
Somurolov先生精彩的象棋玩家的确,声称任何人但他可以从一个位置到另一个骑士这么快。你能打败他吗?
问题
你的任务是写一个程序来计算一个骑士达到从另一点所需要的最少步数,这样你才有机会要比Somurolov快。
对于不熟悉象棋的人来说,可能的骑士动作如图1所示.。
输入
输入开始与一个单一的行本身的情况下。
下一步跟踪N个场景。每个场景由三行包含整数。第一行指定棋盘边的长度L(4 < L = < 300)。整个板尺寸L×L的第二和第三行包含整数对{ 0,…,L-1 } * { 0,…,L-1 }指定开始和结束位置的骑士。整数由一个空格隔开。您可以假定这些位置是该方案的棋盘上的有效位置.。
输出
对于输入的每一个场景,你必须计算从起点到终点的最小的骑士移动量.。如果起点和终点相等,距离为零。距离必须写在一行。
样例输入
3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1
样例输出
5
28
0
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
void bfs(int, int);
const int maxn = 305;
int t, n, l, x0, y0, fx, fy, pos[maxn][maxn], que[maxn * maxn][3];
int dx[8] = {2, 2, 1, -1, -2, -2, -1, 1};
int dy[8] = {-1, 1, 2, 2, 1, -1, -2, -2};
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
cin >> n;
while(t < n)
{
t++;
cin >> l >> x0 >> y0 >> fx >> fy;
memset(pos, -1, sizeof(pos)); memset(que, 0, sizeof(que));
bfs(x0, y0);
cout << pos[fx][fy] << endl;
}
return 0;
}
void bfs(int x, int y)
{
int head = 1, tail = 1;
que[1][0] = x; que[1][1] = y; que[1][2] = 0; pos[x][y] = 0;
while(head <= tail)
{
for(int i = 0; i < 8; i++)
{
int sx = que[head][0] + dx[i], sy = que[head][1] + dy[i];
if(sx >= 0 && sy >=0 && sx < l && sy < l && pos[sx][sy] == -1)
{
pos[sx][sy] = que[head][2] + 1;
tail++;
que[tail][0] = sx; que[tail][1] = sy; que[tail][2] = pos[sx][sy];
if(pos[fx][fy] >= 0)
{
head = tail;
//cout << pos[fx][fy] << endl;
break;
}
}
}
head++;
}
}