[C++知识库]蓝桥杯（跳马问题）【15ms2.531MB】

【问题描述】

一个8Ⅹ8的棋盘上有一个马初始位置为（a，b），他想跳到（c，d），问是否可以？如果可以，问最少要跳几步？

【输入格式】

一行数字a，b，c，d。

【输出格式】

如果跳不到，输出-1；否则输出最少跳到的步数。

【样例输入】

1 1 2 3

【样例输出】

1

【数据规模和约定】

0<a,b,c,d<=8且都是整数

【思路】

理论上只要一直走下去，每个点都能走到，所以不存在走不到的点。

建立一个二维数组path[][]，大小为9*9，用来存放到达该点所需要的最少步数

初始化数组每个元素为0，起点为-1，便于区分

其中每走一步都有8种走法：

----x+1，y+2(x+1<=8,y+2<=8)

----x-1，y+2(x-1>=0,y+2<=8)

----x+2，y+1(x+1<=8,y+2<=8)

----x-2，y+1(x+1>=0,y+2<=8)

----x+1，y-2(x+1<=8,y+2>=0)

----x-1，y-2(x-1>=0,y+2>=0)

----x+2，y-1(x+1<=8,y+2>=0)

----x-2，y-1(x+1>=0,y+2>=0)

定义初始步数为0，从起点开始所走的一步令其数组元素为n+1，以此类推；如果该点的值不为0，则不改变该点的元素值。

注意：输入的点为平面直角系的坐标，大小是从左到右，从下到上

而二维数组的大小是从左到右，从上到下。

但是这不影响最终结果，就是上下颠倒而已

a，c为横坐标，对应二维数组中的一维；b，d为纵坐标，对应二维数组中的二维。

写出来就是path[b][a],path[d][c]。编程的时候特别注意。

#include<stdio.h>
int main(){
	int a,b,c,d;
	scanf("%d %d %d %d",&a,&b,&c,&d);
	int path[9][9]={0},n=0;
	int i=b,j=a,mark=0;
	int k,l;
	path[b][a]=-1;
	if(a==c&&b==d){
		printf("%d",n);
	}
	while(a!=c||b!=d){
		n++;
		if(n!=1){
			for(k=1;k<9;k++){
			for(l=1;l<9;l++){
				if(path[k][l]==(n-1)){
					i=k;
					j=l;
		if(((i+1)<=8)&&((j+2)<=8)&&(path[i+1][j+2]==0)){
			path[i+1][j+2]=n;
		}
		if(((i-1)>=0)&&((j+2)<=8)&&(path[i-1][j+2]==0)){
			path[i-1][j+2]=n;
		}
		if(((i+2)<=8)&&((j+1)<=8)&&(path[i+2][j+1]==0)){
			path[i+2][j+1]=n;
		}
		if(((i-2)>=0)&&((j+1)<=8)&&(path[i-2][j+1]==0)){
			path[i-2][j+1]=n;
		}
		if(((i+1)<=8)&&((j-2)>=0)&&(path[i+1][j-2]==0)){
			path[i+1][j-2]=n;
		}
		if(((i-1)>=0)&&((j-2)>=0)&&(path[i-1][j-2]==0)){
			path[i-1][j-2]=n;
		}
		if(((i+2)<=8)&&((j-1)>=0)&&(path[i+2][j-1]==0)){
			path[i+2][j-1]=n;
		}
		if(((i-2)>=0)&&((j-1)>=0)&&(path[i-2][j-1]==0)){
			path[i-2][j-1]=n;
		}
		if(path[d][c]!=0){
			printf("%d",path[d][c]);
			mark=1;
		}		
				}
				if(mark==1){
					break;
				}	
			}
			if(mark==1){
					break;
				}
		}
		}
		if(n==1){
		if(((i+1)<=8)&&((j+2)<=8)){
			path[i+1][j+2]=n;
		}
		if(((i-1)>=0)&&((j+2)<=8)){
			path[i-1][j+2]=n;
		}
		if(((i+2)<=8)&&((j+1)<=8)){
			path[i+2][j+1]=n;
		}
		if(((i-2)>=0)&&((j+1)<=8)){
			path[i-2][j+1]=n;
		}
		if(((i+1)<=8)&&((j-2)>=0)){
			path[i+1][j-2]=n;
		}
		if(((i-1)>=0)&&((j-2)>=0)){
			path[i-1][j-2]=n;
		}
		if(((i+2)<=8)&&((j-1)>=0)){
			path[i+2][j-1]=n;
		}
		if(((i-2)>=0)&&((j-1)>=0)){
			path[i-2][j-1]=n;
		}
		if(path[d][c]!=0){
			printf("%d",path[d][c]);
			mark=1;
		}
		}
		if(mark==1){
			break;
		}
	}
	return 0;
}