思路与算法

用最多25个格子的骑士图表示教学棋盘，维护当前点与未访问点位集，逐个尝试合法未访问邻格。全部访问时累计一条。加入必要条件剪枝：剩余图断开、出现无法接续的点、剩余度1端点过多时返回；已确定唯一末端时，其余度2邻点若必须使用当前边则强制下一步。候选按度数排序，但仍穷尽全部可行分支。

正确性说明

每条遍历序列恰对应从起点出发的一条深搜分支，最终计数不重不漏。当前点之后的未访问点必须形成一条连通路径，故断开或度0不可能完成。路径只有两个端点，已固定当前端点后，未访部分不允许过多被迫端点；唯一末端确定后，其他剩余度2点必须使用两个相邻边，若其一是当前边，就必须作为下一步。这些剪枝都只排除不可能完成的状态。另以不使用这些剪枝的独立完整DFS穷尽1..5所有225个棋盘起点组合并逐项核对。

复杂度

V=nm≤25。读入与骑士邻接初始化O(V)，回溯最坏可宽松界为O(V·8^V)，空间O(V)的位集邻接与递归栈。计数上界8^(V-1)≤2^72，参考用256位计数器确保无溢出。每个文件最多9组，教学全域及9组最大棋盘均按原1秒64MB验证。

易错点

本题是完整遍历路径数，不是最短路或可达格数。单格计1。教学范围明确缩至5×5；原9×9的工程缺项并未被这次验收消除，不能把新题包宣称为原81格全域完成。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using Mask = __uint128_t;
Mask adj[81];
int N;
array<unsigned long long, 4> answer;
int bit(Mask x) {
    unsigned long long lo = (unsigned long long)x;
    return lo ? __builtin_ctzll(lo) : 64 + __builtin_ctzll((unsigned long long)(x >> 64));
}
int pop(Mask x) {
    return __builtin_popcountll((unsigned long long)x) +
           __builtin_popcountll((unsigned long long)(x >> 64));
}
void add() {
    for (int i = 0; i < 4; ++i)
        if (++answer[i])
            break;
}
bool connected(Mask U) {
    int first = bit(U);
    Mask seen = Mask(1) << first, front = seen;
    while (front) {
        Mask next = 0;
        while (front) {
            int v = bit(front);
            front &= front - 1;
            next |= adj[v];
        }
        front = next & U & ~seen;
        seen |= front;
    }
    return seen == U;
}
void dfs(int current, Mask U) {
    if (!U) {
        add();
        return;
    }
    int count = pop(U);
    Mask moves = adj[current] & U;
    if (!moves)
        return;
    if (count == 1) {
        add();
        return;
    }
    int leaves = 0;
    Mask leafMask = 0;
    int forcedEnd = -1;
    for (Mask pending = U; pending; pending &= pending - 1) {
        int v = bit(pending);
        int d = pop(adj[v] & U);
        if (d == 0)
            return;
        if (d == 1) {
            if (++leaves > 2)
                return;
            leafMask |= Mask(1) << v;
        }
        if (d + bool(adj[v] & (Mask(1) << current)) == 1) {
            if (forcedEnd >= 0)
                return;
            forcedEnd = v;
        }
    }
    if (leaves == 2) {
        moves &= leafMask;
        if (!moves)
            return;
    }
    if (forcedEnd >= 0) {
        Mask endBit = Mask(1) << forcedEnd;
        if (adj[current] & endBit)
            return;
        int forced = -1;
        for (Mask pending = moves; pending; pending &= pending - 1) {
            int v = bit(pending);
            if (pop(adj[v] & U) == 1 && v != forcedEnd) {
                if (forced >= 0)
                    return;
                forced = v;
            }
        }
        if (forced >= 0)
            moves = Mask(1) << forced;
    }
    if (!connected(U))
        return;
    array<pair<int, int>, 8> order;
    int z = 0;
    for (Mask p = moves; p; p &= p - 1) {
        int v = bit(p);
        if (v == forcedEnd)
            continue;
        order[z++] = {pop(adj[v] & U), v};
    }
    sort(order.begin(), order.begin() + z);
    for (int j = 0; j < z; ++j) {
        int v = order[j].second;
        dfs(v, U ^ (Mask(1) << v));
    }
}
string decimal(array<unsigned long long, 4> x) {
    string s;
    while (x[0] || x[1] || x[2] || x[3]) {
        unsigned rem = 0;
        for (int i = 3; i >= 0; --i) {
            __uint128_t v = (__uint128_t(rem) << 64) | x[i];
            x[i] = v / 10;
            rem = v % 10;
        }
        s += char('0' + rem);
    }
    if (s.empty())
        s = "0";
    reverse(s.begin(), s.end());
    return s;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n, m, x, y;
        cin >> n >> m >> x >> y;
        N = n * m;
        fill(adj, adj + 81, Mask(0));
        int colors[2] = {0, 0};
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j) {
                ++colors[(i + j) & 1];
                for (int dx : {-2, -1, 1, 2})
                    for (int dy : {-2, -1, 1, 2})
                        if (abs(dx) + abs(dy) == 3) {
                            int r = i + dx, c = j + dy;
                            if (r >= 0 && r < n && c >= 0 && c < m)
                                adj[i * m + j] |= Mask(1) << (r * m + c);
                        }
            }
        answer.fill(0);
        int color = (x + y) & 1;
        if ((N % 2 == 0 && colors[0] == colors[1]) ||
            (N % 2 == 1 && colors[color] == colors[color ^ 1] + 1))
            dfs(x * m + y, ((Mask(1) << N) - 1) ^ (Mask(1) << (x * m + y)));
        cout << decimal(answer) << '\n';
    }
}