$$\color{Red}{马走日【DFS之搜索顺序】}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

类似的题-》 武士风度的牛【bfs版本求最优解】

思路

深度优先遍历————>不开st数组就每次把遍历过的点变成条件不让遍历的点的类型即可。

我们只开一个数组，用它的状态同时记录是否来过，如果想要进行每个点都遍历，需要恢复现场，保证搜不到答案的分支不会把上层的可走路线消除。

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

    static int N = 15, T, n, m, x, y, cnt;
    static boolean[][] st = new boolean[N][N];
    static int[] dx = {-2, -1, 1, 2, 2, 1, -1, -2}, dy = {1, 2, 2, 1, -1, -2, -2, -1};
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static void dfs(int x, int y, int z) {
        if (z == n * m) {
            cnt++;
            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, z + 1);
        }
        st[x][y] = false;
    }

    public static void main(String[] args) throws IOException {
        T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            String[] s1 = br.readLine().split(" ");
            cnt = 0;
            n = Integer.parseInt(s1[0]);
            m = Integer.parseInt(s1[1]);
            x = Integer.parseInt(s1[2]);
            y = Integer.parseInt(s1[3]);
            dfs(x, y, 1);
            System.out.println(cnt);
        }
    }
}