七月第一周

骑士移动

题目描述：写程序，计算骑士从一个位置移动到另一个位置所需的最少移动次数。骑士移动的规则如下如所示。

每一次跳动，都可以有八种选择，经过多次正确选择后可以找到一个最近的路程。

算法设计：

这是一个求最短距离的问题，可以使用queue进行广度优先搜索步骤，现将起点放入队列，如果队列不空，则对头出对，否则扩展8个方向，如果找到目标，则立即返回步长+1并放入队列，标记其已访问，如果骑士的当前位置为（x，y），则移动时当前位置坐标加上偏移量即可。

输入：

3
8
0 0
7 0 
100
0 0
30 50
10
1 1
1 1

输出：

5
28
0

 代码：

#include<bits/stdc++.h>

int size ;
struct status{     #结构体
	int x;
	int y;
	int step;
}q[100006];

int vec[8][2]={
   {-2,-1},{-1,-2},{-2,1},{-1,2},{2,-1},{1,-2},{2,1},{1,2}};  #方向
int is[333][333];
void bfs(int sx,int sy,int ex,int ey){     #广度优先搜索
	int head =0,tail=0;
    memset(is,0,sizeof(is));
	q[tail].x=sx;
	q[tail].y=sy;
	is[sx][sy]=1;
	tail++;
	while (head<tail){
		if (q[head].x==ex&&q[head].y==ey){
				printf("%d\n",q[head].step);
				break ;
		}
		for(int i=0;i<8;i++){       #对各个方向进行遍历
			int nx=q[head].x+vec[i][0];
			int ny=q[head].y+vec[i][1];
			int step=q[head].step;
			if (nx>=0&&nx<size&&ny>=0&&ny<size&&is[nx][ny]==0){
				q[tail].x=nx;
				q[tail].y=ny;
				q[tail].step=step+1;
				is[nx][ny]=1;
				tail++;
			}	
		} 
		head ++;
	}
	
} 

int main(){
	int k;
	scanf("%d",&k);
	int sx,sy,ex,ey;
	while (k--){        #对每个要实现最短距离的目标进行遍历
		scanf("%d",&size);
		scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
		bfs(sx,sy,ex,ey);
	}
	return 0;
} 

YJG