马的遍历（算法设计与分析）

遍历（算法设计与分析）"/>

马的遍历（算法设计与分析）

任务描述

本关任务：编写一个马的遍历小程序。

题目描述

有一个5*4的棋盘，棋盘最左上角的坐标是(1,1)，棋盘最右下角的坐标是(5,4)。

在棋盘的某个位置放置一个中国象棋的马，按照中国象棋马的行棋规则，设计一个算法，求出马遍历棋盘上全部20个位置的行棋方式。

编程要求

根据提示，在右侧编辑器补充代码.
要求：在棋盘的（5,1）这个位置放置一个中国象棋的马，按照中国象棋马的行棋规则，设计一个算法，求出马遍历棋盘上全部20个位置的行棋方式

测试说明

平台会对你编写的代码进行测试：

测试输入：输入马的起始点坐标x,y: 2 1
预期输出：

• count=1
• 20 1 16 7 12
• 15 6 11 2 17
• 10 19 4 13 8
• 5 14 9 18 3
• count=2
• 12 1 16 7 20
• 17 6 11 2 15
• 10 13 4 19 8
• 5 18 9 14 3
• count=3
• 20 1 14 5 18
• 15 6 19 10 13
• 2 11 8 17 4
• 7 16 3 12 9
• count=4
• 12 1 16 5 20
• 17 6 13 10 15
• 2 11 8 19 4
• 7 18 3 14 9
• count=5
• 12 1 18 5 14
• 17 6 13 10 19
• 2 11 8 15 4
• 7 16 3 20 9
• count=6
• 20 1 16 9 12
• 15 8 11 4 17
• 2 19 6 13 10
• 7 14 3 18 5
• count=7
• 12 1 16 9 20
• 17 8 11 4 15
• 2 13 6 19 10
• 7 18 3 14 5

代码和思路如下：

#include<stdio.h>
const int m=5,n=4;//定义此题中棋盘大小
int fx[8]={1,2,2,1,-1,-2,-2,-1};//定义马走的8个方向
int fy[8]={2,1,-1,-2,-2,-1,1,2};
int A[m+1][n+1];//如果为0表示当前节点未遍历过，非0值dep表示该节点为走的第dep步
int dep,x,y,count=0;;//分别表示第几步、横坐标、纵坐标、满足条件的棋盘数
bool check(int x,int y)
{//判断此时位置是否超出棋盘范围if(x>=1 && x<=m&& y>=1 &&y<=n &&(!A[x][y]))return true;elsereturn false;
}void output()
{printf("count=%d\n",count);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){printf("%3d",A[j][i]);}printf("\n");}printf("\n");
}void solve(int x,int y,int dep)
{int i,xx,yy;for(i=0;i<=7;i++){xx=x+fx[i];yy=y+fy[i];if(check(xx,yy)){A[xx][yy]=dep;if(dep==n*m)//当步数达到n*m时表示已走完每一个节点{count++;output();	}else{solve(xx,yy,dep+1);}A[xx][yy]=0;//将走过的点重置为未遍历过}}
}int main()
{//5 1 输入横纵坐标scanf("%d %d",&x,&y);if(x>m||y>n||x<1||y<1){printf("输入有误！\n");}else{A[x][y]=1;solve(x,y,2);// printf("%d\n",count);printf("");}
}

ps：马的遍历优先顺序可变，在此题中顺序为：
        向下跳两格，向右跳一格。
        逆时针旋转一周。 

希望对大家的学习有所帮助！