3038: 马走日 dfs 入门必写

解题思路:

注意事项:

参考代码:

#include "bits/stdc++.h"
using namespace std;
// 全局变量声明
int n, m, x, y, kkk = 0; // n和m表示棋盘的大小，x和y表示起始位置，kkk用于计数
int a[15][15]; // 棋盘数组
int xxx[10] = {-2, -1, 2, 1, -2, -1, 2, 1}; // 马移动的x方向偏移量
int yyy[10] = {-1, -2, -1, 2, 1, 2, 1, -2}; // 马移动的y方向偏移量
void dfs(int xx, int yy, int k) {
    // 如果已经走完所有格子，增加计数器并返回
    if (k == n * m) {
        kkk++;
        return;
    }
    // 遍历所有可能的马移动方向
    for (int i = 0; i < 8; i++) {
        int X = xx + xxx[i]; // 计算新的x坐标
        int Y = yy + yyy[i]; // 计算新的y坐标
        // 检查新坐标是否在棋盘范围内且该位置未被访问过
        if (X >= 0 && X < n && Y >= 0 && Y < m && a[X][Y] == 1) {
            a[X][Y] = 0; // 标记该位置为已访问
            dfs(X, Y, k + 1); // 递归调用dfs继续搜索
            a[X][Y] = 1; // 回溯，恢复该位置为未访问状态
        }
    }
}

int main() {
    int t; // 测试用例数量
    cin >> t; // 输入测试用例数量
    while (t--) {
        kkk = 0; // 初始化计数器
        cin >> n >> m >> x >> y; // 输入棋盘大小和起始位置
        // 初始化棋盘，将所有位置设为未访问状态
        for (int i = 0; i < 15; i++) {
            for (int j = 0; j < 15; j++) {
                a[i][j] = 1;
            }
        }
        a[x][y] = 0; // 将起始位置设为已访问状态
        dfs(x, y, 1); // 从起始位置开始进行深度优先搜索
        cout << kkk << endl; // 输出结果
    }
    return 0;
}