一、原问题链接
http://poj.org/problem?id=3278
二、输入和输出
1.输入
两个数，第1个数代表农夫的位置，第2个数代表牛的位置
2.输出
农夫抓牛的最小步数
三、输入和输出样例
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利用广度优先搜索实现抓牛问题的文章就介绍到这了,更多相关Java广度优先搜索内容请搜索Devmax以前的文章或继续浏览下面的相关文章希望大家以后多多支持Devmax！