C:Hopscotch【2019北大夏令营C】_hopscotch(跳房子) is a popular game. the rule is very

C:Hopscotch【2019夏令营C】找不到提交入口正确性未知

• 查看

• 提交

• 统计

• 提问

• 总时间限制:

  1000ms

• 内存限制:

  65536kB

• 描述

  Hopscotch(跳房子) is a popular game. The rule is very simple: we draw some houses on the ground and then throw a stone. Based on the position of the stone, we decide which house to jump to. Here, we use consecutive positive integer coordinates on the x-axis to represent the houses,the coordinate of the ith house is i. We also assume that there are infinite number of houses.Then, we define the new rules as follows, each time we throw a stone,

  1. if the stone falls into a house (marked as H), we can jump from the current house i to the house 3*i;
  2. if the stone falls outside the house (marked as O), we can jump from the current house i to house i/2.(round down).

  For example, initially at house 1, and in order to go to house 6, we can throw the stones in two ways：HHHOO or HHOHO.Now,your task is to compute the least number of jumps (k) needed to jump from a source house (n) and a destination house (m). You should also output the corresponding way of throwing the stones. If there are multiple ways, please output the smallest way in alphabet order.

• 输入

  There are multiple test cases. For each test case, there are two integers n and m (1<=n, m<=1000), representing the source house and destination house. The input ends with 0 0.

• 输出

  For each test case, the first line of output is an integer, which is the minimal number of jumps (k). The testing data guarantees that there is a solution and k <=25. The second line outputs the corresponding way of throwing the stone.

• 样例输入

  1 6
  0 0
  1
  2

• 样例输出

  5
  HHHOO
  1
  2

• 提示

  For the sample input, the minimal number of jump is 5 (k), and correspondingly there are two ways of throwing stones,

  1->H->3->H->9->H->27->O->13->O->6

  1->H->3->H->9->O->4->H->12->O->6

  We choose the first one as it is smaller in alphabet order.

题解

• BFS，从m走到n
  • BFS搜索走到的目的地的是最浅层的，即步数最少的
  • 搜索到n的那一层，同一层的孩子结点要考察完，选择字典序最小的

int main()
{
    int m,n;
    while(cin>>m>>n && (m||n)){
        if(m==n){
            cout<<"0\n"<<endl;
            continue;
        }
        //BFS m->n
        queue<int>q;
        queue<string>pq;
        q.push(m);
        pq.push("");
        int curr;
        string currp, best;
        while(q.empty()==0 && best.empty()){
            curr=q.front(); q.pop();
            currp=pq.front(); pq.pop();
            //H
            currp.push_back('H');
            if(3*curr==n){//solved
                if(best.empty() || currp<best){
                    best=currp;
                }
            }
            else{
                q.push(3*curr);
                pq.push(currp);
            }
            //O
            currp.pop_back();
            currp.push_back('O');
            if(curr/2==n){//solved
                if(best.empty() || currp<best){
                    best=currp;
                }
            }
            else{
                q.push(curr/2);
                pq.push(currp);
            }
        }
        cout<<best.size()<<endl;
        cout<<best<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47