面试题 08.02:迷路的机器人

简介: 面试题 08.02:迷路的机器人

题目

题目链接

设想有个机器人坐在一个网格的左上角,网格 r 行 c 列。机器人只能向下或向右移动,但不能走到一些被禁止的网格(有障碍物)。设计一种算法,寻找机器人从左上角移动到右下角的路径。

网格中的障碍物和空位置分别用 1 和 0 来表示。

返回一条可行的路径,路径由经过的网格的行号和列号组成。左上角为 0 行 0 列。如果没有可行的路径,返回空数组

示例 1:

输入:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
输出: [[0,0],[0,1],[0,2],[1,2],[2,2]]
解释: 
输入中标粗的位置即为输出表示的路径,即
0行0列(左上角) -> 0行1列 -> 0行2列 -> 1行2列 -> 2行2列(右下角)

解题

乍一看这题,想起了leetcode-63:不同路径 II这道题,题目背景是一样的

但是此题,需要求一条路径,因此采用动态规划不太合适,可以采用记忆化递归+深度优先搜索+回溯

方法一:记忆化递归+回溯

由于只要找到一个路径,因此回溯具有返回值bool

由于初始加入{0,0},对于结果,如果返回true,则为path,否则为{}

if(i==m-1&&j==n-1&&obstacleGrid[i][j]==0) 一定要补充obstacleGrid[i][j]==0,因为如果终点是障碍的,显然是不行的

由于,每个格子(i,j)可能会重复访问到,之前访问过,就说明这条路线不通。因此当(i,j)朝2个方向遍历完后,没有返回true,那么就visited[i][j]=true;标记已访问,可以大大减少时间复杂度。

写法一:

class Solution {
public:
    vector<vector<int>> path;
    bool backtracing(vector<vector<int>>& obstacleGrid,vector<vector<int>>& dirs,int m,int n,int i,int j,vector<vector<bool>>& visited){
        if(i==m-1&&j==n-1&&obstacleGrid[i][j]==0){
            return true;
        }
        else if(i>=m||j>=n) return false;
        for(vector<int>& dir:dirs){
            if(obstacleGrid[i][j]||visited[i][j]) break;
            i+=dir[0];
            j+=dir[1];
            path.push_back({i,j});
            if(backtracing(obstacleGrid,dirs,m,n,i,j,visited)) return true;
            i-=dir[0];
            j-=dir[1];
            path.pop_back();
        }
        visited[i][j]=true;//记忆化
        return false;
    }
    vector<vector<int>> pathWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m=obstacleGrid.size();
        int n=obstacleGrid[0].size();
        vector<vector<int>> dirs={{1,0},{0,1}};
        path.push_back({0,0});
        vector<vector<bool>> visited(m,vector<bool>(n,false));
        if(backtracing(obstacleGrid,dirs,m,n,0,0,visited)) return path;
        else return {};
    }
};

写法二:

更加简洁的写法,每次递归,都先处理,当前对应的(i,j)

而上面一种写法是提前将下一次递归的内容加入到path中去。

class Solution {
public:
    vector<vector<int>> path;
    bool backtracing(vector<vector<int>>& obstacleGrid,int m,int n,int i,int j,vector<vector<bool>>& visited){
        if(i>=m||j>=n||obstacleGrid[i][j]||visited[i][j]) return false;
        path.push_back({i,j});
        if(i==m-1&&j==n-1||backtracing(obstacleGrid,m,n,i+1,j,visited)||backtracing(obstacleGrid,m,n,i,j+1,visited)) return true;
        path.pop_back();
        visited[i][j]=true;
        return false;
    }
    vector<vector<int>> pathWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m=obstacleGrid.size();
        int n=obstacleGrid[0].size();
        vector<vector<bool>> visited(m,vector<bool>(n,false));
        backtracing(obstacleGrid,m,n,0,0,visited);
        return path;
    }
};


相关文章
|
5月前
|
运维 Kubernetes 负载均衡
K8s 常见面试题,让你求职不迷路
K8s 常见面试题,让你求职不迷路
124 0
|
10月前
|
机器人
剑指Offer - 面试题13:机器人的运动范围
剑指Offer - 面试题13:机器人的运动范围
65 0
|
10月前
|
机器人 Java Python
leetcode每日一题.面试题13:机器人的运动范围
leetcode每日一题.面试题13:机器人的运动范围
51 0
|
11月前
|
算法 机器人 C++
【每日算法Day 94】经典面试题:机器人的运动范围
【每日算法Day 94】经典面试题:机器人的运动范围
|
11月前
|
算法 机器人
图解LeetCode——面试题13. 机器人的运动范围
图解LeetCode——面试题13. 机器人的运动范围
57 1
|
机器学习/深度学习 自然语言处理 算法
【每日算法Day 94】经典面试题:机器人的运动范围
地上有一个 m 行 n 列的方格,从坐标 [0, 0] 到坐标 [m-1, n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下移动一格(不能移动到方格外),也不能进入行坐标和列坐标的数位之和大于 k 的格子。例如,当 k 为 18 时,机器人能够进入方格 [35, 37] ,因为 3+5+3+7=18。但它不能进入方格 [35, 38],因为 3+5+3+8=19。请问该机器人能够到达多少个格子?
103 0
【每日算法Day 94】经典面试题:机器人的运动范围
|
2月前
|
传感器 人工智能 监控
智能耕耘机器人
智能耕耘机器人
41 3
|
6月前
|
人工智能 自然语言处理 机器人
智能电话机器人核心技术:自然语言处理
什么是自然语言处理? 自然语言处理是计算机科学领域与人工智能领域中的一个重要方向.它研究能实现人与计算机之间用自然语言进行有效通信的各种理论和方法.自然语言处理是一门融语言学、计算机科学、数学于一体的科学.因此,这一领域的研究将涉及自然语言,即人们日常使用的语言,所以它与语言学的研究有着密切的联系,但又有重要的区别. 自然语言处理并不是一般地研究自然语言,而在于研制能有效地实现自然语言通信的计算机系统,特别是其中的软件系统.因而它是计算机科学的一部分. 自然语言处理(NLP)是计算机科学,人工智能,语言学关注计算机和人类(自然)语言之间的相互作用的领域.
|
1月前
|
传感器 人工智能 自然语言处理
智能咖啡厅助手:人形机器人 +融合大模型,行为驱动的智能咖啡厅机器人
智能咖啡厅助手:人形机器人 +融合大模型,行为驱动的智能咖啡厅机器人
智能咖啡厅助手:人形机器人 +融合大模型,行为驱动的智能咖啡厅机器人
|
2月前
|
传感器 机器学习/深度学习 算法
植保机器人具备智能感知与决策能力
植保机器人具备智能感知与决策能力
17 2