Java利用廣度優(yōu)先搜索實(shí)現(xiàn)抓牛問(wèn)題
更新時(shí)間：2022年06月29日 09:17:49 作者：chengqiuming
廣度優(yōu)先搜索是最簡(jiǎn)便的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。本文將利用廣度優(yōu)先搜索實(shí)現(xiàn)抓牛問(wèn)題，感興趣的可以了解下
一、原問(wèn)題鏈接
http://poj.org/problem?id=3278
二、輸入和輸出
1.輸入
兩個(gè)數(shù)，第1個(gè)數(shù)代表農(nóng)夫的位置，第2個(gè)數(shù)代表牛的位置
2.輸出
農(nóng)夫抓牛的最小步數(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);
}
}
}
}五、測(cè)試
綠色為輸入，白色為輸出。
到此這篇關(guān)于Java利用廣度優(yōu)先搜索實(shí)現(xiàn)抓牛問(wèn)題的文章就介紹到這了,更多相關(guān)Java廣度優(yōu)先搜索內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
本文是小編給大家收藏整理的IDEA 2019.1.3 激活碼大全，非常不錯(cuò)，具有一定的參考借鑒價(jià)值，需要的朋友參考下吧2019-10-10
解決Springboot項(xiàng)目打包后的頁(yè)面丟失問(wèn)題(thymeleaf報(bào)錯(cuò))
這篇文章主要介紹了解決Springboot項(xiàng)目打包后的頁(yè)面丟失問(wèn)題(thymeleaf報(bào)錯(cuò))，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-11-11
這篇文章主要介紹了Lambda 是JDK 8 的重要新特性。它允許把函數(shù)作為一個(gè)方法的參數(shù)（函數(shù)作為參數(shù)傳遞進(jìn)方法中），使用 Lambda 表達(dá)式可以使代碼變的更加簡(jiǎn)潔緊湊,使Java代碼更加優(yōu)雅，感興趣的小伙伴一起來(lái)學(xué)習(xí)吧2021-08-08
老生常談Java?網(wǎng)絡(luò)編程?——?Socket?詳解
這篇文章主要介紹了Java?網(wǎng)絡(luò)編程?——?Socket?相關(guān)知識(shí)，本文通過(guò)示例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2023-05-05
Java?Web開(kāi)發(fā)常用框架Spring?MVC?Struts示例解析
這篇文章主要為大家介紹了Java?Web開(kāi)發(fā)常用框架Spring?MVC?Struts示例解析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-06-06
這篇文章主要介紹了介紹java中Pair(配對(duì)),示例描述使用Pair類(lèi)實(shí)現(xiàn)簡(jiǎn)單Integer到String的映射,示例中g(shù)etKey方法返回key對(duì)象，getValue方法返回對(duì)應(yīng)值對(duì)象,需要的朋友可以參考下2023-03-03
Java的Hibernate框架中的雙向主鍵關(guān)聯(lián)與雙向外鍵關(guān)聯(lián)
Hibernate想要實(shí)現(xiàn)雙向的關(guān)聯(lián)就必須在映射文件的兩端同時(shí)配置<one-to-one>,另外還要在主映射的一端采用foreign外鍵關(guān)聯(lián)屬性,下面我們就一起來(lái)看一下Java的Hibernate框架中的雙向主鍵關(guān)聯(lián)與雙向外鍵關(guān)聯(lián)方法:2016-06-06
這篇文章主要介紹了idea中項(xiàng)目文件目錄消失的解決方案,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-11-11
Spring MVC實(shí)現(xiàn)mysql數(shù)據(jù)庫(kù)增刪改查完整實(shí)例
這篇文章主要介紹了Spring MVC實(shí)現(xiàn)mysql數(shù)據(jù)庫(kù)增刪改查完整實(shí)例，從創(chuàng)建一個(gè)web項(xiàng)目開(kāi)始，分享了項(xiàng)目結(jié)構(gòu)以及具體Java代碼和前端頁(yè)面等相關(guān)內(nèi)容，具有一定借鑒價(jià)值，需要的朋友可以了解下。2017-12-12
本文詳細(xì)講解了Java基于TCP協(xié)議的Socket通信，文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-12-12