【正经题解】马走日

#include <iostream>
#include <cstring>

using namespace std;

const int MAX_N = 15;
int visited[MAX_N][MAX_N];
int directions[8][2] = {{1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};
int pathCount;

// 深度优先搜索函数
void dfs(int x, int y, int steps, int n, int m) {
    int nextX, nextY, k;
    // 如果已经走完整个棋盘，增加路径计数
    if (steps == n * m) {
        pathCount++;
    }
    // 如果当前位置未被访问
    if (visited[x][y] == 0) {
        visited[x][y] = 1; // 标记为已访问
        // 尝试八个方向的移动
        for (k = 0; k < 8; k++) {
            nextX = x + directions[k][0];
            nextY = y + directions[k][1];
            // 检查下一步是否在合法范围内且未被访问过
            if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m && visited[nextX][nextY] == 0) {
                dfs(nextX, nextY, steps + 1, n, m);
            }
        }
        visited[x][y] = 0; // 回溯，标记为未访问
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m, startX, startY;
        cin >> n >> m >> startX >> startY;
        pathCount = 0;
        memset(visited, 0, sizeof(visited)); // 初始化访问数组
        dfs(startX, startY, 1, n, m);
        cout << pathCount << endl;
    }
    return 0;
}