蓝桥杯备战日志(Python)16-玩具蛇&序列个数-(DFS&枚举、递归)

玩具蛇

原题

小蓝有一条玩具蛇，一共有 16节，上面标着数字 1 至 16。每一节都是一个正方形的形状。相邻的两节可以成直线或者成 90度角。

小蓝还有一个 4 × 4 的方格盒子，用于存放玩具蛇，盒子的方格上依次标着字母 A 到 P共 16个字母。

小蓝可以折叠自己的玩具蛇放到盒子里面。他发现，有很多种方案可以将玩具蛇放进去。

下图给出了两种方案：

请帮小蓝计算一下，总共有多少种不同的方案。如果两个方案中，存在玩具蛇的某一节放在了盒子的不同格子里，则认为是不同的方案。

分析

将4x4的方格矩阵看成16个结点(位置固定)的图，本题考查图的深度优先遍历DFS，首先指定访问的第一个结点，下一个访问的结点的位置位于当前结点的上下左右4个位置(前提是未越界且未被访问)，最后求“按照不同顺序访问完所有结点的路径”的种类数。

在编程中DFS一般使用递归实现，关键点是下一个结点的访问和回溯，具体实现见“源码”部分。

源码

count = 0
num = 16
snake = [ [0]*4 for _ in range(4) ]

# 判断当前位置是否可以访问，可访问条件：不越界且未被访问过
def iscan_access(i,j):
    return i >= 0 and j >= 0 and i < 4 and j < 4 and snake[i][j] == 0

def dfs(n,i,j):
    global count
    if not iscan_access(i,j):
        return
    if n == num:
        count += 1
        return

    n += 1
    snake[i][j] = 1  # 标记已经访问了
    
    dfs(n,i,j+1)
    dfs(n,i,j-1)
    dfs(n,i+1,j)
    dfs(n,i-1,j)

    snake[i][j] = 0  # 标记未被访问，回溯

for i in range(4):
    for j in range(4):
        dfs(1,i,j)

print(count)

序列个数

原题

请问有多少个序列满足下面的条件：

1. 序列的长度为 5。
2. 序列中的每个数都是 1 到 10 之间的整数。
3. 序列中后面的数大于等于前面的数。

分析

本题解题思路不难，即根据题意条件枚举所有的序列情况，考虑到条件的特殊性，可以使用递归实现枚举。

递归实现的关键是序列中当前的数>=前一个数，枚举当前序列的数的区间范围为上一个数到序列最大数n_max（这里n_max=10），递归的出口就是当前枚举的序列长度达到指定长度5，递归的入口（这里看作递归函数的参数）是当前序列的上一个数和长度。

源码

n_min = 1
n_max = 10
length = 5

res = 0

def search_sequence(n: int,A: int):
    '''序列的第n个数为 A
       A <= 第n+1个数 <= n_max
    '''
    global res
    if n == length:
        res += 1
        return
    for i in range(A,n_max+1):
        search_sequence(n+1,i)

for i in range(n_min,n_max+1):
    search_sequence(1,i)

print(res)

上一篇：​​蓝桥杯备战日志(Python)15-铺设道路-(贪心、递归分裂区间)​​