迷宫问题

from collections import deque

m,n = map(int, input().split())
maze = []

def bfs(maze, start, target):
    queue = deque([start])
    visited = []
    director = [(0,1), (0,-1), (-1,0), (1,0)]
    while queue:
        node = queue.popleft()
        visited.append(node)
        i, j = node
        maze[i][j] = -1  # 已访问过的节点不可再次访问
        if node == target:
            return visited

        for x in director:
            i, j = node
            i = i + x[0]
            j = j + x[1]
            if 0 <= i < m and 0 <= j < n and maze[i][j] == 0:
                queue.append((i,j))
    return "no way"

for i in range(m):
    maze.append([int(i) for i in input().split()])

visited = bfs(maze, (0,0), (m - 1,n - 1))
# 找成功路径
visited = visited[::-1]
target = visited[0]
route = []
route.append(target)
for x in visited:
    if (abs(x[0]-route[-1][0])==1 and  x[1]==route[-1][1])&nbs***bsp;(x[0]==route[-1][0] and abs(x[1]-route[-1][1]) == 1):
        route.append(x)
for i in route[::-1]:
    print(f"({i[0]},{i[1]})")

h, w = list(map(int, input().strip().split(" ")))
map_num = []
for i in range(h):
    map_num.append(list(map(int, input().strip().split(" "))))
route = []


def find_route(coordi_pair, up=0, down=0, left=0, right=0):
    if coordi_pair == [h - 1, w - 1]:
        return 1
    if up == 0 and down == 0 and left == 0 and right == 0:
        down_num = (
            map_num[coordi_pair[0] + 1][coordi_pair[1]] if coordi_pair[0] + 1 < h else 1
        )
        right_num = (
            map_num[coordi_pair[0]][coordi_pair[1] + 1] if coordi_pair[1] + 1 < w else 1
        )
        if down_num == 0:
            if (
                find_route(
                    [coordi_pair[0] + 1, coordi_pair[1]], up=1
                )
                == 1
            ):
                route.append((coordi_pair[0] + 1, coordi_pair[1]))
                return 1
        if right_num == 0:
            if find_route([coordi_pair[0], coordi_pair[1] + 1], left=1) == 1:
                route.append((coordi_pair[0], coordi_pair[1] + 1))
                return 1
        return -1
    if up == 1:
        down_num = (
            map_num[coordi_pair[0] + 1][coordi_pair[1]] if coordi_pair[0] + 1 < h else 1
        )
        right_num = (
            map_num[coordi_pair[0]][coordi_pair[1] + 1] if coordi_pair[1] + 1 < w else 1
        )
        left_num = (
            map_num[coordi_pair[0]][coordi_pair[1] - 1]
            if coordi_pair[1] - 1 >= 0
            else 1
        )
        if down_num and right_num and left_num:
            return -1
        if down_num == 0:
            if find_route([coordi_pair[0] + 1, coordi_pair[1]], up=1) == 1:
                route.append((coordi_pair[0] + 1, coordi_pair[1]))
                return 1
        if right_num == 0:
            if find_route([coordi_pair[0], coordi_pair[1] + 1], left=1) == 1:
                route.append((coordi_pair[0], coordi_pair[1] + 1))
                return 1
        if left_num == 0:
            if find_route([coordi_pair[0], coordi_pair[1] - 1], right=1) == 1:
                route.append((coordi_pair[0], coordi_pair[1] - 1))
                return 1
    if down == 1:
        up_num = (
            map_num[coordi_pair[0] - 1][coordi_pair[1]]
            if coordi_pair[0] - 1 >= 0
            else 1
        )
        right_num = (
            map_num[coordi_pair[0]][coordi_pair[1] + 1] if coordi_pair[1] + 1 < w else 1
        )
        left_num = (
            map_num[coordi_pair[0]][coordi_pair[1] - 1]
            if coordi_pair[1] - 1 >= 0
            else 1
        )
        if up_num and right_num and left_num:
            return -1
        if up_num == 0:
            if find_route([coordi_pair[0] - 1, coordi_pair[1]], down=1) == 1:
                route.append((coordi_pair[0] - 1, coordi_pair[1]))
                return 1
        if right_num == 0:
            if find_route([coordi_pair[0], coordi_pair[1] + 1], left=1) == 1:
                route.append((coordi_pair[0], coordi_pair[1] + 1))
                return 1
        if left_num == 0:
            if find_route([coordi_pair[0], coordi_pair[1] - 1], right=1) == 1:
                route.append((coordi_pair[0], coordi_pair[1] - 1))
                return 1
    if left == 1:
        up_num = (
            map_num[coordi_pair[0] - 1][coordi_pair[1]]
            if coordi_pair[0] - 1 >= 0
            else 1
        )
        down_num = (
            map_num[coordi_pair[0] + 1][coordi_pair[1]] if coordi_pair[0] + 1 < h else 1
        )
        right_num = (
            map_num[coordi_pair[0]][coordi_pair[1] + 1] if coordi_pair[1] + 1 < w else 1
        )
        if down_num and right_num and up_num:
            return -1
        if down_num == 0:
            if find_route([coordi_pair[0] + 1, coordi_pair[1]], up=1) == 1:
                route.append((coordi_pair[0] + 1, coordi_pair[1]))
                return 1
        if right_num == 0:
            if find_route([coordi_pair[0], coordi_pair[1] + 1], left=1) == 1:
                route.append((coordi_pair[0], coordi_pair[1] + 1))
                return 1
        if up_num == 0:
            if find_route([coordi_pair[0] - 1, coordi_pair[1]], down=1) == 1:
                route.append((coordi_pair[0] - 1, coordi_pair[1]))
                return 1
    if right == 1:
        up_num = (
            map_num[coordi_pair[0] - 1][coordi_pair[1]]
            if coordi_pair[0] - 1 >= 0
            else 1
        )
        down_num = (
            map_num[coordi_pair[0] + 1][coordi_pair[1]] if coordi_pair[0] + 1 < h else 1
        )
        left_num = (
            map_num[coordi_pair[0]][coordi_pair[1] - 1]
            if coordi_pair[1] - 1 >= 0
            else 1
        )
        if down_num and up_num and left_num:
            return -1
        if down_num == 0:
            if find_route([coordi_pair[0] + 1, coordi_pair[1]], up=1) == 1:
                route.append((coordi_pair[0] + 1, coordi_pair[1]))
                return 1
        if up_num == 0:
            if find_route([coordi_pair[0] - 1, coordi_pair[1]], down=1) == 1:
                route.append((coordi_pair[0] - 1, coordi_pair[1]))
                return 1
        if left_num == 0:
            if find_route([coordi_pair[0], coordi_pair[1] - 1], right=1) == 1:
                route.append((coordi_pair[0], coordi_pair[1] - 1))
                return 1
find_route((0, 0))
route.append((0, 0))
route.reverse()
for item in route:
    print(f'({item[0]},{item[1]})')

dfs

def dfs(maze_mat,routes,p = (0,0)):
    routes.append(p)
    if((p[0] == len(maze_mat)-1)and(p[1]==len(maze_mat[0])-1)): return True
    if((p[0] < 0) or (p[1] < 0) or (p[0] >= len(maze_mat)) or (p[1]>=len(maze_mat[0])) or (maze_mat[p[0]][p[1]]==1)):
        routes.pop()
        return False
    for dir_vec in ((1,0),(-1,0),(0,1),(0,-1)):
        next_p = (p[0]+dir_vec[0],p[1]+dir_vec[1])
        if(next_p in routes): continue              # 防成环
        if(dfs(maze_mat,routes,next_p) == True): return True
    routes.pop()
    return False

maze_height = int(input().split()[0])
maze_mat = []
for i in range(maze_height):
    maze_mat.append(list(map(int,input().split())))

routes = []
dfs(maze_mat,routes)
for p in routes: print(str(p).replace(" ",""))

n, m = map(int, input().split())
nums = []
for i in range(n):
    nums.append([int(i) for i in input().split()])

route = []

def dfs(i, j):
    if nums[i][j] == 1:
        return False
    if i == n - 1 and j == m - 1:
        return True
    nums[i][j] = 1
    for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
        if -1 < x < n and -1 < y < m and dfs(x, y):
            route.append((x, y))
            return True

dfs(0, 0)

for i in [(0, 0)] + route[::-1]:
    print(f"({i[0]},{i[1]})")

# 采用动态规划的方法

import sys

'''
1. dp[i][j]表示走到 [i,j]这个位置需要的最小步数,初始赋值一个达不到的最大值，此处采用 m*n+1, dp[0][0]=1
2. 递推关系 dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i+1][j]+1, dp[i][j+1]+1)，即判断[i,j]上下左右四个方向
的最小值中一步再加一步
3. 更新dp[i][j],有些值可能第一次循环没有更新到，所以需要多次循环，直到dp[i][j]没有变化。此处采用hash存储可能更加节省计算量
'''

# 读取数据，并给动态规划赋值
m, n = map(int, input().split())
path = []
maze = []
dp = []

max_val = m * n + 1
for i in range(m):
    maze.append(list(map(int, input().split())))
    dp.append([max_val] * n)


# 更新dp[i][j]
has_updated = True
dp[0][0] = 1
while has_updated:
    has_updated = False
    for i in range(m):
        for j in range(n):
            if maze[i][j] == 1: # 障碍物，用最大值代替
                dp[i][j] = max_val
                continue
            elif dp[i][j] < max_val:  # 已经更新过的路径不再更新，如果要求最小路径，可能需要调整。
                continue
            else:
                prev = dp[i][j]
                # 四个方向上的值，抵达不了的用最大值代替
                a = max_val if j == 0 else dp[i][j - 1] + 1
                b = max_val if i == 0 else dp[i - 1][j] + 1
                c = max_val if i == m - 1 else dp[i + 1][j] + 1
                d = max_val if j == n - 1 else dp[i][j + 1] + 1
                dp[i][j] = min(a, b, c, d)
                if prev != dp[i][j]:  # 判断是否存在元素更新
                    has_updated = True


# 基于dp[i][j]反向计算来时候的路径，存储到path中
i = m - 1
j = n - 1
path.append([i, j])
while i+j>0:
    if i > 0 and dp[i - 1][j] == dp[i][j] - 1:
        path.append([i - 1, j])
        i -= 1
    elif j > 0 and dp[i][j - 1] == dp[i][j] - 1:
        path.append([i, j - 1])
        j -= 1
    elif i < m - 1 and dp[i + 1][j] == dp[i][j] - 1:
        path.append([i + 1, j])
        i += 1
    elif j < n - 1 and dp[i][j + 1] == dp[i][j] - 1:
        path.append([i, j + 1])
        j += 1

#逆向打印path
for i, j in path[::-1]:
    print("({},{})".format(i, j))