1219：马走日

【题目描述】
马在中国象棋以日字形规则移动。

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

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 15;
bool st[N][N];
int n, m, x, y, ans,  dir[8][2] = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}};

void dfs(int x, int y, int cnt)
{
    if(n * m == cnt)
    {
        ans++;
        return;
    }
    st[x][y] = true; 
    for(int i = 0; i < 8; i++)
    {
        int a = x + dir[i][0], b = y + dir[i][1];
        if(a >= 0 && a < n && b >= 0 && b < m && !st[a][b])
                dfs(a, b, cnt + 1);
    }
    st[x][y] = false;
}

int main()
{
    int T;
    cin >> T;
    while(T--) {
        cin >> n >> m >> x >> y;
        ans = 0;
        dfs(x, y, 1);
        cout << ans << endl;        
    }
    return 0;   
}