Java怎么利用廣度優先搜索實現抓牛問題

本篇內容介紹了“Java怎么利用廣度優先搜索實現抓牛問題”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

一、原問題

二、輸入和輸出

1.輸入

兩個數，第1個數代表農夫的位置，第2個數代表牛的位置

2.輸出

農夫抓牛的最小步數

三、輸入和輸出樣例

1.輸入樣例

5 17

2.輸出樣例

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怎么利用廣度優先搜索實現抓牛問題”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！