Java利用廣度優(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)文章
Java concurrency集合之ArrayBlockingQueue_動(dòng)力節(jié)點(diǎn)Java學(xué)院整理
ArrayBlockingQueue是數(shù)組實(shí)現(xiàn)的線程安全的有界的阻塞隊(duì)列。下面通過(guò)本文給大家介紹Java concurrency集合之ArrayBlockingQueue的相關(guān)知識(shí),感興趣的朋友一起看看吧2017-06-06
SpringBoot短鏈接跳轉(zhuǎn)的代碼實(shí)現(xiàn)
短鏈跳轉(zhuǎn)是一種通過(guò)將長(zhǎng)鏈接轉(zhuǎn)換為短鏈接的方式,以便在互聯(lián)網(wǎng)上進(jìn)行鏈接共享和傳播的技術(shù),短鏈將原始長(zhǎng)鏈接通過(guò)特定算法轉(zhuǎn)換為較短的鏈接,使得它更容易分享、傳播和展示,本文給大家介紹了SpringBoot短鏈接跳轉(zhuǎn)的代碼實(shí)現(xiàn),需要的朋友可以參考下2024-03-03
Java之SpringBoot定時(shí)任務(wù)案例講解
這篇文章主要介紹了Java之SpringBoot定時(shí)任務(wù)案例講解,本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08
Java中JFrame實(shí)現(xiàn)無(wú)邊框無(wú)標(biāo)題方法
這篇文章主要介紹了Java中JFrame實(shí)現(xiàn)無(wú)邊框無(wú)標(biāo)題方法,本文直接給出代碼實(shí)例,需要的朋友可以參考下2015-05-05
關(guān)于FastJson?long?溢出問(wèn)題的小結(jié)
這篇文章主要介紹了關(guān)于FastJson?long?溢出問(wèn)題的小結(jié),具有很好的參考價(jià)值,希望對(duì)大家有所幫助。2022-01-01

