pku1915.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>

typedef struct 
{
	int x, y;
} Pos;

Pos q[91000];
int siz;
int dis[8][2] = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};
int head, tail;
int visit[301][301];
int weight;

int in(int x, int y)
{
	if (x < 0 || y < 0 || x >= siz || y >= siz)
	{
		return 0;
	}
	return 1;
}

int BFS(Pos s, Pos e)
{
	int i, j, head, tail, nextx, nexty;
	for (i = 0; i < 300; i++)
	{
		for (j = 0; j < 300; j++)
		{
			visit[i][j] = -1;
		}
	}
	visit[s.x][s.y] = 0;
	head = 0;
	tail = 0;
	q[0].x = s.x;
	q[0].y = s.y;
	do
	{
		weight = visit[q[head].x][q[head].y];
		for (i = 0; i < 8; i++)
		{
			nextx = q[head].x + dis[i][0];
			nexty = q[head].y + dis[i][1];
			if (in(nextx, nexty) && visit[nextx][nexty] == -1)
			{
				tail++;
				q[tail].x = nextx;
				q[tail].y = nexty;
				visit[nextx][nexty] = weight + 1;
			}
		}
		head++;
	}
	while (visit[e.x][e.y] == -1);
	return visit[e.x][e.y];
}

int main()
{
	Pos s, e;
	int T;
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d", &siz);
		scanf("%d%d%d%d", &s.x, &s.y, &e.x, &e.y);
		printf("%d\n", BFS(s, e));
	}
}