BFS基础思想题之“Catch That Cow”

题目大意：

　　在一个x正半轴上，给你两个点，N 代表人，K代表牛。

　　牛是不会动的，要求你去抓牛，求出最小步数。

　　你有三种行动方式，分别为 

　　　　　　前进：坐标加一，步数加一。

　　　　　　后退：坐标减一，步数加一。

　　　　　　跳跃：坐标乘二，步数加一。

　　其中x轴坐标限制在 [0，100000]。

　　样例只有一组：5  17 --> 4

解题思路：

　　这是一道入门的BFS，主要看重培养BFS的思想。

　　我们只需要一个队列就能完成这个目标。

　　先将人的坐标入队，然后将三种行动的坐标都入队，

　　然后判断队首元素，不符合就出队，符合就弹出循环输出队首的标记数。

　　每次循环标记都要加一。

AC代码：

　　

import java.util.*;
import java.util.Queue;
import java.util.LinkedList; 

public class Main{

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int vis[] = new int[100005];
            Queue<Integer> map = new LinkedList<Integer>();
            int man = sc.nextInt();
            int cow = sc.nextInt();
            map.offer(man); vis[man] ++;
            while(map.size() != 0){
                if(man == cow){System.out.println("0");break;}
                int t = map.peek();
                //System.out.println(t);
                map.poll();
                if(t + 1 >= 0 && t + 1 <= 100000){
                    if(vis[t + 1] == 0){map.offer(t + 1);vis[t + 1] = vis[t] + 1;}
                }
                if(t - 1 >= 0 && t - 1 <= 100000){
                    if(vis[t - 1] == 0){map.offer(t - 1);vis[t - 1] = vis[t] + 1;}
                }
                if(t * 2 >= 0 && t * 2 <= 100000){
                    if(vis[t * 2] == 0){map.offer(t * 2);vis[t * 2] = vis[t] + 1;}
                }
                if(map.peek() == cow){System.out.println(vis[cow] - 1);break;}
            }
        }
    }
}