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

目录
  • 一、原问题链接
  • 二、输入和输出
  • 三、输入和输出样例
  • 四、代码
  • 五、测试

一、原问题链接

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广度优先搜索内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • 基于Java实现的图的广度优先遍历算法

    本文以实例形式讲述了基于Java的图的广度优先遍历算法实现方法,具体方法如下: 用邻接矩阵存储图方法: 1.确定图的顶点个数和边的个数 2.输入顶点信息存储在一维数组vertex中 3.初始化邻接矩阵: 4.依次输入每条边存储在邻接矩阵arc中 输入边依附的两个顶点的序号i,j: 将邻接矩阵的第i行第j列的元素值置为1: 将邻接矩阵的第j行第i列的元素值置为1: 广度优先遍历实现: 1.初始化队列Q 2.访问顶点v:visited[v]=1;顶点v入队Q; 3.while(队列Q非空) v=队列

  • Java实现二叉树的深度优先遍历和广度优先遍历算法示例

    Java实现二叉树的深度优先遍历和广度优先遍历算法示例

    本文实例讲述了Java实现二叉树的深度优先遍历和广度优先遍历算法.分享给大家供大家参考,具体如下: 1. 分析 二叉树的深度优先遍历的非递归的通用做法是采用栈,广度优先遍历的非递归的通用做法是采用队列. 深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次.要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历.中序遍历.后序遍历.具体说明如下: 先序遍历:对任一子树,先访问根,然后遍历其左子树,最后遍历其右子树. 中序遍历:对任一子树,先遍历其左子树,然

  • Java编程实现基于图的深度优先搜索和广度优先搜索完整代码

    Java编程实现基于图的深度优先搜索和广度优先搜索完整代码

    为了解15puzzle问题,了解了一下深度优先搜索和广度优先搜索.先来讨论一下深度优先搜索(DFS),深度优先的目的就是优先搜索距离起始顶点最远的那些路径,而广度优先搜索则是先搜索距离起始顶点最近的那些路径.我想着深度优先搜索和回溯有什么区别呢?百度一下,说回溯是深搜的一种,区别在于回溯不保留搜索树.那么广度优先搜索(BFS)呢?它有哪些应用呢?答:最短路径,分酒问题,八数码问题等.言归正传,这里笔者用java简单实现了一下广搜和深搜.其中深搜是用图+栈实现的,广搜使用图+队列实现的,代码如下:

  • 深度优先与广度优先Java实现代码示例

    深度优先与广度优先Java实现代码示例

    在编程生活中,我们总会遇见树性结构,这几天刚好需要对树形结构操作,就记录下自己的操作方式以及过程.现在假设有一颗这样树,(是不是二叉树都没关系,原理都是一样的) 1.深度优先 英文缩写为DFS即Depth First Search. 深度优先搜索是一种在开发爬虫早期使用较多的方法.它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) .在一个HTML文件中,当一个超链被选择后,被链接的HTML文件将执行深度优先搜索,即在搜索其余的超链结果之前必须先完整地搜索单独的一条链.深度

  • Java实现利用广度优先遍历(BFS)计算最短路径的方法

    Java实现利用广度优先遍历(BFS)计算最短路径的方法

    本文实例讲述了Java实现利用广度优先遍历(BFS)计算最短路径的方法.分享给大家供大家参考.具体分析如下: 我们用字符串代表图的顶点(vertax),来模拟学校中Classroom, Square, Toilet, Canteen, South Gate, North Gate几个地点,然后计算任意两点之间的最短路径. 如下图所示: 如,我想从North Gate去Canteen, 程序的输出结果应为: BFS: From [North Gate] to [Canteen]: North Ga

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

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

    目录 一.原问题链接 二.输入和输出 三.输入和输出样例 四.代码 五.测试 一.原问题链接 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; impor

  • Java利用深度搜索解决数独游戏详解

    Java利用深度搜索解决数独游戏详解

    目录 一.问题描述 二.输入和输出 三.输入和输出样例 四.分析 五.算法设计 六.代码 七.测试 一.问题描述 数独是一项非常简单的任务.如下图所示,一张 9 行 9 列的表被分成 9 个 3*3 的小方格.在一些单元格中写上十进制数字 1~9,其他单元格为空.目标是用 1 ~9 的数字填充空单元格,每个单元格一个数字,这样在每行.每列和每个被标记为 3*3 的子正方形内,所有 1~9 的数字都会出现.编写一个程序来解决给定的数独任务. 二.输入和输出 1.输入 对于每个测试用例,后面都跟 9

  • Java利用Dijkstra和Floyd分别求取图的最短路径

    Java利用Dijkstra和Floyd分别求取图的最短路径

    目录 1 最短路径的概述 2 杰斯特拉(Dijkstra)算法 2.1 原理 2.2 案例分析 3 弗洛伊德(Floyd)算法 3.1 原理 3.2 案例分析 4 邻接矩阵加权图实现 5 邻接表加权图实现 本文详细介绍了图的最短路径的概念,然后介绍了求最短路径的两种算法:Dijkstra算法和Floyd算法的原理,最后提供了基于邻接矩阵和邻接表的图对两种算法的Java实现. 阅读本文需要一定的图的基础,如果对于图不是太明白的可以看看这篇文章:Java数据结构之图的原理与实现. 1 最短路径的概述

  • Java利用正则表达式提取数据的方法

    什么是正则表达式 正则表达式是一种可以用于模式匹配和替换的规范,一个正则表达式就是由普通的字符(例如字符a到z)以及特殊字符(元字符)组成的文字模式,它 用以描述在查找文字主体时待匹配的一个或多个字符串.正则表达式作为一个模板,将某个字符模式与所搜索的字符串进行匹配. Java利用正则表达式提取数据 Java正则表达式的用途很广,之前要用到将一大 3M 的 txt 文本切分成多个小文本,用 C# 写的话很简洁,代码也就二十几行,今天用 Java 写了一下,果然,Java 很罗嗦. 切分文件的代码

  • Java利用TCP协议实现客户端与服务器通信(附通信源码)

    进行TCP协议网络程序的编写,关键在于ServerSocket套接字的熟练使用,TCP通信中所有的信息传输都是依托ServerSocket类的输入输出流进行的. 上一篇博客和大家分享了在网络编程中要注意的基础知识,关于IP.TCP.UDP以及端口和套接字的一些概念,想了解的小伙伴可以看我的这篇文章"盘点那些进行网络编程必须要知道的基础知识",那么今天大灰狼就来和大家分享一下如何使用TCP/IP进行网络程序的开发. TCP协议概念 先来了解一下TCP协议的基本概念. 我们知道TCP是可靠

  • Java利用正则取标签之间的数据

    我就废话不多说了,大家还是直接看代码吧~ String str = "哈哈<font color='red'>1111</font>还是你牛<font color='red'>11111</font> "; String regStr = "<font color='red'>(.*?)</font>"; Pattern pattern = Pattern.compile(regStr); if

  • Java利用反射实现框架类的方法实例

    框架类的简单实现 实现步骤: 1. 加载配置文件 2. 获取配置文件中定义的数据 3. 加载该类进内存 主要讲解第一步:加载配置文件 的相关知识. //1.加载配置文件 //1.1创建Properties对象 Properties pro = new Properties(); //1.2加载配置文件,转换为一个集合 //1.2.1获取class目录下的配置文件 ClassLoader classLoader = ReflectTest.class.getClassLoader(); Input

  • java利用正则表达式处理特殊字符的方法实例

    前言 一串字符串中有特殊符号,可能会影响到相关接口业务,所以需要把字符串中的特殊字符都过滤掉 百度上面搜索大部分处理方法是通过正则表达式, 他需要处理的特殊符号都写进正则表达式中去校验, 这种方式一眼看过去就非常别扭, 感觉不灵活, 万一需要过滤其他的又得临时加进去 解决方案 如下所示 public static String stringFilter (String str){ String regEx="[\\u00A0\\s\"`~!@#$%^&*()+=|{}':;',

随机推荐