总时间限制: 1000ms 内存限制: 65536kB

描述

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

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

思路

从第0行出发, 遍历每一列, 当发现棋盘#就标记放一个棋子, 深度搜索下一行.

临界条件: 当行数row等于棋盘行数N时, 方案数自增, 然后返回上一层.

代码

#include <iostream>
#include <cstring>
using namespace std;
int N, M;               // 输入N行M列
int totalWays;
int visited[12][12];    // 标记棋盘上该点是否访问过
int direction[8][2] = { // 八个方向
    {-2, -1}, {-2, 1}, {-1, 2}, {-1, -2},
    {1, 2}, {2, 1}, {2, -1}, {1, -2}
};
void DFS(int x, int y, int curSteps) {
    if( curSteps == N * M ) {
        totalWays++;
        return;
    }
    /* 遍历8个方向 */
    for(int i = 0; i < 8; i++) {
        int tmpX = x + direction[i][0];
        int tmpY = y + direction[i][1];
        if( tmpX >= 0 && tmpX <= N-1 && tmpY >= 0 
            && tmpY <= M-1 && !visited[tmpX][tmpY] ) {
            visited[tmpX][tmpY] = 0x1;
            DFS(tmpX, tmpY, curSteps+1);
            visited[tmpX][tmpY] = 0x0;
        }
    }
}
int main() {
    /* Read data */
    int rounds;
    int x, y;           // 马的初始位置
    cin >> rounds;
    while( rounds-- ) {
        cin >> N >> M >> x >> y;
        /* Initialize data */
        memset(visited, 0x0, sizeof(visited));
        totalWays =  0;
        visited[x][y] = 0x1;    // 起始位置被访问
        /* DFS and display result */
        DFS(x, y, 1);
        cout << totalWays << endl;
    }
    return 0;
}