题目描述：

马在中国象棋中以日字形规则移动。请编写一段程序，给定 n×m 大小的棋盘以及马的初始位置 (x, y)，要求不能重复经过棋盘上的同一个点，计算马可以有多少途径遍历棋盘上的所有点。

输入：

第一行输入一个整数 T (T < 10)，表示测试数据的组数。

每一组测试数据包含一行，四个整数，分别为棋盘的大小 n, m 和马的初始位置坐标 x, y：

• 0 ≤ x ≤ n-1
• 0 ≤ y ≤ m-1
• m < 10
• n < 10

输出：

对于每组测试数据，输出一个整数，表示马能遍历棋盘的途径总数。如果无法遍历整个棋盘，输出 0。

样例输入：

1
5 4 0 0

样例输出：

32

思路分析：

这个问题可以用回溯法（深度优先搜索，DFS）来解决。马的移动规则类似于一个“骑士回溯问题”，需要遍历整个棋盘的每一个点，并且不允许重复经过同一个点。通过递归搜索每一种可能的路径，并且在搜索过程中标记访问过的点。

步骤：

1. ​定义马的移动方式​：马可以按照日字形规则移动，总共有 8 种可能的方向。
2. ​递归回溯​：从初始位置 (x, y) 开始，尝试所有 8 种可能的移动。如果当前位置合法且没有被访问过，就继续搜索。
3. ​标记访问​：在递归过程中维护一个标记数组，记录每个点是否已经被访问。
4. ​路径计数​：当递归搜索完成时，如果所有点都被遍历，则计数增加。

复杂度分析：

• ​时间复杂度​：最坏情况下，所有的路径都需要被探索，因此时间复杂度大约是 O(8^(n*m))，这里的 n*m 是棋盘的大小。由于题目中棋盘最大为 9x9，这个复杂度是可以接受的。
• ​空间复杂度​：主要是 visited 数组，占据 O(n*m) 空间。

示例解释：

输入：

1
5 4 0 0

输出：

32

• 这里的棋盘是 5x4 的大小，马从 (0, 0) 位置开始，能通过回溯法计算出共有 32 条不同的遍历路径。