bfs求路径(Python)

解题思路:

1 单点可以选择两次 且保证合成每个数字要最优

2 可以看成是求最小路径 bfs的一种题型

参考代码:

def bfs(queue):

    for num in queue:

        step=temp[num]+1 # 步数来着上一个点+1

        for j in qu: # 选择

            so=num+j

            if so>n-1: # 题目意思 大于就要取余

                so%=n

            if exist[so]==0: # 最初都是0 但是都没有记录步数 这里来个限制条件

                exist[so]=1

                temp[so]=step # 只要没有访问 无脑记录下来

                queue.append(so)

            else: # 第二次或者更多次访问 取最小

                if step<temp[so]: # 只有小于才可以入队

                    temp[so]=step

                    queue.append(so)

n,k=map(int,input().split())

qu=[1,k]

exist=list(0 for i in range(n+1))

temp=list(0 for i in range(n+1))

bfs([0])

print(max(temp[1:-1])) # 最后取最大值 下标0和n去掉