A70647. 马的遍历
编程题
提高
知识点
题目描述
中国象棋半张棋盘如图（a）所示。马自左下角往右上角跳。
今规定只许往右跳，不许往左跳，且要求马跳的方式按照（b）图顺时针深度优先递归。比如图（a）中所示为一种跳行路线。如果马要从 0,0 点，跳到 4,8 点，前 6 种跳法的打印格式如下，请参考前 6 种跳的方式，输出马从 0,0 点到 4,8 点所有可能的跳的路线。
1:0,0->2,1->4,2->3,4->4,6->2,7->4,8
2:0,0->2,1->4,2->3,4->1,5->3,6->4,8
3:0,0->2,1->4,2->3,4->1,5->2,7->4,8
4:0,0->2,1->4,2->2,3->4,4->3,6->4,8
5:0,0->2,1->4,2->2,3->4,4->2,5->4,6->2,7->4,8
6:0,0->2,1->4,2->2,3->4,4->2,5->0,6->2,7->4,8
输入格式
无
输出格式
按要求输出路径。
说明/提示
## 思路
「马的遍历」用深度优先搜索：沿一条路走到底再回溯，注意标记访问。
## 步骤
1. 读入图或网格。
2. 从起点 DFS，标记 vis，扩展相邻状态。
3. 在边界处更新答案或输出路径，回溯时恢复。
「马的遍历」用深度优先搜索：沿一条路走到底再回溯，注意标记访问。
## 步骤
1. 读入图或网格。
2. 从起点 DFS，标记 vis，扩展相邻状态。
3. 在边界处更新答案或输出路径，回溯时恢复。