©2020-2024 ioDraw All rights reserved,
Privacy Policy
【问题描述】
一个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; }