题解 | #迷宫问题#

迷宫问题

http://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc

dfs的方法,此题相当于一个四叉树,每次可以选择走上下左右任何方向,只要不越界。如果发现某条路径不通,需要注意把该不通路径中所有的轨迹删掉。

a, b = map(int, str(input()).split())
route_c = []#存放走过的轨迹
maze = []#接收输入数组
path = [[0 for i in range(b)] for i in range(a)]#记录哪个轨迹点曾经走过,确保不走回头路
#path = np.zeros([a, b])
#print(path)
for j in range(a):
    l = [i for i in list(map(int, str(input()).split()))]
    maze.append(l)


def find_r(m, n, route_c):
    #nonlocal route_c
    #route_c_l = route_c
    if maze[m][n] == 1:
        return
    else:
        route_c.append([m, n])
        path[m][n] = 1
    if m == a-1 and n == b-1:
        for ele in route_c:
            print('(' + str(ele[0])+','+str(ele[1])+')')
        return
    l_rc = len(route_c)
    #back_r = -1 if l_rc<2 else route_c[-2][0]
    if m < a-1 and path[m+1][n] == 0 :
        find_r(m+1, n, route_c)
        #l_rc = 2
        route_c = route_c[:l_rc]#能够走到这一步,说明该路径不通,则把轨迹点都删掉。
    l_rc = len(route_c)
    if n < b-1 and path[m][n+1] == 0 :
        find_r(m, n+1, route_c)
        route_c = route_c[:l_rc]
    l_rc = len(route_c)
    if m > 0 and path[m-1][n] == 0:
        find_r(m-1, n, route_c)
        route_c = route_c[:l_rc]
    l_rc = len(route_c)
    if n > 0 and path[m][n-1] == 0:
        find_r(m, n-1, route_c)
        route_c = route_c[:l_rc]
find_r(0, 0, route_c)
全部评论

相关推荐

10-25 14:25
门头沟学院 C++
投的服务端研发岗,基本上就只问了实习和简历,啥八股都没有,也没给算法题,然后就结束了
ngiv:你看看别人面经就知道了, 拼多多三面很多主管面, 基本上就是20分钟纯聊天, 当然也看到有问了一个小时的
点赞 评论 收藏
分享
牛客915519934号:差不多得了 ,真以为我们好忽悠呢?当初就是听了你们的话没有赶上风口入行Java,现在还想再忽悠我呢?这明显就是一个新风口,国家大力发展制造业,以后这个圈子的钱只会越来越多,不管是入门还是大佬,只要进来少说有你一口饭吃,一个个自私自利自己上了车就劝退其他人,钱都让你赚得了呗。就这点东西,入门很容易的,学个pcb,单片机就可以去找工作了,少说一万五起,以后只会越来越高,以后想进阶就去FPGA,linux,给的钱吊打互联网,再说说你们一直说数电模电难?实际呢也不过一个月就能拿下的事情,你不需要学的多深,只需要入门就足够了,就按我说的学出来少说两万起,最好报个培训班,入门更快,兄弟们跟着我冲就完事了,趁着这个机会,狠狠赚他一笔。
点赞 评论 收藏
分享
1 1 评论
分享
牛客网
牛客企业服务