主要内容 #
- 问题描述
- 计算方法
- 参考代码
1. 问题描述 #
中国象棋半张棋盘如图(a)所示。马自左下角往右上角跳。现在规定只许往右跳,不许往左跳。比如图(a)中所示为一种跳行路线,并将所经路线打印出来。打印格式为:0,0->2,1->3,3->1,4->3,5->2,7->4,8…
2. 算法分析 #
如图(b),马最多有四个方向,若原来的横坐标为j、纵坐标为i,则四个方向的移动可表示为:
1: (i,j)→(i+2,j+1); (i<3,j<8)
2: (i,j)→(i+1,j+2); (i<4,j<7)
3: (i,j)→(i-1,j+2); (i>0,j<7)
4: (i,j)→(i-2,j+1); (i>1,j<8)
搜索策略:
- S1:A[1]:=(0,0);
- S2:从A[1]出发,按移动规则依次选定某个方向,如果达到的是(4,8)则转向S3,否则继续搜索下一个到达的顶点;
- S3:打印路径。
3. 参考程序 #
#include < iostream > using namespace std; int a[100][3]; // 路径 int t = 0; //路径总数 int x[4] = {2, 1, -1, -2}; //四种移动规则 int y[4] = {1, 2, 2, 1}; void search(int); //搜索的函数声明 void print(int); //打印的函数声明 int main(){ a[1][1] = 0; //从坐标(0, 0)开始向右跳第二步 a[1][2] = 0; search(2); return 0; } void search(int i){ for(int j = 0; j <= 3; ++j){ // 往四个方向跳 if(a[i-1][1] + x[j] >= 0 && a[i-1][1] + x[j] <= 4 && a[i-1][2] + y[j] <= 8 && a[i-1][2] + y[j] >= 0){ //判断马不越界 a[i][1] = a[i - 1][1] + x[j]; //保存当前马的位置 a[i][2] = a[i - 1][2] + y[j]; if(a[i][1] == 4 && a[i][2] == 8){ //到达右上角位置 print(i); }else{ search(i + 1); } } } } void print(int n){ for(int i = 1; i <= n - 1; ++i){ cout << a[i][1] << "," << a[i][2] << "-->"; } cout << "4,8" << endl; }