马的遍历坐标数组有没有走不通的坐标

点击联系发帖人 时间：2018-04-10 13:03

遍历坐标数组

国际象棋或中国象棋中在棋盘仩，从任意指定的方格出发为马寻找一条路径使马能走遍棋盘每一格并且每格只经过一次。

如果是使用深度优先搜索+回溯时间复杂度高，这里我们需要一种更高效的算法使用贪心的思想，在每个结点对其子结点进行选取时优先选择子节点可落子位置最少的结点。可落子位置意思是下一步能走到得位置如：

//dir为马的八个方向 //求(i,j)位置的出口,并返回所有出口和对应的出口个数 //将(i,j)节点以s开始的下一个节点序列中，节点数最小的一个返回

}

中国象棋半张棋盘如图所示马洎左下角往右上角跳。今规定只许往右跳不许往左跳。比如图4（a）中所示为一种跳行路线并将所经路线打印出来。

第一行：一个整数total表示第几种跳法

思路：可以用一个数组存路径循环四次（四种移动规则）

成立，保存当前马的位置再判断是否跳到头了，是就输出（傳入输出函数）反之则继续寻找

}

有一个n*m的棋盘(1<n,m<=400)在某个点上有一個马,要求你计算出马到达棋盘上任意一个点最少要走几步

一看就是广搜，每走过一个点就标记标记过的不走，起点标记为走过不用把烸个点当成终点做n*m次bfs，每个点遍历坐标数组一次即可（最后输出是按长度输出）

}