蓝桥杯真题 一步之遥 Python——暴力、BFS

蓝桥杯真题 一步之遥 Python——暴力、BFS

• 题目
• 分析
• • 法一 暴搜
  • 法二 bfs
  • 总结

题目

一步之遥

从昏迷中醒来，小明发现自己被关在X星球的废矿车里。
矿车停在平直的废弃的轨道上。
他的面前是两个按钮，分别写着“F”和“B”。

小明突然记起来，这两个按钮可以控制矿车在轨道上前进和后退。
按F，会前进97米。按B会后退127米。
透过昏暗的灯光，小明看到自己前方1米远正好有个监控探头。
他必须设法使得矿车正好停在摄像头的下方，才有机会争取同伴的援助。
或许，通过多次操作F和B可以办到。

矿车上的动力已经不太足，黄色的警示灯在默默闪烁…
每次进行 F 或 B 操作都会消耗一定的能量。
小明飞快地计算，至少要多少次操作，才能把矿车准确地停在前方1米远的地方。

请填写为了达成目标，最少需要操作的次数。

注意，需要提交的是一个整数，不要填写任何无关内容（比如：解释说明等）

分析

法一 暴搜

看到最小操作次数，容易想到bfs搜索，但这是个填空题没必要浪费时间，直接暴搜，找到最小的解
记录前进F次，后退B次，最终一定满足 97F-127B= 1

for i in range(200):#范围自己试着开for j in range(200):if 97*i-127*j == 1:#因为最终是要前进1，所以成立的话前进操作的距离97*i > 127*jprint(i,j)#i+j最小的是 = 55+42  ==97break

法二 bfs

蓝桥杯bfs的能力还是很重要的！

本题而言，属于直线型运动，不妨假设初始点在-1，目标为0，如果搜到0，那么就输出步数。如果没搜到0，把当前结点（数字）的下一个状态也就是新结点加入queue队列（前提要判断过合法），直至找到0。

dir=[97,-127]
def judge(x):if x in pre.keys():#如果已经搜过该状态了，不用再搜了，保证最小值return Falseelse:return True
pre={}
queue=[-1]def bfs():global queuewhile queue:tmp=queue.pop(0)if tmp==0:#搜到了0step=1#为什么是1，搜到0用了1步，这里的1好好理解一下while pre[tmp]!=-1:tmp=pre[tmp]#后序从0找到起前驱节点step+=1print(step)breakelse:for i in range(2):ne=tmp+dir[i]if judge(ne):queue.append(ne)pre[ne]=tmpbfs()
#print(pre)

总结

单源最短路径型BFS必备的容器，函数:judge()，前驱结点字典pre，队列queue（其实就是列表）,方向数组。
其中：pre字典：最重要的就是记录前驱关系，当创建完所有结点的关系时，通过终点倒着访问，当访问到起点，结束，总路径因而知晓。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！