首页 > 编程札记 > 编程

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

阅读：评论：0

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

任务描述

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

题目描述

有一个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=%dn",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("%dn",count);printf("");}
}