首页 > 试题广场 >

在一个n*m的格子迷宫内，有部分格子可以通过，有部分格子是禁

[问答题]
在一个n*m的格子迷宫内，有部分格子可以通过，有部分格子是禁止通行的，允许上下左右4个方向移动。 假定小强在迷宫中的坐标（i,j）的位置上，从迷宫的任意边界走出即为走出迷宫。请给出小强以最少步骤走出迷宫的算法。
添加回答
一碗阳光头像 一碗阳光
最小生成树，
设置初始标记值flag为1，建立n*m的二维数组，全部初始化为0，障碍物时-1，从小强的位置（i,j）开始（标记为1），每次对四周的四个格子中能到达的格子（不包含到达过得的格子和）标记为flag+1,然后flag自加1，递归标记整个二维数组直到无法到达新的位置或已到达边界，如果到达边界则从第一个到达的边界开始回溯，每次选择周围格子中数字最小的整数，直到走到格子中数字为1的方格为止，此时走的步数即为最小步数，如果走完所有格子都未到达边界，则无法走出。
编辑于 2017-08-23 15:52:58 回复(0)
牛客258995545号头像 牛客258995545号
def minDistance(i,j):
step=0
m=len(grid)
n=len(grid[0])
start_i,start_j=i,j
while  new_i <m and new_y<n:
    
direction=[(0,1),(0,-1),(1,0),(-1,0)]
for x,y in direction:
new_i,new_j= start_i+x,start_j+y
step+=1

发表于 2020-09-09 06:45:56 回复(0)
没错_我就是你的雷哥头像 没错_我就是你的雷哥
a,b,c,d=[向左、向右、向上、向下]
if a=True:
    a=a+1
    if a=0 or a=m:
         return 1
else：
    b=b+1 
    if b=0 or b=m
         return 1
if c=True
    c=c+1
    if c=0 or c=n
         return 1
else:
    d=d+1
     if d=0 or d=n;
     return 1


发表于 2018-04-09 20:45:09 回复(0)
提交观点

问题信息

2017 算法工程师 滴滴
上传者：小小
难度：
3条回答 3603浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号