迷路的机器人
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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!