文档章节

广度优先遍历-走迷宫

a_xianyu
 a_xianyu
发布于 2017/08/26 10:49
字数 546
阅读 33
收藏 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
163
0

没有更多内容

加载失败,请刷新页面

加载更多

二进制相关

二进制 众所周知计算机使用的是二进制,数字的二进制是如何表示的呢? 实际就是逢二进一。比如 2 用二进制就是 10。那么根据此可以推算出 5的二进制等于 10*10+1 即为 101。 在计算机中,负数以...

NotFound403
昨天
0
0
day22:

1、写一个getinterface.sh 脚本可以接受选项[i,I],完成下面任务: 1)使用格式:getinterface.sh [-i interface | -I ip] 2)当用户使用-i选项时,显示指定网卡的IP地址;当用户使用-I选项...

芬野de博客
昨天
1
0
Spring Cloud Alibaba基础教程:使用Nacos实现服务注册与发现

自Spring Cloud Alibaba发布第一个Release以来,就备受国内开发者的高度关注。虽然Spring Cloud Alibaba还没能纳入Spring Cloud的主版本管理中,但是凭借阿里中间件团队的背景,还是得到不少...

程序猿DD
昨天
3
0
Java并发编程:深入剖析ThreadLocal

ThreadLocal 的理解 ThreadLocal,很多地方叫线程本地变量,或线程本地存储。ThreadLocal为变量在每个线程中都创建了一个副本,每个线程可以访问自己内部的副本变量。===》解决的问题是线程间...

细节探索者
昨天
2
0
【Python3之异常处理】

一、错误和异常 1.错误 代码运行前的语法或者逻辑错误 语法错误(这种错误,根本过不了python解释器的语法检测,必须在程序执行前就改正) def test: ^SyntaxError: invalid...

dragon_tech
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部