UC知道数据结构－－马踏棋盘问题
来源：百度知道 编辑：UC知道 时间：2024/05/26 12:53:35
有哪位高手可以帮小弟解决这个问题啊！不胜感激！！！
1、 国际象棋马的走法：先直走或横走一格，再沿离开原来格子的方向斜走二格，合起来为一步棋；国际象棋棋盘黑白交错，格数8×8。
2、基本要求
1) 给出马从任意一个位置出发遍历整个棋盘的一条路径。
2) 在1)的基础上给出从该位置出发的所有遍历路径
3、问题提示：
整个棋盘可表示为一个M×N的二维数组。假若马目前在位置（i,j）则马下一步可移动的位置0、1、……、7可分别表示为(i-2,j+1),(i-1,j+2),(i+1,j+2),(i+2,j+1),(i+2,j-1),(i+1,j-2), (i-1,j-2), (i-2,j-1)。当然，这些位置一定在棋盘边界以内（保证下一步移动位置坐标（i，j）,有0<i<M+1,0<j<N+1）。
格子具有集合性，故考虑使用无向图来表示格子及其间关系；以邻接表作为该无向图中结点与相邻8个结点（4黑4白）的存储结构；以顶点表存储格子，每格为顶点表中一结点，其指针域指向该顶点所能到达的第一个结点。
表头结点：
Vex x y link
Vex:头结点所在的序号
x:头结点所在的横坐标；
y:头结点所在的纵坐标；
link:指向Vex下一个能够到达的邻接结点
链表中结点的结构同表头结点的结构同。在此不一一赘述了；
假定我们按照以下方式对棋盘上的格子进行编号（如红色标注），那么编号与格子所在的坐标（如蓝色标注）位置必然存在一定关系。（留给大家思考）
1、 国际象棋马的走法：先直走或横走一格，再沿离开原来格子的方向斜走二格，合起来为一步棋；国际象棋棋盘黑白交错，格数8×8。
2、基本要求
1) 给出马从任意一个位置出发遍历整个棋盘的一条路径。
2) 在1)的基础上给出从该位置出发的所有遍历路径
3、问题提示：
整个棋盘可表示为一个M×N的二维数组。假若马目前在位置（i,j）则马下一步可移动的位置0、1、……、7可分别表示为(i-2,j+1),(i-1,j+2),(i+1,j+2),(i+2,j+1),(i+2,j-1),(i+1,j-2), (i-1,j-2), (i-2,j-1)。当然，这些位置一定在棋盘边界以内（保证下一步移动位置坐标（i，j）,有0<i<M+1,0<j<N+1）。
格子具有集合性，故考虑使用无向图来表示格子及其间关系；以邻接表作为该无向图中结点与相邻8个结点（4黑4白）的存储结构；以顶点表存储格子，每格为顶点表中一结点，其指针域指向该顶点所能到达的第一个结点。
表头结点：
Vex x y link
Vex:头结点所在的序号
x:头结点所在的横坐标；
y:头结点所在的纵坐标；
link:指向Vex下一个能够到达的邻接结点
链表中结点的结构同表头结点的结构同。在此不一一赘述了；
假定我们按照以下方式对棋盘上的格子进行编号（如红色标注），那么编号与格子所在的坐标（如蓝色标注）位置必然存在一定关系。（留给大家思考）
采用栈的结构(系统自带，递归就是)，使用深度优先搜索的方法来处理。
假设它现在正处在第（x,y）。
Procedure DFS(x,y)
Begin
for (x',y')∈{从(x,y)出发每一个只用走一步就可以到达的点} do
if not visited(x,y) then
begin
visited(x,y)<--TRUE
TheNumberOfThePointsThatNotVisited-1
if TheNumberOfThePointsThatNotVisited=1 then print
else DFS(x',y')
Visited(x,y)<--False
TheNumberOfThePointsThatNotVisited+1
end
值得一提的是：马每走一步，它所在的格子的颜色都会发生变化，一些棋盘一只马是可以遍历的，有的则不能。
032131313654