文档章节

广度优先遍历-走迷宫

a_xianyu
 a_xianyu
发布于 2017/08/26 10:49
字数 546
阅读 28
收藏 1

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

    迷宫可以用二维数组进行表示,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

没有更多内容

加载失败,请刷新页面

加载更多

idea 通过jpa自动生成实体类

引入jpa包 打开persistence窗口 右键选择连接数据库 如果数据库没配置,则可以在下图选项中配置 选择好数据库和实体类的生成地址

斩神魂
34分钟前
1
0
tcpdump 命令

TCPDUMP简介 tcpdump 是一个很常用的网络包分析工具,可以用来显示通过网络传输到本系统的 TCP/IP 以及其他网络的数据包。tcpdump 使用 libpcap 库来抓取网络报,这个库在几乎在所有的 Linu...

寰宇01
41分钟前
2
0
软件的Alpha、Beta、RC、GA版本的区别

Alpha:是内部测试版,一般不向外部发布,会有很多Bug.一般只有测试人员使用。 Beta:也是测试版,这个阶段的版本会一直加入新的功能。在Alpha版之后推出。 RC:(Release Candidate) 顾名思义...

乔老哥
42分钟前
3
0
慢雾安全海贼王:从DApp亡灵军团,细说区块链安全

本文转载自微信公号“万向区块链”,为慢雾安全负责人海贼王在万向区块链实验室举办的2018上海区块链国际周-技术开放日上的演讲速记整理。 这张图总结了智能合约攻防的各个方面,分为两大部分...

万向区块链
48分钟前
14
0
Matlab编程之——卷积神经网络CNN代码解析

卷积神经网络CNN代码解析 deepLearnToolbox-master是一个深度学习matlab包,里面含有很多机器学习算法,如卷积神经网络CNN,深度信念网络DBN,自动编码AutoE ncoder(堆栈SAE,卷积CAE)的作...

酒逢知己千杯少
48分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部