Java利用廣度優(yōu)先搜索實現(xiàn)抓牛問題
更新時間:2022年06月29日 09:17:49 作者:chengqiuming
廣度優(yōu)先搜索是最簡便的圖的搜索算法之一,這一算法也是很多重要的圖的算法的原型。本文將利用廣度優(yōu)先搜索實現(xiàn)抓牛問題,感興趣的可以了解下
一、原問題鏈接
http://poj.org/problem?id=3278
二、輸入和輸出
1.輸入
兩個數(shù),第1個數(shù)代表農夫的位置,第2個數(shù)代表牛的位置
2.輸出
農夫抓牛的最小步數(shù)
三、輸入和輸出樣例
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利用廣度優(yōu)先搜索實現(xiàn)抓牛問題的文章就介紹到這了,更多相關Java廣度優(yōu)先搜索內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
Java concurrency集合之ArrayBlockingQueue_動力節(jié)點Java學院整理
ArrayBlockingQueue是數(shù)組實現(xiàn)的線程安全的有界的阻塞隊列。下面通過本文給大家介紹Java concurrency集合之ArrayBlockingQueue的相關知識,感興趣的朋友一起看看吧2017-06-06