应该有比有爆搜更好的算法!
#pragma GCC optimize(2)// 吸口氧气
#pragma GCC optimize(3)// 吸口臭氧
#include <iostream>
#include <cstring>
using namespace std;
const int N = 12;
int g[N][N], T, m, n, x, y;
static constexpr int dirs[][2] {{-1, -2}, {-2, -1}, {-2, 1}, {-1, 2},
{1, 2}, {2, 1}, {2, -1}, {1, -2}};
int dfs(int x, int y, int r) { // r == remainder(剩余的)
if (x < 0 || y < 0 || x >= n || y >= m || g[y][x] == 1)
return 0;
if (--r == 0) return 1;
g[y][x] = 1; // mark as visited
int ans = 0;
for (const auto& d : dirs) // 往8个方向去扩展
ans += dfs(x + d[0], y + d[1], r);
g[y][x] = 0; // backtracking (恢复现场)
return ans;
}
int main() {
cin >> T;
while (T--) {
cin >> m >> n >> y >> x;
memset(g, 0, sizeof(int) * m * n);
printf("%d\n", dfs(x, y, m * n));
}
return 0;
}