蓝桥杯备战日志(Python)10-最短路-(图的遍历)

最短路

原题

如下图所示， 是一个无向图，其中蓝色边的长度是 、橘色边的长度是 、绿色边的长度是 。

则从  到  的最短距离是多少？

分析

本题考查图的遍历，本题使用深度优先（DFS）遍历指定起点和终点的路径，最终即可求出最短路径。

首先是对图中各个结点及其相互之间的通路进行录入，这里使用一个元组(a,b,p)表示两个结点之间的路，其中a, b, p分别表示结点a、结点b、两点之间的路径长度。

paths_t = (
    ("A", "B", 2),("A", "C", 1),("A", "D", 1),("A", "E", 1),
    ("B", "G", 1),("B", "J", 2),("C", "D", 3),("C", "G", 3),
    ("C", "F", 3),("D", "G", 2),("D", "H", 1),("D", "I", 2),
    ("E", "H", 1),("E", "I", 3),("F", "J", 1), ("F", "G", 1),
    ("G", "K", 2),("G", "I", 3),("H", "L", 2),("H", "I", 1),
    ("I", "M", 3),("J", "S", 2),("K", "N", 1),("K", "L", 3),
    ("L", "R", 1),("L", "M", 1),("M", "N", 2),("M", "Q", 1),
    ("M", "S", 1),("N", "P", 1),("Q", "O", 1),("O", "R", 3),
    ("R", "S", 1),
)

这里起点为结点A，终点为结点S，进行深度优先遍历：从点A出发，然后选择一个与A相邻顶点b（这里的b为B, C, D, E）进行访问并记录当前路径长度，再从b出发选择一个与b相邻顶点进行访问，依次继续，直到访问到终点。

源码

paths_t = (
    ("A", "B", 2),("A", "C", 1),("A", "D", 1),("A", "E", 1),
    ("B", "G", 1),("B", "J", 2),("C", "D", 3),("C", "G", 3),
    ("C", "F", 3),("D", "G", 2),("D", "H", 1),("D", "I", 2),
    ("E", "H", 1),("E", "I", 3),("F", "J", 1), ("F", "G", 1),
    ("G", "K", 2),("G", "I", 3),("H", "L", 2),("H", "I", 1),
    ("I", "M", 3),("J", "S", 2),("K", "N", 1),("K", "L", 3),
    ("L", "R", 1),("L", "M", 1),("M", "N", 2),("M", "Q", 1),
    ("M", "S", 1),("N", "P", 1),("Q", "O", 1),("O", "R", 3),
    ("R", "S", 1),
)

# 初始化最短路径长度和起点、终点
path_min = 3 * 26
start = 'A'
end = 'S'

def get_path(path,t):
    '''path为从start点到t[1]点的某个路径的长度'''
    global path_min
    # 访问到终点
    if t[1] == end:
        path_min = min(path_min,path)
        return
    # 继续找下一个相邻的点进行访问
    for p in paths_t:
        if t[1] == p[0]:
            path += t[2]
            get_path(path,p)
        
for t in paths_t:
    # 从点start出发，找到一个与A相邻的顶点
    if t[0] == start:
        get_path(t[2],t)

print(path_min)

蛇形填数

原题

如下图所示，小明用从  开始的正整数“蛇形”填充无限大的矩阵。

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

容易看出矩阵第二行第二列中的数是 。请你计算矩阵中第  行第  列的数是多少？

“暴力枚举”编程实现

所谓蛇形填数，就是矩阵中的数按照从小到大的次序用线连接后是一个“蛇形图案”。

从数字1（第1行第1列）开始，设每个数字的位置用行索引、列索引的方式表示，即(row, col)。控制连线的方向的操作可以细分为以下四步：

① 斜向下连线的准备：行索引不变，列索引加1；如数字1到数字2，数字6到7，......

② 斜向下连线：行索引加1，列索引减1，直到列索引变为1；如数字2、3，数字7、8、9、10，......

③ 斜向上连线的准备：行索引加1，列索引不变；如数字3到数字4，数字10到11，......

④ 斜向上连线：行索引减1，列索引加1，直到行索引变为1；如数字4、5、6，数字11、12、13、14、15，......

具体实现见如下代码。

m,n = 20,20
num = 1 
row, col = 1, 1

# 每次将一个数字进行连线后判断当前数字的位置(row,col)是否满足题意
def temp_func():
    global num, row, col, m, n
    num += 1
    if row == m and col == n:
        print(num)
        return True
    else:
        return False

def findNum():
    global row, col
    while True:
        col += 1
        if temp_func(): return
        while col > 1:
            row += 1
            col -= 1
            if temp_func(): return
        row += 1
        if temp_func(): return
        while row > 1:
            row -= 1
            col += 1
            if temp_func(): return

findNum()

找规律

以上“暴力枚举” 实现较繁琐，且效率较低，在比赛中遇到这种类型的填空题一般可以找到其数字规律，以上实现仅供有兴趣的朋友了解参考。

针对本题的第矩阵中第20行第20列的数字，行、列索引相等的数字位于对角线上，可以找找矩阵中对角线的数字的规律，然后求解。

1,5,13,25,...n是为第i行第i列的元素(i=1,2,3,4,...,n)，即对角线上的元素。

其数字规律的表达式可能不止一种，看个人的找规律方法，比赛中遇到这种类型题需要参赛者对数字排列有一定的敏感性。以下是其两种表达式（递归式和普通公式）。

def get_n(i):
    if i==1:
        return 1
    elif i >= 2:
        n = get_n(i-1) + (i-1) * 4
        return n
get_n(20)


def get_n1(i):
    return i*i+(i-1)**2
get_n1(20)

上一篇：​​蓝桥杯备战日志(Python)9-寻找2020-(“异常”的使用-IndexError)​​