【搜索】C029_马走日（dfs 回溯）

Irina ·

更新时间:2024-11-10

· 991 次阅读

一、题目描述

马在中国象棋以日字形规则移动。请编写一段程序，给定 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

二、题解 方法一：dfs + 回溯 在 dfs 中加入 step，每次进入 dfs 时先判断当前 step 是否等于 R × C。是，则 count++ 否则，继续枚举 8 个方向。注意状态回溯。

import java.util.*;
import java.math.*;
import java.io.*;
public class Main{
	static int count, R, C;
	static boolean[][] vis = new boolean[10][10];
    public static void main(String[] args) throws IOException {  
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        BufferedWriter w = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = sc.nextInt();
		while (T-- > 0) {
			R = sc.nextInt();
			C = sc.nextInt();
			int x = sc.nextInt();
			int y = sc.nextInt();
			vis[x][y] = true;
			dfs(x, y, 1);
			System.out.println(count);
			count = 0;
		}
    }
	private static int[][] dir = {{1,2},{-1,2},{1,-2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};
	static void dfs(int x, int y, int step) {
		if (step == R * C) {
			count++;
			return;
		}
		for (int k = 0; k = 0 && x = 0 && y < C; 
	}
}

复杂度分析 时间复杂度：O(Cn8)O(C_n^8)O(Cn8)，空间复杂度：O(n2)O(n^2)O(n2)，
作者：Kipp99

dfs

1024 个赞