递归+最短路径 | HJ43 迷宫问题

import copy
def func(migong, i, j, path):
    if (i, j) == (n-1, m-1):
        res.append(copy.deepcopy(path))
        return
    if j+1 < m and migong[i][j+1] != '1' and (i,j+1)not in path:
        path.append((i, j+1))
        func(migong, i, j+1, path)
        path.pop()
    if i+1 < n and migong[i+1][j] != '1' and (i+1,j)not in path:
        path.append((i+1, j))
        func(migong, i+1, j, path)
        path.pop()
    if j-1 >= 0 and migong[i][j-1] != '1' and (i,j-1)not in path:
        path.append((i, j-1))
        func(migong, i, j-1, path)
        path.pop()
    if i-1 >= 0 and migong[i-1][j] != '1' and (i-1,j)not in path:
        path.append((i-1, j))
        func(migong, i-1, j, path)
        path.pop()

while True:
    try:
        n, m = list(map(int, input().split(' ')))
        migong = []
        res = []
        for _ in range(n):
            migong.append(input().split(' '))
        func(migong, 0, 0, [(0,0)])
        min_length, min_path = n*m, None
        for path in res:
            if len(path) < min_length:
                min_length = len(path)
                min_path = path
        for node in min_path:
            print(f'({node[0]},{node[1]})')
    except:
        break

用时:40min

华为笔试刷题 文章被收录于专栏

高质量题: 1~40:HJ16,HJ22,HJ24,HJ26,HJ27,HJ28,HJ35,HJ37,HJ39; 40~80:HJ41,HJ42,HJ43,HJ44,HJ48,HJ50,HJ52,HJ53,HJ57,HJ61,HJ63,HJ64,HJ70,HJ71,HJ74,HJ77; 80~108:HJ82,HJ85,HJ88,HJ89,HJ93,HJ95,HJ98,HJ103,HJ107

全部评论

相关推荐

晗江雪:其实我只是觉得你们导员说的很好笑
点赞 评论 收藏
分享
小浪_Coding:找硬件测试,也可兼顾软测欧, 简历还可以的 ,注意排版,项目写的有条理一点, 然后个人技能多加点, 润色好简历之后就开始沟通海投了,深圳,东莞这边做硬件相关的公司还不少, 医疗类,仪器类的都可以尝试
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务