A Knight‘s Journey 爆搜DFS

题目分析

拿到题目一看，立即想起了马走日，然而不是 写到后面发现就是个升级版马走日

题目大意分析：给定棋盘大小，移动棋子，寻路是否找到字典序路径能够遍历整个棋盘

马走日题目的要求则是：给定 n∗m 大小的棋盘，以及马的初始位置 (x，y)，要求不能重复经过棋盘上的同一个点，计算马可以有多少途径遍历棋盘上的所有点。

这不差不多嘛…但是字典序遍历很关键！我们需要先推导出如何走能够使字典序最小！

脑模一下棋盘，发现除了A1位置开始走，不可能再找到比A1位置开始更小字典序的路径了。

因此选择从A1开始遍历，优先向左遍历。至于遍历，我们一般采用喜闻乐见的数组储存增量的方式。由于向左走才能保证字典序最小，因此选择增量的顺序为：

( − 1 , − 2 ) , ( 1 , − 2 ) , ( − 2 , − 1 ) , ( 2 , − 1 ) , ( − 2 , 1 ) , ( 2 , 1 ) , ( − 1 , 2 ) , ( 1 , 2 ) (-1,-2),(1,-2),(-2,-1),(2,-1),(-2,1),(2,1),(-1,2),(1,2) (−1,−2),(1,−2),(−2,−1),(2,−1),(−2,1),(2,1),(−1,2),(1,2)

推导出走的路径来之后就是爆搜了：关于爆搜的思路整理请看[DFS总结-HeartFireY]https://blog.csdn.net/yanweiqi1754989931/article/details/109603384 PS：点个赞呗～

传坐标进去，用遍历深度作为搜索标志，深度 = 面积时遍历成功，flag标记一下状态，主函数输出一下路径或者失败。Over

偶对了，最好复制一下题目的输出，我漏了个冒号WA，检查了老半天

AC Code

#include 
#define xa x + a[i] //x方向进行移动
#define yb y + b[i] //y方向进行移动
using namespace std;
const int MAX_N = 27;
//字典序最小的方向增量
const int a[8] = {-1,1,-2,2,-2,2,-1,1};		//配合xa食用
const int b[8] = {-2,-2,-1,-1,1,1,2,2};		//配合yb食用
int vis[MAX_N][MAX_N];          //棋盘/访问记录数组
pair way[MAX_N];	//合法路径记录数组
int n, p, q, cnt = 0, flag = 0;

void dfs(int x, int y, int dep)
{
    way[dep].first = y + 'A' - 1, way[dep].second = x + '0';
    if (dep == p * q)
    {
        flag = 1;
        return;
    }
    for (int i = 0; i  0 && xa  0 && yb > n;
    while(n--){
        flag = 0, cnt++;
        cin >> p >> q;
        memset(vis, false, sizeof(vis));
        vis[1][1] = true; //起点
        dfs(1, 1, 1);
        cout