马走棋盘之最短路径步数——C

描述问题

输入测试例子数T，每个例子输入棋盘大小m行n列, (1<=m,n<=500),再输入a,b,c,d表示(a,b)–>(c,d)，(1<=a,c<=m)且(1<=b,d<=n)且两点不是同一点，若马走的到，输出按照马的走法（日字走法）的 最短路径的步数，否则输出0。

分析问题

最短路径，让人联想到bfs，于是我们可以用队列，若未访问过，将可走的点放入队列中，直到队列为空之前，若走到则输出最短路径所走的步数，若队列已经空而仍然未到达目标，则输出0；

代码 + 注释

#include <stdio.h>
#include <stdlib.h> 
//注意，为方便数组访问，纵向为x轴，横向为y轴
typedef struct {
	int x;//x坐标
	int y;//y坐标
	int len;//步数
}node;

typedef node* Node;

int main() {
	
	int test_num;//测试例子数
	scanf("%d",&test_num);
	
	while(test_num --) {
		
		int m , n;
		scanf("%d %d",&m,&n);//m行n列的棋盘
		//使用calloc动态分配时已初始化为0，方便
		int **mark = (int **)calloc((m+1),sizeof(int *));
		for(int i = 0;i < m + 1;i ++) {
			mark[i] = (int *)calloc((n+1),sizeof(int));
		}//创建标记数组，记录哪些点已经访问过，1代表已访问，0代表未访问
		
		int a,b,c,d;
		scanf("%d %d %d %d",&a,&b,&c,&d);//输入坐标
		mark[a][b] = 1;//将起点标记为访问过
		
		int move_x[] = {-2,-1,1,2,2,1,-1,-2};
		int move_y[] = {1,2,2,1,-1,-2,-2,-1};
		//以上两个数组是对应每个点按照马字走法对应的x，y坐标的变化
		//比方说index（数组索引）为0时，代表(x-2,y+1)。
		Node queue = (Node)calloc(m*n+1,sizeof(node));//创建队列
		
		int head = 0,tail = 1;//head指向队列头，tail指向队列尾
		//这里不打算用queue[0],纯属个人习惯
		queue[1].x = a;
		queue[1].y = b;
		queue[1].len = 0;//让起点坐标入队列，由于马未开始动，步数为0
		
		int tag = 0;//标记是否走得到的变量
		
		while(head <= tail) {//队列非空时 

			head ++;//取出头结点使用,然后头结点出队
			
			for(int i = 0;i < 8;i ++) { //此处是为了遍历8个方向，即bfs

				//(queue[head].x + move_x[i] > 0)
				//横坐标不越界
				//(queue[head].y + move_y[i] > 0)
				//纵坐标不越界
				//(mark[queue[head].x + move_x[i]][queue[head].y + move_y[i]] == 0)
				//下一个方向所到达的点未访问过
				if(queue[head].x + move_x[i] > 0 
				&& queue[head].y + move_y[i] > 0 
				&& mark[queue[head].x + move_x[i]][queue[head].y + move_y[i]] == 0) {
				//满足上述三个条件马才可走到下一个方向所到的点
	
					tail ++;
					
					queue[tail].x = queue[head].x + move_x[i];
					
					queue[tail].y = queue[head].y + move_y[i];
					//可到达的点入队
					
					mark[queue[tail].x][queue[tail].y] = 1;
					//再标记当前到达的点为已访问
					
					queue[tail].len = queue[head].len + 1;
					//这一步是用于计算步数，注意每次8个方向搜索完之后，入队的结点的len值都是一样的，然后下一层搜索再让步数+1
					
					if(queue[tail].x == c && queue[tail].y == d) {//如果已经到达目标点
						printf("%d\n",queue[tail].len);
						//输出最短路径的步数
						tag = 1;
						//标记已经能够到达目标点
						break;
						//退出内层循环
					}
					
				}
			} 
			if(tag) break;//若找到点，退出外层循环
		}
		if(tag == 0) printf("0\n");
		//若队列已空，tag == 0代表不能到达，按照题意输出0；
		
		for(int i = 0;i < m + 1;i ++) {
			free(mark[i]);
		}
		free(mark);//释放
		free(queue);//释放
	}
	return 0;
}