文档章节

广度优先遍历-走迷宫

a_xianyu
 a_xianyu
发布于 2017/08/26 10:49
字数 546
阅读 17
收藏 1
点赞 0
评论 0

    经常会遇到走迷宫的问题,也就是求一个人从迷宫的起点到终点的任意一条最短路径。

    迷宫可以用二维数组进行表示,1表示可以行走,0表示不能行走。如下所示

         1 0 0 1 1 0

         1 1 1 1 0 1

         0 1 0 1 1 1

         0 0 1 1 0 1

,问题也就是求从左上角到右下角的最短路径。

    典型的广度优先遍历,直接上代码(借鉴别人的,然后进行了简化,更方便学习和理解)

import java.util.Deque;
import java.util.Iterator;
import java.util.LinkedList;

/**
 * @author lishunpu
 * @create 2017-08-26 10:23
 */
public class Main {
    public static String path="";
    public static Deque<String> queue = new LinkedList<String>();
    public static int m, n; //m表示横坐标,y表示纵坐标

    public static void main(String[] args) {
        int[][] map = {
                {1,0,0,1,1,0},
                {1,1,1,1,0,1},
                {0,1,0,1,1,1},
                {0,0,1,1,0,1}
        };
        m = map.length;
        n = map[0].length;
        bfs(0, 0, map);
        System.out.println(path);
    }

    public static void bfs(int x, int y, int[][] map) {
        if (x < 0 || y < 0 || x >= m || y >= n || map[x][y] == 0) {
            return;
        }

        queue.offerLast("[" + x + "," + y + "]"); //将当前位置放入队列中
        map[x][y] = 0; //并将其设置为已经走过

        if (x == m - 1 && y == n - 1) { //到达终点
            updatePath();
            map[x][y] = 1;
            queue.removeLast();
            return;
        }

        bfs(x, y + 1, map); //上
        bfs(x + 1, y, map); //右
        bfs(x, y - 1, map); //下
        bfs(x - 1, y, map); //左
        map[x][y] = 1;
        queue.removeLast();
    }

    public static void updatePath() {
        StringBuilder sb = new StringBuilder();
        Iterator<String> iterator = queue.iterator();
        while (iterator.hasNext())
            sb.append(iterator.next() + ",");
        if (sb.length() > 0)
            sb.deleteCharAt(sb.length() - 1);
        path = sb.toString();
    }
}

    对于上面的输入,结果为 [0,0],[1,0],[1,1],[1,2],[1,3],[2,3],[2,4],[2,5],[3,5]

    题目的变种很多,但主要思想都不会变。

温馨提示:如果要多次求路径,则前后两次会出现不一样的结果,因为每次遍历都会对矩阵中的值进行修改。此时可以新建一个矩阵visit[][],所有值初始化为1,表示没有访问过,用0表示访问过,每次遍历时判断visit[x][y]的值。另外,静态变量不能赋初值(除非能确定在整个遍历过程中其值都不会发生改变),必须在每次查找路径时重新赋值,不信的话可以试试附上的bfs的第一题。

附上遇到的bfs的题:

    http://acm.nyist.net/JudgeOnline/problem.php?pid=58

© 著作权归作者所有

共有 人打赏支持
a_xianyu
粉丝 0
博文 36
码字总数 18533
作品 0
哈尔滨
程序员
深度优先搜索遍历与广度优先搜索遍历

深度优先遍历过程 1、图的遍历 和树的遍历类似,图的遍历也是从某个顶点出发,沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图的算法的基础。 深度优先遍历和广度优先遍历...

长平狐
2013/01/06
1K
0
【算法研究】搜索算法-深度优先搜索

---------- 如果您觉得本文有用,可以在微博上关注我,每周我都会在微博上发布新博客发表的通知,我的微博 深度优先搜索 介绍 如果您觉得这篇文章排版不舒服,请到我的微盘下载pdf:搜索算法...

王选易
2013/12/13
0
3
图论 应用篇

上次写了篇图的基本构造方法,运用图这种强大的数据结构结构,还能解决实际应用中的许多问题,今天这篇就主要整理一些常见的应用 一、路径问题 路径问题在图的处理领域是非常重要的。如我们最...

丶legend
2017/11/05
0
0
游戏与常用的五大算法---下篇

前言: 心是一个人的翅膀,心有多大,世界就有多大。很多时候限制我们的,不是周遭的环境,也不是他人的言行,而是我们自己!看不开,放不下,忘不了,把自己囚禁在灰暗的记忆里;不敢想,不...

loving_forever_
2017/01/08
0
0
数据结构java迷宫的路径搜索方式与迷宫数据存储模式

@小代 你好,想跟你请教个问题: 实现一个以链表作存储结构的栈类型,然后编写一个求解迷宫的非递归程序 跟 在迷宫中进行路径搜索时,可采用深度优先搜索或广度优先搜索的策略 并且用二维数组...

问题
2014/12/28
119
0
基于深搜生成迷宫,基于广搜和深搜生成迷宫 求代码分享

用图深度优先搜索生成迷宫,再用图深度搜索和图广度搜索解迷宫 ,用PYTHON语言写的

金辰颖
2012/04/13
751
5
洪水填充(Flood fill)算法

洪水填充(Flood fill)算法 从一个起始节点开始把附近与其连通的节点提取出或填充成不同颜色颜色,直到封闭区域内的所有节点都被处理过为止,是从一个区域中提取若干个连通的点与其他相邻区域...

放个屁
2015/06/20
0
1
图的JS实现

图的定义 图就是由若干个顶点和边连接起来的一种结构。很多东西都可以用图来说明,例如人际关系,或者地图。 其中图还分为有向图和无向图。 如下就是有向图 图的数据结构 对于图这种关系,可...

光哥很霸气
2017/10/12
0
0
python 回溯法 记录

一直不是太理解回溯法,这几天集中学习了一下,记录如下。 回溯法有“通用的解题法”之称。 1.定义: 也叫试探法,它是一种系统地搜索问题的解的方法。 2.基本思想: 从一条路往前走,能进则...

罗兵
2017/05/29
0
0
深度优先和广度优先遍历及其 Java 实现

图的遍历,所谓遍历,即是对结点的访问。一个图有那么多个结点,如何遍历这些结点,需要特定策略,一般有两种访问策略: 深度优先遍历 广度优先遍历 深度优先 深度优先遍历,从初始访问结点出...

BKC
2016/07/08
76
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

轻松搭建svn版本管理工具+svnmanager管理客户端

前面的文章有写过svn版本管理工具的安装是基于svn的安装包进行安装,对于svn与apache的结合还得下svn和apache的模块进行结合过程比较繁琐,今天来介绍下通过centos的yum来安装svn能够快速安装...

javazyw
12分钟前
0
0
keepalived配置高可用集群

Linux集群概述 根据功能划分为两大类:高可用和负载均衡 高可用集群通常为两台服务器,一台工作,另外一台作为冗余,当提供服务的机器宕机,冗余将接替继续提供服务 实现高可用的开源软件有:...

TaoXu
17分钟前
0
0
mysql联表批处理操作

1 概述 mysql中的单表增删改查操作,可以说是基本中的基本. 实际工作中,常常会遇到一些基本用法难以处理的数据操作,譬如遇到主从表甚至多级关联表的情况(如一些历史问题数据的批量处理),考虑到...

社哥
20分钟前
0
0
IntelliJ IDEA 详细图解最常用的配置,适合刚刚用的新人。

刚刚使用IntelliJ IDEA 编辑器的时候,会有很多设置,会方便以后的开发,磨刀不误砍柴工。 比如:设置文件字体大小,代码自动完成提示,版本管理,本地代码历史,自动导入包,修改注释,修改...

kim_o
34分钟前
0
0
Google Java编程风格指南

目录 前言 源文件基础 源文件结构 格式 命名约定 编程实践 Javadoc 后记 前言 这份文档是Google Java编程风格规范的完整定义。当且仅当一个Java源文件符合此文档中的规则, 我们才认为它符合...

niithub
37分钟前
0
0
java.net.MalformedURLException异常说明

1.异常片段 Java代码中,在进行URL url = new URL(urllink)操作时,提示以下异常信息,该类异常主要问题出在参数urllink上面。 异常片段1 java.net.MalformedURLException at java.ne...

lqlm
37分钟前
1
0
CentOS7修改mysql5.6字符集

解决办法:CentOS7下修改MySQL数据库字符编码为UTF-8,UTF-8包含全世界所有国家所需要的字符集,是国际编码。 具体操作如下: 1.进入MySQL [root@tianqi-01 ~]# mysql -uroot -p Enter passw...

河图再现
39分钟前
0
0
DevExpress v18.1新版亮点——WPF篇(一)

用户界面套包DevExpress v18.1日前终于正式发布,本站将以连载的形式为大家介绍各版本新增内容。本文将介绍了DevExpress WPF v18.1 的新功能,快来下载试用新版本!点击下载>> Accordion Co...

Miss_Hello_World
41分钟前
0
0
Rancher 2.0集群与工作负载告警

Rancher 2.0操作指南。本文将step by step演示如何使用Rancher 2.0中集成的告警功能,包括设置通知程序、设置集群级别以及工作负载级别的告警。 在Rancher 1.x时期,告警功能是很多Rancher用...

RancherLabs
46分钟前
1
0
Python中字符串拼接的N中方法

python拼接字符串一般有以下几种方法: ①直接通过(+)操作符拼接 s = 'Hello'+' '+'World'+'!'print(s) 输出结果:Hello World! 使用这种方式进行字符串连接的操作效率低下,因为python中...

木头释然
47分钟前
9
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部