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-06SpringBoot短鏈接跳轉(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-03Java之SpringBoot定時(shí)任務(wù)案例講解
這篇文章主要介紹了Java之SpringBoot定時(shí)任務(wù)案例講解,本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08Java中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