迷宫

题目描述：

输入一个二维数组，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
【输入】
一个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
【输出样例】
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

思路

广度优先遍历：用一个列表记录广度优先遍历的节点，每个节点设置一个前向索引记录该节点的父亲节点的位置

import numpy as np
class node:
    def __init__(self, x, y, pre):
        self.x = x
        self.y = y
        self.pre = pre


if __name__ == "__main__":
    puzzle = [
        [0, 1, 0, 1, 0],
        [0, 0, 0, 1, 0],
        [0, 1, 0, 0, 0],
        [0, 0, 0, 1, 0],
    ]
    visit = np.zeros(20).reshape(4, 5)
    pre = 0
    tail = 0
    queue = [node(0, 0, -1)]
    visit[0][0]=1
    tail += 1
    flag = 0

    move = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    while(pre < tail):
        cur = queue[pre]

        for i in range(len(move)):  # 移动
            next_x = cur.x+move[i][0]
            next_y = cur.y+move[i][1]

            if next_x not in range(len(puzzle)) or next_y not in range(len(puzzle[0])):  # 超出边界
                continue

            if not visit[next_x][next_y] and puzzle[next_x][next_y]==0:  # 如果没有访问过且不为0
                visit[next_x][next_y] = 1
                queue.append(node(next_x, next_y, pre))
                tail += 1

            if next_x == len(puzzle)-1 and next_y == len(puzzle[0])-1:  # 如果访问到尾节点，则终止
                flag = 1
                break

        pre += 1

    if flag == 1:
        trace=[]
        cur = queue[-1]
        pre = cur.pre
        while pre != -1:
            trace.append((cur.x,cur.y))
            cur = queue[pre]
            pre = cur.pre
        trace.append((0,0))

        for item in trace[::-1]:
            print(item)
      

当仅仅是求通路不要求最短也可以使用深度优先：一直按同一个方向进行遍历，当遇到不能继续访问的节点时进行回溯

import numpy as np


class Node:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.dir = 1

    def get_dir(self):
        return self.dir

    def change_dir(self):
        self.dir += 1

    

def dfs(puzzle,end_x,end_y):
    start_x = 0
    start_y = 0
    stack = [Node(start_x, start_y)]

    while(stack):
        node = stack[-1]
        direction = node.get_dir()
        x = node.x
        y = node.y

        puzzle[x][y] = 1 #避免重复访问该节点
        if x == end_x and y == end_y:
            return stack

        if direction == 1:
            if x+1 in range(len(puzzle)) and puzzle[x+1][y] == 0: #判断是否越界，以及是否可以经过
                stack.append(Node(x+1, y))
            node.change_dir() # 切换至下一个方向继续运行
            continue
        elif direction == 2:
            if x-1 in range(len(puzzle)) and puzzle[x-1][y] == 0:
                stack.append(Node(x-1, y))
            node.change_dir()
            continue
        elif direction == 3:
            if y+1 in range(len(puzzle[0])) and puzzle[x][y+1] == 0:
                stack.append(Node(x, y+1))
            node.change_dir()
            continue
        elif direction == 4:
            if y-1 in range(len(puzzle[0])) and puzzle[x][y-1] == 0:
                stack.append(Node(x, y-1))
            node.change_dir()
            continue

        node=stack.pop() # 当direction大于等于4证明路径不可达
        puzzle[node.x][node.y]=0 # 当前路径已经不包含该节点，解除该节点的不可访问锁，这样当回溯到这个节点时可以继续访问该节点的另一个方向

    return None


if __name__ == "__main__":
    puzzle = [
        [0, 1, 0, 1, 0],
        [0, 0, 0, 1, 0],
        [0, 1, 0, 0, 0],
        [0, 0, 0, 1, 0],
    ]
    stack = dfs(puzzle, len(puzzle)-1, len(puzzle[0])-1)
    for node in stack:
        print((node.x,node.y))