迷宫问题经典dfs方式解决

简介: 迷宫问题经典dfs方式解决

定义一个二维数组 N*M ,如 5 × 5 数组下所示:

int maze[5][5] = {

0, 1, 0, 0, 0,

0, 1, 1, 1, 0,

0, 0, 0, 0, 0,

0, 1, 1, 1, 0,

0, 0, 0, 1, 0,

};

它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。

数据范围: 2 \le n,m \le 10 \2n,m10  , 输入的内容只包含 0 \le val \le 1 \0val1

输入描述:

输入两个整数,分别表示二维数组的行数,列数。再输入相应的数组,其中的1表示墙壁,0表示可以走的路。数据保证有唯一解,不考虑有多解的情况,即迷宫只有一条通道。

输出描述:

左上角到右下角的最短路径,格式如样例所示。

5 5

0 1 0 0 0

0 1 1 1 0

0 0 0 0 0

0 1 1 1 0

0 0 0 1 0

输出格式

(0,0)

(1,0)

(2,0)

(2,1)

(2,2)

(2,3)

(2,4)

(3,4)

(4,4)

这道题是经典的dfs的场景,

以下代码可以参考 已经测试通过

import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
            int n = in.nextInt();
            int m = in.nextInt();
            int[][] ints=new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                ints[i][j] = in.nextInt();
            }
        }
        boolean[][] booleans=new boolean[n][m];
        Deque<String> res=new LinkedList<>();
        dfs(ints,0,0,booleans,res);
        for (String re : res) {
            System.out.println(re);
        }
    }
    private static boolean dfs(int[][] ints, int i, int Y,boolean[][] booleans,Deque<String> path) {
        //递归结束标记
        if(i==ints.length-1 && Y==ints[0].length-1){
            path.addLast("("+i+","+Y+")");
            return true;
        }
        booleans[i][Y]=true;
        path.addLast("("+i+","+Y+")");
        //下探
        //向下走第一个条件是剪枝 第二个避免 重复走
       if(i+1<=ints.length-1 && !booleans[i+1][Y]&&ints[i+1][Y]==0&&dfs(ints,i+1,Y,booleans,path)){
           return true;
       } ;
        if(i-1>=0 && !booleans[i-1][Y]&&ints[i-1][Y]==0&&dfs(ints,i-1,Y,booleans,path)){
            return true;
        } ;
        if(Y+1<=ints[0].length-1 && !booleans[i][Y+1]&&ints[i][Y+1]==0&&dfs(ints,i,Y+1,booleans,path)){
            return true;
        } ;
        if(Y-1>=0 && !booleans[i][Y-1]&&ints[i][Y-1]==0&&dfs(ints,i,Y-1,booleans,path)){
            return true;
        } ;
            //回溯
            booleans[i][Y]=false;
        path.removeLast();
            return false;
    }
}
相关文章
|
8月前
|
算法
Hierholzer算法dfs找欧拉回路模板
Hierholzer算法dfs找欧拉回路模板
79 0
|
数据采集 自然语言处理 搜索推荐
图文详解 DFS 和 BFS | 算法必看系列知识二十四
深度优先遍历(Depth First Search, 简称 DFS) 与广度优先遍历(Breath First Search)是图论中两种非常重要的算法,生产上广泛用于拓扑排序,寻路(走迷宫),搜索引擎,爬虫等,也频繁出现在高频面试题中。
32992 4
图文详解 DFS 和 BFS | 算法必看系列知识二十四
|
6月前
|
存储 算法 Python
Python图论实战:从零基础到精通DFS与BFS遍历,轻松玩转复杂网络结构
【7月更文挑战第11天】图论在数据科学中扮演关键角色,用于解决复杂网络问题。Python因其易用性和库支持成为实现图算法的首选。本文通过问答形式介绍DFS和BFS,图是节点和边的数据结构,遍历用于搜索和分析。Python中图可表示为邻接表,DFS用递归遍历,BFS借助队列。DFS适用于深度探索,BFS则用于最短路径。提供的代码示例帮助理解如何在Python中应用这两种遍历算法。开始探索图论,解锁更多技术可能!
165 6
|
7月前
|
存储 SQL 算法
LeetCode题目100:递归、迭代、dfs使用栈多种算法图解相同的树
LeetCode题目100:递归、迭代、dfs使用栈多种算法图解相同的树
|
存储 算法
深度优先遍历(DFS):探索图的奥秘
当进行深度优先遍历(DFS)时,我们需要按照一定的步骤来遍历图中的节点。 选择起始节点:选择图中的一个起始节点作为遍历的起点。 标记已访问:将起始节点标记为已访问,并将其放入数据结构中,比如栈或递归调用。 探索相邻节点:从起始节点开始,探索与其相邻的节点。这是通过查找邻接表来实现的,邻接表存储了每个节点的相邻节点信息。 深入探索:选择一个相邻节点,标记为已访问,并将其放入数据结构中。然后,从这个相邻节点出发,继续探索其相邻节点,形成一个深入的路径。这一步是递归的核心。 回溯:当没有未访问的相邻节点时,回溯到上一个节点,继续探索其他未访问的相邻节点。这可以通过从数据结构中弹出节点来实现,或者从递
316 0
|
机器学习/深度学习 存储 算法
【DFS经典例题】2n皇后问题
【DFS经典例题】2n皇后问题
83 0
|
8月前
|
算法
深度优先搜索(DFS)的基础理解与实现
深度优先搜索(DFS)的基础理解与实现
96 0
|
数据采集 算法 C++
DFS(深度优先搜索)详解(概念讲解,图片辅助,例题解释,剪枝技巧)
DFS(深度优先搜索)详解(概念讲解,图片辅助,例题解释,剪枝技巧)
1175 0
解密经典数学问题:跳马问题的DFS解法
本文介绍了跳马问题的背景和解析,并提供了一种基于DFS的解题思路。通过详细的代码实现和解题技巧的讲解,读者能够对跳马问题有更深入的理解和掌握。
348 0