『LeetCode|每日一题』----＞迷路的机器人

目录

1.每日一句

2.作者简介

『LeetCode|每日一题』迷路的机器人

1.每日一题

2.解题思路

        2.1 思路分析（dfs + 回溯）

        2.2 核心代码

        2.3 完整代码

        2.4 运行结果

---

1.每日一句

挑战是生活的常态，迈过去，就是欢喜顺遂

2.作者简介

🏡个人主页：XiaoXiaoChen-2716 

📚学习专栏：力扣专栏 

🕒发布日期：2022/11/13

『LeetCode|每日一题』迷路的机器人

1.每日一题

原文链接--->点我

2.解题思路

        2.1 思路分析（dfs + 回溯）

类似于这种找迷宫的问题，其实用深度优先或者广度优先+回溯是最容易理解的方法

        S1：这种问题首先得考虑dfs函数里应该有哪些参数，首先矩阵不可缺少，还需要方向参数i ，j，很容易理解，用一个used二维矩阵来记录点是否被访问；

        S2：首先就是越界检查，i和j都不能小于零，同时也不能大于长和宽，这是最基本的，然后此时访问的这个位置不能是障碍物否则无法通过，然后就是此时访问的这个点它不能被访问过了；

        S3：访问一个点之和要记得把该点设置为访问过了，然后把该点的坐标放进一个list里面；

        S4：然后定义一个res用来存储一条可行的路径，此题有一个坑，我刚开始也踩了，那就是把所有不知障碍物的点都访问了一遍，我额外加了一个链表，用来添加每一次的结果，然后在最后remove它的最后一个元素，这样就不会把所有点都访问了；

        S5：函数写好之和，只需要把used数组初始化后，把起点传进去就好了

        2.2 核心代码

private void dfs(int[][] obstacleGrid , int[][] used , int i , int j){
        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;
        if(i < 0 || i >= row || j < 0 || j >= col || used[i][j] != 0 || obstacleGrid[i][j] == 1){
            return ;
        }
        used[i][j] = 1;
        List ans = new ArrayList<>();
        ans.add(i);
        ans.add(j);
        temp.add(ans);
        if(i == row - 1 && j == col - 1){
            res = new ArrayList<>(temp);
            return ;
        }
        dfs(obstacleGrid , used , i + 1 , j);
        dfs(obstacleGrid , used , i , j + 1);
        temp.remove(temp.size() - 1);
    }

         2.3 完整代码

class Solution {
    List> res = new ArrayList<>();
    List> temp = new ArrayList<>();
    public List> pathWithObstacles(int[][] obstacleGrid) {
        
        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;
        int[][] used = new int[row][col];
        for(int i = 0 ; i < row ; i++){
            for(int j = 0 ; j < col ; j++){
                used[i][j] = 0;
            }
        }
        dfs(obstacleGrid , used , 0 , 0);
        return res;
 
    }
    private void dfs(int[][] obstacleGrid , int[][] used , int i , int j){
        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;
        if(i < 0 || i >= row || j < 0 || j >= col || used[i][j] != 0 || obstacleGrid[i][j] == 1){
            return ;
        }
        used[i][j] = 1;
        List ans = new ArrayList<>();
        ans.add(i);
        ans.add(j);
        temp.add(ans);
        if(i == row - 1 && j == col - 1){
            res = new ArrayList<>(temp);
            return ;
        }
        dfs(obstacleGrid , used , i + 1 , j);
        dfs(obstacleGrid , used , i , j + 1);
        temp.remove(temp.size() - 1);
    }
}

        2.4 运行结果

---

🍁 类似题目推荐：

1.数据结构基础

2.算法专项练习

3.剑指offer专项练习

4.推荐一个学习网站：LeetCode，算法的提升在于日积月累，只有每天练习才能保持良好的状态

如果文章对各位大佬有帮助就支持一下噢，不好的地方请各位大佬多多指教！