蓝桥杯python组——蛇形填数-猿码集

蓝桥杯python组——蛇形填数

1. 题意

本文所讲的问题是 2019年第十届蓝桥杯Python省赛题目的第三题，即蛇形填数。

题目要求在一个 $n\times m$ 的二维数组里，按照蛇形方式填写从 $1$ 到 $n\times m$ 的整数。比如，当 $n=4,m=4$ 时，填出的数组是：

1 2 3 4 8 7 6 5 9 10 11 12 16 15 14 13

输入数据为一个正整数 $m$，约定 $m$ 的值范围为 $[1,30]$。需要在规定的时间内输出蛇形填数的方案。

2. 思路分析

对于蛇形填数，我们常见的想法是：每次将数字放到矩阵中，然后根据蛇形的规则，选择下一个点的位置。如果下一个点已经被填过了，就顺时针旋转一下方向。

具体实现时，我们可以维护一个方向变量 dir，0 表示向右，1 表示向下，2 表示向左，3 表示向上。初始化 dir=0，表示一开始向右填数。然后就可以用两个for循环遍历矩阵，根据索引值和方向变量 dir 计算出填入的数的值，并将其放到矩阵的对应位置。


# 输入值 m，生成 n × m 的矩阵
n = m 
a = [[0]*m for i in range(n)]
# 初始化变量
num = 1 
x, y = 0, 0 
dir = 0 # 方向
dx, dy = [0, 1, 0, -1], [1, 0, -1, 0] # dx,dy表示下一步的偏移量
# 开始填数
while num <= n * m:
    a[x][y] = num
    num += 1
    # 计算下一个数的位置
    nx, ny = x + dx[dir], y + dy[dir] 
    if 0 <= nx < n and 0 <= ny < m and a[nx][ny] == 0: 
        # 如果下一个数合法且未被填过
        x, y = nx, ny 
    else: 
        # 改变方向
        dir = (dir + 1) % 4 
        # 计算下一个数的位置
        x, y = x + dx[dir], y + dy[dir]

该算法时间复杂度为 $O(n \times m)$，符合要求。

3. 代码实现

完整代码中，我们还需要处理答案输出。最后将生成的二维数组逐行输出即可。代码如下：


m = int(input())
n = m
a = [[0]*m for i in range(n)]
# 初始化变量
num = 1 
x, y = 0, 0 
dir = 0 
dx, dy = [0, 1, 0, -1], [1, 0, -1, 0] 
# 开始填数
while num <= n * m:
    a[x][y] = num
    num += 1
    nx, ny = x + dx[dir], y + dy[dir] 
    if 0 <= nx < n and 0 <= ny < m and a[nx][ny] == 0: 
        x, y = nx, ny 
    else: 
        dir = (dir + 1) % 4 
        x, y = x + dx[dir], y + dy[dir] 
# 输出二维列表，逐行格式化输出
for i in range(n):
    print(" ".join([str(x) for x in a[i]]))

4. 总结

本文主要介绍了蓝桥杯Python省赛2019年第三题——蛇形填数，该问题的核心在于蛇形填数算法的设计和实现。通过详细的解释和代码实现，相信读者能够更好地了解该算法。

此外，蓝桥杯是一项非常有名的计算机竞赛，其题目涵盖了很多计算机领域的知识。通过参加蓝桥杯，大家可以更好地掌握编程技能，增强算法设计思维，提高计算机应用水平。

蓝桥杯python组——蛇形填数