四口鲸鱼爱吃盐

用户名：uq_98591838827

访问量：1709

签　名：

等　　级
排　　名	482
经　　验	4679
参赛次数	0
文章发表	28
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

题解: 蓝桥杯算法训练VIP-反置数【Python】
浏览：36

题解: 蓝桥杯算法训练VIP-提货单【Python】
浏览：18

编写题解：分解质因数【Python】
浏览：49

你可能喜欢

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）如果a<0，那就不是这个代码了，哈哈哈哈

蓝桥杯算法提高VIP-学霸的迷宫【Python题解】BFS

　　作者: 四口鲸鱼爱吃盐　　　　发表时间：2023-03-25 10:44:14 浏览：100　|　评论：0　

原题链接：蓝桥杯算法提高VIP-学霸的迷宫

# 解题思路
本题利用广度优先搜索。

注意题目中要求：
> 如果有多条长度相同的最短路径，选择在此表示方法下字典序最小的一个。

因此我们搜索的顺序是 `D, L, R, U`，即：**下左右上**。

具体见参考代码及其注释。

# 参考代码
```python
# 广度优先搜索
n, m = map(int, input().split())
cell = [list(map(int, input())) for i in range(n)]

# visited用来记录结点访问状态
visited = [[False for j in range(m)] for i in range(n)]
visited[0][0] = True

# dx, dy 表示 下左右上 方向的坐标变动
d = ['D', 'L', 'R', 'U']
dx = [1, 0, 0, -1]
dy = [0, -1, 1, 0]

# res 用来记录当前搜索层结点的结果
# res[0][0] 表示横坐标
# res[0][1] 表示纵坐标
# res[0][2] 表示到达该结点的移动次数
# res[0][3] 表示到达该结点的路径
res = [[0, 0, 0, []]]

while res:
    # 终止条件：到达目标结点
    if (res[0][0] == n-1) and (res[0][1] == m-1):
        print(res[0][2])
        print(''.join(res[0][3]))

# 遍历四个方向
    for i in range(4):
        new_x = res[0][0] + dx[i]
        new_y = res[0][1] + dy[i]
        new_path = res[0][3] + [d[i]]

# 如果新坐标不超过边界
        if (0 <= new_x <= n-1) and (0 <= new_y <= m-1):
            # 如果该结点没有被访问过，且可以通过
            if (not visited[new_x][new_y]) and cell[res[0][0]][res[0][1]] == 0:
                res.append([new_x, new_y, res[0][2]+1, new_path])
                visited[new_x][new_y] = True

# 该结点搜索完毕
    res.pop(0)
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

四口鲸鱼爱吃盐

TA的其他文章

你可能喜欢

C语言训练-8除不尽的数（C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

【作业调度方案】（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）如果a<0，那就不是这个代码了，哈哈哈哈

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

蓝桥杯算法提高VIP-学霸的迷宫【Python题解】BFS

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

【亲和数】（C语言代码）

关于float，double变量的几点说明

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

众数问题（C语言代码）

哥德巴赫曾猜测（C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

简单的a+b （C语言代码）

四口鲸鱼爱吃盐

TA的其他文章

你可能喜欢

C语言训练-8除不尽的数 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

【作业调度方案】 （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码） 如果a<0，那就不是这个代码了，哈哈哈哈

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

蓝桥杯算法提高VIP-学霸的迷宫【Python题解】BFS

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

【亲和数】 （C语言代码）

关于float，double变量的几点说明

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

众数问题 （C语言代码）

哥德巴赫曾猜测 （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

简单的a+b （C语言代码）

C语言训练-8除不尽的数（C语言代码）

【作业调度方案】（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）如果a<0，那就不是这个代码了，哈哈哈哈

　　评论区

【亲和数】（C语言代码）

众数问题（C语言代码）

哥德巴赫曾猜测（C语言代码）