Java怎么利用广度优先搜索实现抓牛问题

本篇内容介绍了“Java怎么利用广度优先搜索实现抓牛问题”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

一、原问题

二、输入和输出

输入

两个数，第1个数代表农夫的位置，第2个数代表牛的位置

输出

农夫抓牛的最小步数

三、输入和输出样例

输入样例

5 17

输出样例

4

四、代码

package graph.poj3278; import java.util.LinkedList;import java.util.Queue;import java.util.Scanner; public class POJ3278BFS {    static final int MAXN = 100009;    static boolean vis[] = new boolean[MAXN];    static int d[] = new int[MAXN];    static int n, k;     public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        n = scanner.nextInt();        k = scanner.nextInt();         if (k <= n) {            System.out.println(n - k);            return;        }        solve();    }     static void solve() {        Queue<Integer> q = new LinkedList<>();        vis[n] = true;        d[n] = 0;        q.add(n);        while (!q.isEmpty()) {            int u = q.peek();            q.poll();            if (u == k) {                System.out.println(d[k]);                return;            }            int x;            x = u + 1;            if (x >= 0 && x <= 100000 && !vis[x]) { // 向前走一步                d[x] = d[u] + 1;                vis[x] = true;                q.add(x);            }            x = u - 1;            if (x >= 0 && x <= 100000 && !vis[x]) { // 向后走一步                d[x] = d[u] + 1;                vis[x] = true;                q.add(x);            }            x = u * 2;            if (x >= 0 && x <= 100000 && !vis[x]) { // 跳着走                d[x] = d[u] + 1;                vis[x] = true;                q.add(x);            }        }    }}

五、测试

绿色为输入，白色为输出。

“Java怎么利用广度优先搜索实现抓牛问题”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注编程网网站，小编将为大家输出更多高质量的实用文章！