Java利用广度优先搜索实现抓牛问题

广度优先搜索是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。本文将利用广度优先搜索实现抓牛问题，感兴趣的可以了解下

一、原问题链接

http://poj.org/problem?id=3278

二、输入和输出

1.输入

两个数，第1个数代表农夫的位置，第2个数代表牛的位置

2.输出

农夫抓牛的最小步数

三、输入和输出样例

1.输入样例

5 17

2.输出样例

四、代码

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 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); } } } }