广度优先遍历-走迷宫
博客专区 > a_xianyu 的博客 > 博客详情
广度优先遍历-走迷宫
a_xianyu 发表于8个月前
广度优先遍历-走迷宫
  • 发表于 8个月前
  • 阅读 12
  • 收藏 1
  • 点赞 0
  • 评论 0

【腾讯云】买域名送云解析+SSL证书+建站!>>>   

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

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

标签: bfs 迷宫
  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 0
博文 36
码字总数 18533
×
a_xianyu
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: