面试题 08.02. 迷路的机器人

LeetCode： 面试题 08.02. 迷路的机器人

典型的 dfs、bfs 题 >> 题目大意： 机器人只能往下或往右走 >> 从左上角走到右下角 >> 二维数组中 1 为障碍物

真是做吐了 >> dfs 竟然忘记把访问过的坐标进行标记 >> 提交了7次， TimeOutLimit 了 7 次 >> 我真是憨憨

因为我们只需要随便返回一条可行的路径就可以了 >> 那么在 达到 右下角的位置后， 直接 return false , 后面再继续递归就没意义了

同时只需要递归一条路径 >> 访问过的坐标点也不需要进行回溯

dfs 深度优先搜索

    List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
        dfs(obstacleGrid, 0, 0);
        return ans;
    }


    public boolean dfs(int[][] arr, int row, int col) {
        if (row >= arr.length || col >= arr[0].length || arr[row][col] == 1) return true;
        ans.add(Arrays.asList(row, col));
        // 访问过的坐标进行标记
        arr[row][col] = 1;
        if (row == arr.length - 1 && col == arr[0].length - 1) {
            return false;
        }

        // 下 && 右
        boolean b = dfs(arr, row + 1, col) && dfs(arr, row, col + 1);

        if(b)
            ans.remove(ans.size() - 1);

        return b;
    }