M04123: 马走日

backtracking, http://cs101.openjudge.cn/pctbook/M04123

马在中国象棋以日字形规则移动。

请编写一段程序，给定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

样例输出

这个问题可以使用回溯算法来解决。需要模拟马的移动路径，并在每一步检查是否能访问到棋盘上的所有点。

思路：

马的移动遵循“日”字形规则，可以向8个方向移动：上下左右及斜对角。
使用回溯法遍历棋盘上的每一个点。每当访问一个新的点，就将其标记为已访问，且递归尝试访问下一个点。
如果能够成功访问所有棋盘点（即移动的步数等于棋盘的大小），则记录为一个有效路径。
避免重复访问，使用一个二维数组来标记每个点是否已访问过。

步骤：

先初始化棋盘的大小和起始位置。
使用回溯递归进行搜索。
检查每一个方向的移动是否合法，并在合法时进行递归调用。
当递归到达棋盘的所有点时，计数有效路径。

cpp

#include <iostream>
#include <vector>

using namespace std;

const int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};  // 马的横向移动
const int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};  // 马的纵向移动

// 回溯法计算遍历路径的数量
void dfs(int x, int y, int n, int m, int visited_count, vector<vector<bool>>& visited, int& result) {
    // 如果已经遍历了所有格子
    if (visited_count == n * m) {
        result++;
        return;
    }

    // 尝试所有8个方向
    for (int i = 0; i < 8; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        // 如果新位置合法并且没有被访问过
        if (nx >= 0 && ny >= 0 && nx < n && ny < m && !visited[nx][ny]) {
            visited[nx][ny] = true;
            dfs(nx, ny, n, m, visited_count + 1, visited, result);
            visited[nx][ny] = false;  // 回溯
        }
    }
}

int main() {
    int T;
    cin >> T;  // 输入测试数据组数
    
    while (T--) {
        int n, m, x, y;
        cin >> n >> m >> x >> y;  // 输入棋盘大小和起始位置

        // 访问标记数组，初始化为false
        vector<vector<bool>> visited(n, vector<bool>(m, false));
        int result = 0;

        // 从起始位置(x, y)开始，标记为已访问
        visited[x][y] = true;
        dfs(x, y, n, m, 1, visited, result);

        // 输出结果
        cout << result << endl;
    }
    
    return 0;
}

代码解释：

dx 和 dy 数组：定义了马可以向8个方向移动的偏移量。
dfs 函数：使用递归进行回溯。参数包括当前坐标 (x, y)，棋盘大小 n, m，已访问的点数 visited_count，标记访问状态的 visited 数组，以及存储结果的 result。
回溯过程：每次尝试马的8个可能的移动，若合法且未访问过，就递归调用。
主函数：首先读取测试数据组数 T，然后每组数据执行一次 dfs，最终输出结果。

复杂度：

在最坏的情况下，每个位置都要遍历一次，且对于每个位置尝试8个方向的移动。最坏时间复杂度为 O(8^N)（其中 N 为棋盘的格数）。但由于棋盘大小限制，最大为 9x9，实际运行时会比这个上限快得多。

M04123: 马走日 ​

M04123: 马走日