牛客华为机试-迷宫问题

题目描述

定义一个二维数组N*M（其中2<=N<=10;2<=M<=10），如5 × 5数组下所示：

int maze[5][5] = {

    0, 1, 0, 0, 0,
    0, 1, 0, 1, 0,
    0, 0, 0, 0, 0,
    0, 1, 1, 1, 0,
    0, 0, 0, 1, 0

};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。入口点为[0,0],既第一空格是可以走的路。
Input：
一个N × M的二维数组，表示一个迷宫。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。
Output：
左上角到右下角的最短路径，格式如样例所示。
Sample Input：
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
Sample Output：
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

输入描述:
输入两个整数，分别表示二位数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。

输出描述:
左上角到右下角的最短路径，格式如样例所示。

思路

栈实现深度遍历

代码实现

dirs = [
    lambda x,y:(x+1,y),#下
    # lambda x,y:(x-1,y),#上
    # lambda x,y:(x,y-1),#左
    lambda x,y:(x,y+1)#右
#模拟上下左右
]

def solve_maze(x1,x2,y1,y2):
    stack = []                    #模拟栈
    stack.append((x1,y1))         #放入起始值
    maze[x1][y1] = '2'            #访问过标记为2
    while len(stack) > 0:         #循环访问
        cur_node = stack[-1]      #取栈中最后一个值
        if cur_node == (x2,y2):   #如果到了终点，输出栈中所有元素，并return
            for i in stack:
                print('(' + str(i[0]) + ',' + str(i[1]) + ')')
            return
        for d in dirs:                                             #依次向下向右遍历
            next_node = d(cur_node[0],cur_node[1])                 #取下一结点
            if n > next_node[0] >= 0 and m > next_node[1] >= 0:    #数组越界判断   
                if maze[next_node[0]][next_node[1]] == '0':        
                    #结点内是0则访问置为2，结点入栈
                    stack.append(next_node)
                    maze[next_node[0]][next_node[1]] = '2'
                    break
        else:       #否则退回到上一个访问成功的结点
            stack.pop()
while True:
    try:
        s = list(map(int,input().split()))
        #接收迷宫的维度n，m
        n = s[0]
        m = s[1]
        maze = []
        for i in range(n):
            #接收迷宫的数据
            maze .append(input().split())
        #maze = [[0 0 0 0 1]
                 [1 1 1 0 0]
                 [0 1 0 1 0]]
        #将数据处理成上述形式，用来深度遍历
        solve_maze(0,n-1,0,m-1)
        #调用函数
    except:
        break