27237: 体育游戏跳房子

bfs, http://cs101.openjudge.cn/practice/27237

跳房子是大家小时候的体育游戏之一，游戏的规则简单易懂、具有可变性。我们在地面上画出一个个房子，然后扔石子，根据石子的落地位置确定跳到哪个房子。我们将房子抽象为x轴上的连续的正整数坐标点，第i个房子的坐标为i，并假设房子个数无限。我们的游戏规则如下：

石子落到房子内，记为H，我们可以跳到当前坐标的3倍坐标位置。
石子落到房子外，记为O，我们需跳回当前坐标折半并向下取整的坐标位置。

例如，初始在第1个房子，要想到达第6个房子，既可以HHHOO，也可以HHOHO。请你编一个程序，给出从第n个房子到第m个房子所需要的最少跳跃次数k和石子的扔法。若最少跳跃次数下存在多种扔法，则选取字典序最小的扔法。

输入

输入包含多组。每组是两个正整数n和m(1≤n，m ≤1000)。以0 0作为输入的结束

输出

对每组样例，第一行输出一个整数k，表示最少跳跃次数k（题目数据保证k有解且k ≤25），第二行输出相应的扔法。

样例输入

sample1 in：
1 6
0 0

sample1 out：
5
HHHOO
# 1->H->3->H->9->H->27->O->13->O->6
# 1->H->3->H->9->O->4->H->12->O->6
# HHHOO比HHOHO在字典序上更小。

样例输出

sample2 in:
2 4
0 0

sample2 out:
4
HHOO

提示

bfs

来源: 2023fall zzr. 2017 程序设计实习期末考试

python

from collections import deque
#import heapq

def bfs(s, e):
    q = deque()
    q.append((0, s, ''))
    vis = set()
    vis.add(s)
    # q = []
    #heapq.heappush(q, (0, s, ''))

    while q:
        step, pos, path = q.popleft()
        #step, pos, path = heapq.heappop(q)
        if pos == e:
            return step, path

        if pos * 3 not in vis:
            q.append((step+1, pos*3, path+'H'))
            vis.add(pos*3)
            #heapq.heappush(q, (step+1, pos*3, path+'H'))
        if int(pos // 2) not in vis:
            vis.add(int(pos//2))
            q.append((step+1, int(pos//2), path+'O'))
            #heapq.heappush(q, (step+1, int(pos//2), path+'O'))

while True:
    n, m = map(int, input().split())
    if n == 0 and m == 0:
        break
    step, path = bfs(n, m)
    print(step)
    print(path)

27237: 体育游戏跳房子 ​

27237: 体育游戏跳房子