weixin_51343465
weixin_51343465
2021-05-24 10:23
采纳率: 50%
浏览 60

迷宫问题,需要用递归

1. 简答题 问题描述:一只老鼠在一个n×n迷宫的入口处,它想要吃迷宫出口处放着奶酪,问这只老鼠能否吃到奶酪?如果可以吃到,请给出一条从入口到奶酪的路径。 思考:解决问题之前,我们首先要做的就是仔细研究问题,找出问题的已知条件和要得到的是什么。和解数学问题、物理问题一样要先弄懂问题。那么,老鼠走迷宫问题的已知条件有什么呢? 数学模型重新定义问题: 问题:问老鼠能否吃到奶酪就是问能否找到一条从迷宫入口到出口的路径。如果不能找到,那么老鼠就吃不到奶酪;如果能够找到,那么就给出这条路径。 观察10×10的迷宫。这个迷宫其实是由10×10=100个格子组成的,其中绿色格子代表墙,白色格子代表路,如图(1)所示。“绿色格子代表墙,白色格子代表路”是用语言形式描述的,需要转换成数学的形式。用1和0分别定义绿色格子和白色格子,可以得到如图(2)的迷宫。 将上面10×10的迷宫定义为如下的二维数组,即 m[10][10]=[1,1,1,0,1,1,1,1,1,1, 1,0,0,0,0,0,0,0,1,1, 1,0,1,1,1,1,1,0,0,1, 1,0,1,0,0,0,0,1,0,1, 1,0,1,0,1,1,0,0,0,1, 1,0,0,1,1,0,1,0,1,1, 1,1,1,1,0,0,0,0,1,1, 1,0,0,0,0,1,1,1,0,0, 1,0,1,1,0,0,0,0,0,1, 1,1,1,1,1,1,1,1,1,1] 有了对迷宫的数学定义,就可以很简单的定义迷宫的入口和出口了。迷宫的入口是m[0][3],出口是m[7][9]。老鼠走迷宫问题就是要找一条从入口到出口的路径,如果存在就返回这条路径;如果不存在,就返回不存在这种路径。也就是说,要在二维数组m中找一条从m[0][3]到m[7][9]全部为0的路径。 请使用递归解决迷宫路径查找问题。

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新

  • xufive
    天元浪子 2021-05-24 15:31
    已采纳
    def maze(m, n, route, pos, export):
        """走迷宫
        
        m       - 迷宫数组,列表
        n       - 迷宫阶数
        route   - 可能的路线,列表
        pos     - 当前位置,元组
        export  - 出口位置,元组
        """
        
        route.append(pos)
        if pos == export:
            print(route)
        
        if pos[0] > 0 and m[pos[0]-1][pos[1]] == 0 and (pos[0]-1,pos[1]) not in route:
            maze(m, n, route[:], (pos[0]-1,pos[1]), export)
        
        if pos[0] < n-1 and m[pos[0]+1][pos[1]] == 0 and (pos[0]+1,pos[1]) not in route:
            maze(m, n, route[:], (pos[0]+1,pos[1]), export)
        
        if pos[1] > 0 and m[pos[0]][pos[1]-1] == 0 and (pos[0],pos[1]-1) not in route:
            maze(m, n, route[:], (pos[0],pos[1]-1), export)
        
        if pos[1] < n-1 and m[pos[0]][pos[1]+1] == 0 and (pos[0],pos[1]+1) not in route:
            maze(m, n, route[:], (pos[0],pos[1]+1), export)
        
        #print('此路不通')
        
    m = [
        [1,1,1,0,1,1,1,1,1,1], 
        [1,0,0,0,0,0,0,0,1,1], 
        [1,0,1,1,1,1,1,0,0,1], 
        [1,0,1,0,0,0,0,1,0,1], 
        [1,0,1,0,1,1,0,0,0,1], 
        [1,0,0,1,1,0,1,0,1,1], 
        [1,1,1,1,0,0,0,0,1,1], 
        [1,0,0,0,0,1,1,1,0,0], 
        [1,0,1,1,0,0,0,0,0,1], 
        [1,1,1,1,1,1,1,1,1,1] 
    ]
    
    maze(m, len(m), list(), (0,3), (7,9))

    运行结果:

    [(0, 3), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (2, 7), (2, 8), (3, 8), (4, 8), (4, 7), (5, 7), (6, 7), (6, 6), (6, 5), (6, 4), (7, 4), (8, 4), (8, 5), (8, 6), (8, 7), (8, 8), (7, 8), (7, 9)]
    点赞 1 评论

相关推荐