蓝桥杯算法训练 跳马_python试题 算法训练 跳马

一，题目描述

资源限制

内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s

问题描述

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

输入格式

　　一行四个数字a,b,c,d。

输出格式

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

样例输入

1 1 2 3

样例输出

1

数据规模和约定

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

二，解决思路

用一个二维数组chess表示棋盘，然后使用搜索算法，每到达一个点，就将代价加一（cost+1），并更新这个点的最小代价，将其存在chess数组中。

代码如下：

#include<iostream> 
#include<stdlib.h>
#include<time.h>
using namespace std;
int chess[8][8];
 
void search(int x,int y,int cost)//当前位于点(x,y)，从（a，b）到达（x，y）的当前最少步数为cost 
{
	//cout<<"("<<x <<","<<y <<"),"<<cost<<endl;
	if(x<0 || 7<x || y<0 || 7<y)return ;//越界就退出函数 
	if(chess[x][y] <10000){//去重 并更新邻接点 
		if(cost < chess[x][y])chess[x][y] = cost;//更新从（a，b）到达（x，y）的最少步数 
		
		int i,j;
		//下面这段for循环代码用来更新 从（a，b）到达（x，y）的八个邻点最少步数 
		for(i=-2;i<=2;i++)
			for(j=-2;j<=2;j++)
			{
				if(i == 0||j == 0)continue;//点(x+i,y+j) 这个点是当前点，不需再更新 
				if(0 <=i+x && i+x<=7 && 0 <=y+j && y+j<=7 && abs(i)+abs(j)==3)
				//上面这个if语句的前半段 0 <=i+x && i+x<=7 && 0 <=y+j && y+j<=7 是为了防止出界，
				//后半段是尝试用 (x+i,y+j)表示点(x,y)的八个邻点。 
				if(chess[i+x][y+j] > cost+1) chess[i+x][y+j] = cost+1;
			}
		return;
	}
	else{
		chess[x][y] = cost;
	}
	//八个方向递归 ，下一步的代价加一 
	search(x+2,y+1,cost+1);
	search(x+2,y-1,cost+1);
	search(x+1,y+2,cost+1);
	search(x+1,y-2,cost+1);
	
	search(x-2,y+1,cost+1);
	search(x-2,y-1,cost+1);
	search(x-1,y+2,cost+1);
	search(x-1,y-2,cost+1);
}
void solution(int a,int b,int c,int d)
{
	//clock_t begin = clock();
	int i,j;
	for(i=0;i<8;i++)
		for(j=0;j<8;j++)
			chess[i][j] = 10000;
	search(a-1, b-1, 0);
	if(chess[c-1][d-1] == 10000)cout<<"-1"<<endl;
	else cout<<chess[c-1][d-1];
	
	/*
	for(i=0;i<8;i++)
	{
		for(j=0;j<8;j++)
			cout<<chess[i][j]<<",";
		cout<<endl;
	}*/
	//clock_t end = clock();
	//cout<<end-begin<<endl;
}
int main()
{
	int a,b,c,d;
	//cout<<"test"<<endl;
	cin>>a>>b>>c>>d;
	
	solution(a,b,c,d);
	return 0;
}

运行效果：

 如有错误，敬请指正，礼貌交流，感激不尽。