编程题：饥饿的小易

悠悠 2022-05-22 08:09 165阅读 0赞

## 题目描述 ##

小易总是感觉饥饿，所以作为章鱼的小易经常出去寻找贝壳吃。最开始小易在一个初始位置x\_0。对于小易所处的当前位置x，他只能通过神秘的力量移动到 4 \* x + 3或者8 \* x + 7。因为使用神秘力量要耗费太多体力，所以它只能使用神秘力量最多100,000次。贝壳总生长在能被1,000,000,007整除的位置(比如：位置0，位置1,000,000,007，位置2,000,000,014等)。小易需要你帮忙计算最少需要使用多少次神秘力量就能吃到贝壳。

## 输入描述: ##

输入一个初始位置x_0,范围在1到1,000,000,006

## 输出描述: ##

输出小易最少需要使用神秘力量的次数，如果使用次数使用完还没找到贝壳，则输出-1

示例1

## 输入 ##

复制

125000000

## 输出 ##

复制

### 思路：用哈希表存储已访问的点，使用队列存储待访问的点，使用bfs广度优先遍历 ###

### 代码： ###

import java.util.*;
    
    /**
     * Created by ASUS on 2018/6/19
     *
     * @Authod Grey Wolf
     */
    public class Practice {
        final static long MOD=1000000007L;
        final static int MAX= 100000;
    
        public static void main(String[] args) {
    
            Practice practice=new Practice();
            practice.sys();
        }
    
        private void sys() {
            Scanner scanner=new Scanner(System.in);
          while(scanner.hasNextLong()){
              long x=scanner.nextLong();
              System.out.println(getRes(x));
          }
        }
    
        private long getRes(long x) {
            //用哈希表来存储已访问的点
            Map<Long,Integer>dist=new HashMap<Long, Integer>();
            //使用队列存储待访问的点，广度优先遍历
            Queue<Long>queue=new LinkedList<Long>();
            dist.put(x,0);
            queue.add(x);
            while (!queue.isEmpty()){
                long d;
                Long top=queue.poll();
                if (dist.get(top)>MAX){
                    break;
                }
                if (top==0){
                    return dist.get(top);
                }
                d=((top<<2)+3)%MOD;
                if (d==0){
                    return dist.get(top)+1;
                }
                if (!dist.containsKey(d)){
                    queue.add(d);
                    dist.put(d,dist.get(top)+1);
                }
                d=((top<<3)+7)%MOD;
                if (d==0){
                    return dist.get(top)+1;
                }
                if (!dist.containsKey(d)){
                    queue.add(d);
                    dist.put(d,dist.get(top)+1);
                }
    
            }
            return -1L;
        }
    
    }

### 效果： ###

125000000  
1

我的座右铭：不会，我可以学；落后，我可以追赶；跌倒，我可以站起来；我一定行。