这道题说的是有一个象棋棋子马，走日字，问能从左上角开始，走的路径满足字典顺序(字母是字典顺序)，问是否能
走完所有的点，有则输出路径，注意，这里有的棋盘可以有很多种走法，但不是字典序列的，所以应该调整好搜索方案
代码如下：
#include <stdio.h>
#include <string.h>
//搜索过程中的路径
int path[100][22];
//搜索的下一跳方法
int dr[8][2] = {{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};
//标记搜索过程中，同一条路径中被标记的位置
int mark[27][27];
//行，列
int p, q;
//总的点数
int total;
//是否搜索成功
int flag;
//打印路径
void print(){
int i,j;
for(i = 1;i <= total;i++){
printf("%c%d", path[i][0] + 64, path[i][1]);
}
printf("
");
}
//用深度优先搜索查找合适的路径
void dfs(int num){
//当路径经过的点数为总数时，表示遍历完毕
if(num == total){
flag = 1;
print();
return;
}
if(flag){
return ;
}
//保存当前搜索点的位置
int x = path[num][0];
int y = path[num][1];
int i,j;
int xn, yn;
//探询8个不同的方向，尝试是否能实现搜索
for(i = 0;i < 8;i++){
//下一跳位置
xn = x + dr[i][0];
yn = y + dr[i][1];
//满足条件则可以作为路径
if(xn >=1 && xn <= q && yn >=1 && yn <=p && !mark[xn][yn]){
//当前这条路径遍历过了，就不能再遍历了，所以标记为已遍历过
mark[xn][yn] = 1;
//更新下一跳坐标，这里比较重要，不能用num += 1,这样做的错误是，
//因为这是一个循环，如果在这次给更新了num，那么下一次就是下一个点
//了，这就不是在一个点(x,y)来搜索不同的方向，而是下一个点开始搜索了
//所以需要更换变量名
int nnum = num + 1;
path[nnum][0] = xn;
path[nnum][1] = yn;
//进行下一步搜索
dfs(nnum);
//根据递归的思想，在进入dfs()函数到这里调用dfs()函数为止，一直是一条路径
//进行搜索，到这里时，应该走别的路径了，所以应该恢复标记
mark[xn][yn] = 0;
}
}
}
int main(){
int t;
scanf("%d", &t);
int i = 1;
for(i = 1;i <= t;i++){
scanf("%d%d", &p,&q);
total = p * q;
memset(path, 0, sizeof(path));
memset(mark, 0, sizeof(mark));
path[1][0] = 1;
path[1][1] = 1;
mark[1][1] = 1;
flag = 0;
printf("Scenario #%d:
",i);
dfs(1);
if(!flag){
printf("impossible
");
}
if(i < t){
printf("
");
}
}
return 0;
}
关于dfs的理解
准备条件：
1、实现寻找目标步骤的方法，即移动的方法
2、一个可以容纳所有可能节点的容器
3、一个用于存储遍历结果的路径的容器
方法：
1、运用递归函数，逐个遍历，将节点选择的地方放在递归函数内部，
当检测到当前节点可行时，需标记为访问过，并将改节点存入路径中，
然后继续寻找下一个可能的节点，找完后，应将遍历过的节点恢复，
因为有可能走别的路径时，要遍历这个节点。
2、在递归调用的同时，每次在入口测试是否达到目标状态，
如果达到目标状态，则将该路径做一个备份，但不能将其恢复默认值，
因为有的路径当不能到达目标节点时，会回溯到上一次，接着递归遍历，
所以会用到上一次的结果。