M04123: 马走日

backtracking, http://cs101.openjudge.cn/pctbook/M04123/

马在中国象棋以日字形规则移动。

请编写一段程序，给定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

maxn = 10;
sx = [-2,-1,1,2, 2, 1,-1,-2] # 马的横向移动
sy = [ 1, 2,2,1,-1,-2,-2,-1] # 马的纵向移动

ans = 0;
 
def Dfs(dep: int, x: int, y: int):
    #是否已经全部走完
    if n*m == dep:
        global ans
        ans += 1
        return
    
    #对于每个可以走的点
    for r in range(8):
        s = x + sx[r]
        t = y + sy[r]
        if chess[s][t]==False and 0<=s<n and 0<=t<m :
            chess[s][t]=True
            Dfs(dep+1, s, t)
            chess[s][t] = False; #回溯
 

for _ in range(int(input())):
    n,m,x,y = map(int, input().split())
    chess = [[False]*maxn for _ in range(maxn)]  #False表示没有走过
    ans = 0
    chess[x][y] = True
    Dfs(1, x, y)
    print(ans)

非递归实现

def knight_tour_non_recursive(test_cases):
    # 定义马的日字形移动规则
    moves = [
        (-2, -1), (-1, -2), (1, -2), (2, -1),
        (2, 1), (1, 2), (-1, 2), (-2, 1)
    ]

    results = []

    for case in test_cases:
        n, m, start_x, start_y = case
        total_squares = n * m

        # 初始化栈
        stack = [(start_x, start_y, [(start_x, start_y)])]
        paths_count = 0

        while stack:
            x, y, path = stack.pop()

            if len(path) == total_squares:
                paths_count += 1
                continue

            for dx, dy in moves:
                nx, ny = x + dx, y + dy
                if 0 <= nx < n and 0 <= ny < m and (nx, ny) not in path:
                    stack.append((nx, ny, path + [(nx, ny)]))

        results.append(paths_count)

    return results


test_cases = []
for _ in range(int(input())):
    test_cases.append(tuple(map(int, input().split())))

results = knight_tour_non_recursive(test_cases)

for res in results:
    print(res)

思路:dfs有递归的意思在里面比起bfs更有记忆和储存的属性，然后面对多重可能的时候要利用好函数，增加函数的一个变量来分类。

但是需要注意：(x + v, y + w) not in lst,x + v in range(n), 时间复杂度高，是O(n)。

# 王杨玉佳 24数学科学学院
T = int(input())

for i in range(T):
    list1 = list(map(int, input().split()))
    n = list1[0]
    m = list1[1]
    x = list1[2]
    y = list1[3]

    direct = [(-1, -2), (-1, 2), (1, -2), (1, 2), (2, 1), (2, -1), (-2, 1), (-2, -1)]

    def dfs(x, y, lst, t):
        s = 0
        if t == n * m:
            return 1
        else:
            for v, w in direct:
                if (x + v, y + w) not in lst and x + v in range(n) and y + w in range(m):
                    lst.append((x + v, y + w))
                    s += dfs(x + v, y + w, lst, t + 1)
                    lst.pop()

        return s

    lst = [(x, y)]
    print(dfs(x, y, lst, 1))

思路：我的思路就是设一个set，在里面放上所有的未经过的点，然后再依次遍历

# pylint:skip-file
# 玄泽彦 24地空学院
directions=[(1,2),(2,1),(-1,2),(-2,1),(2,-1),(1,-2),(-1,-2),(-2,-1)]



def dfs(d,t,not_visit:set):
    global num

    not_visit.remove((d,t))

    if not not_visit:
        num+=1
        not_visit.add((d,t))
    else:
        for dx,dy in directions:
            nx,ny=d+dx,t+dy
            if 0<=nx<n and 0<=ny<m and (nx,ny) in not_visit:
                dfs(nx,ny,not_visit)
        not_visit.add((d,t))
for _ in range(int(input())):
    n,m,x,y=map(int,input().split())

    num=0
    not_visited=set()
    for i in range(n):
        for j in range(m):
            not_visited.add((i,j))
    dfs(x,y,not_visited)
    print(num)