迷路的机器人

2023-12-13 11:43:00

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


网格中的障碍物和空位置分别用 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列(右下角)
说明:r 和 c 的值均不超过 100。

def pathWithObstacles(obstacleGrid):
        path = [] # 路径记录
        n = len(obstacleGrid) # 矩阵长度
        m = len(obstacleGrid[0]) # 矩阵宽度
        def dfs(x,y):
            if x >= n or y >= m: # 边界直接返回
                return False
            if obstacleGrid[x][y] in [1,-1]: # 遇到障碍或者走过,直接返回
                return False
            obstacleGrid[x][y] = -1 # 可走,标记当前的点表示已走过
            path.append([x,y]) # 路径增加当前的点
            if x == n -1 and y == m-1: # 走到终点
                return True
            if dfs(x,y+1) or dfs(x+1,y): # 搜索下面路径和右边路径,通路返回成功
                return True
            else: 
                path.pop()  #  没有通路,路径清除当前的点
        dfs(0,0)
        return path
grid = eval(input())
print(pathWithObstacles(grid))

文章来源:https://blog.csdn.net/m0_73811154/article/details/134844326
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。