【NC235814】马踏棋盘

题目

马踏棋盘

DFS、回溯

思路

回溯模板题，这道题不仅仅是深度优先搜索，而关键在于回溯的思想，具体见代码。注意这道题中的 $n,m$ 的含义。

代码

#include <stdio.h>
#define N 20

const int TO[4][2] = {{1, 2}, {1, -2}, {2, 1}, {2, -1}};

char vis[N][N];
int n, m, ans;

void dfs(int x, int y) {
    if (x == n - 1 && y == m - 1) {
    	// 如果到了终点，则将答案加一
        ans++;
        return;
    }
    for (int i = 0; i < 4; i++) {
        int tx = x + TO[i][0];
        int ty = y + TO[i][1];
        if (tx < 0 || tx >= n || ty < 0 || ty >= m || vis[tx][ty]) {
            continue;
        }
        vis[tx][ty] = 1;
        dfs(tx, ty);
        // 回溯
        vis[tx][ty] = 0;
    }
}

int main(void) {
    scanf("%d%d", &m, &n);
    dfs(0, 0);
    printf("%d\n", ans);
    return 0;
}