一本通-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 <iomanip>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <set>
#include <algorithm>

using namespace std;

int m, n;
vector<vector<int> > gird(15, vector<int>(15));
int res = 0;
int startRow, startCol;

int direction[8][2] = {{-2, 1}, {-1, 2}, {2, 1}, {1, 2}, {-1, -2}, {-2, -1}, {1, -2}, {2, -1}};

void DFS(int row, int col, int step)
{
    gird[row][col] = 1;
    if (step == m * n) {
        ++res;
        return;
    }

    for (int i = 0; i < 8; ++i) {
        int nextRow = row + direction[i][0];
        int nextCol = col + direction[i][1];
        if (0 <= nextRow && nextRow < m && 0 <= nextCol && nextCol < n && gird[nextRow][nextCol] == 0) {
            DFS(nextRow, nextCol, step + 1);
            gird[nextRow][nextCol] = 0;
        }
    }
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int caseNum; cin >> caseNum;
    while (caseNum--) {
        cin >> m >> n >> startRow >> startCol;
        DFS(startRow, startCol, 1);
        cout << res << endl;

        res = 0;
        for (int i = 0; i < m; ++i) {
            fill(gird[i].begin(), gird[i].begin() + n, 0);
        }
    }

    return 0;
}