马走日

题目描述

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

请编写一段程序，给定$n\times m$大小的棋盘，以及马的初始位置$(x，y)$，要求不能重复经过棋盘上的同一个点，计算马可以有多少途径遍历棋盘上的所有点。

输入

第一行为整数$T(T<10)$，表示测试数据组数。

每一组测试数据包含一行，为四个整数，分别为棋盘的大小以及初始位置坐标$n,m,x,y。(0\le x\le n-1,0\le y\le m-1,m<10,n<10)$。

输出

每组测试数据包含一行，为一个整数，表示马能遍历棋盘的途径总数，$0$为无法遍历一次。

输入样例

1
5 4 0 0

输出样例

32

思路

该题需要记录三个状态, 当前点是否被搜过st, 已经搜了多少个点res, 搜完所有点的方案ans。 其中ans就是我们要求的, 当dfs中res为点总数时将ans++即可。 该题就需要回溯了。

代码

const int N = 22;
int n, m;
int st[N][N];
int ans;
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
 
void dfs(int x, int y, int res)
{
    if (res == n * m)
    {
        ans++;
        return;
    }
    st[x][y] = true;
    for (int i = 0; i < 8; i++)
    {
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || a >= n || b < 0 || b >= m)
            continue;
        if (st[a][b])
            continue;
        dfs(a, b, res + 1);
    }
    st[x][y] = false;
}
 
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int x, y;
        cin >> n >> m >> x >> y;
        memset(st, false, sizeof st);
        ans = 0;
        dfs(x, y, 1);
        cout << ans << endl;
    }
    return 0;
}