c++ 骑士巡游（可实现4k的棋盘）

C++ 骑士巡游算法实现 C++ 骑士巡游算法是指使用 C++ 语言来实现骑士巡游问题的解决方案。骑士巡游问题是指在一个 N*N 的棋盘上，让骑士从某个起始点出发，按照 L 形移动，访问每个格子恰好一次，并最终回到起始点的问题。 在这个实现中，我们使用了回溯法和优化技术来实现骑士巡游问题的解决方案。回溯法是一种常用的搜索算法，它通过递归地搜索所有可能的路径来寻找解决方案。在这个实现中，我们使用了非递归的形式来避免递归深度的限制，从而可以实现 4000*4000 棋盘的骑士巡游。 优化技术是指我们使用的一些 trick 来提高算法的效率。例如，我们使用了棋盘的平移来减少搜索空间，并使用了排序来选择下一步的方向。这些优化技术使得我们的算法可以在 10s 内解决 4000*4000 棋盘的骑士巡游问题。 在这个实现中，我们定义了一个结构体 `dir_all` 来表示骑士的下一步选择。这个结构体包含三个成员变量：x、y 和 cnt，分别表示骑士的下一步位置和可行路径的数量。我们使用了一个数组 `dir` 来存储所有可能的 L 形移动方向。 在 `pruning` 函数中，我们使用了剪枝技术来减少搜索空间。我们首先遍历所有可能的 L 形移动方向，然后选择可行路径最少的方向作为下一步选择。这个函数返回一个数组 `d`，其中包含了所有可行的下一步选择。 在 `dfs` 函数中，我们使用了递归的方式来搜索所有可能的路径。但是，由于递归深度的限制，我们使用了非递归的形式来避免这个限制。在这个函数中，我们首先检查是否已经找到解决方案，如果找到则返回。否则，我们使用 `pruning` 函数来选择下一步的方向，并递归地调用 `dfs` 函数来搜索所有可能的路径。 在 `mydfs` 函数中，我们使用了非递归的形式来实现骑士巡游算法。我们首先将起始点 push 到栈中，然后使用循环来模拟递归的过程。在每次循环中，我们使用 `pruning` 函数来选择下一步的方向，并将下一步的位置 push 到栈中。如果找到解决方案，则返回。 我们使用了回溯法和优化技术来实现骑士巡游问题的解决方案，并使用了非递归的形式来避免递归深度的限制。我们的算法可以在 10s 内解决 4000*4000 棋盘的骑士巡游问题。