首页 > 试题广场 >

迷宫问题

[编程题]迷宫问题

热度指数：221307 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

$\hspace{15pt}$ 有一个 $h$ 行 $w$ 列的网格，我们使用 $(i,j)$ 表示网格中从上往下数第 $i$ 行和从左往右数第 $j$ 列的单元格。每个方格要么是可以通过的空方格 $\texttt{`0'}$ ，要么是不可通过的墙方格 $\texttt{`1'}$ ，特别的，网格的四周都是墙方格，你可以沿着空方格上下左右随意移动：从 $(x,y)$ 向上移动一格即抵达 $(x-1,y)$ 、向下移动一格即抵达 $(x+1,y)$ 、向左移动一格即抵达 $(x,y-1)$ 、向右移动一格即抵达 $(x,y+1)$ 。

$\hspace{15pt}$ 现在，你位于迷宫的入口 $(0,0)$ ，想要前往终点 $(h-1,w-1)$ 。请输出一条从起点到终点的可行路径。

$\hspace{15pt}$ 保证起点和终点一定为空方格，你始终可以找到且能唯一找到一条从起点出发到达终点的可行路径。

输入描述:

第一行输入两个整数  代表迷宫的行数和列数。
此后  行，第  行输入  个整数  代表迷宫的布局。其中， 表示单元格  是空方格， 表示单元格  是墙方格。

输出描述:

输出若干行，第  行输出两个整数  ，表示路径的第  步抵达的单元格坐标为  。

你需要保证输出的路径是符合题目要求的，即从起点  出发，到达终点  ，且路径上每个单元格都是空方格，行走的单元格都是彼此相邻的。

示例1

输入

输出

(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)

示例2

输入

输出

(0,0)
(1,0)
(2,0)
(3,0)
(4,0)
(4,1)
(4,2)
(4,3)
(4,4)

算法知识视频讲解

Python3

玻璃气泡

h, w = map(int, input().split())
a = []
visited = [[False] * w for _ in range(h)]
for _ in range(h):
    a.append(list(map(int, input().split())))
res = []

def dfs(a: list, i: int, j: int, visited:list, current: list, res:list):
    if i == h-1 and j == w-1:
        current.append((i,j))
        res.append(current.copy())
        return

    if i < 0&nbs***bsp;j < 0&nbs***bsp;i >= h&nbs***bsp;j >= w:
        return

    if a[i][j] == 0 and not visited[i][j]:
        visited[i][j] = True
        current.append((i,j))
        dfs(a, i - 1, j, visited,current,res)
        dfs(a, i + 1, j, visited,current,res)
        dfs(a, i, j - 1, visited,current,res)
        dfs(a, i, j + 1, visited,current,res)
        current.pop()
        visited[i][j] = False

dfs(a, 0, 0, visited, [], res)
for i in range(len(res[0])):
    print(f"({res[0][i][0]},{res[0][i][1]})")

发表于 2025-05-02 22:26:56 回复(0)

Python3

颜星河

h, w = map(int, input().split())
a = []
path = []
for _ in range(h):
    a.append(list(input().split()))


def migong(x, y, a, path):
    if 0 <= x < len(a) and 0 <= y < len(a[0]) and a[x][y] == "0":
        path.append((x, y))
        if x == len(a) - 1 and y == len(a[0]) - 1:
            return path
        a[x][y] = "1"
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            new_path = migong(x + dx, y + dy, a, path.copy())
            if new_path:
                return new_path
    return None


path = migong(0, 0, a, path)
for i in path:
    print('({},{})'.format(i[0], i[1]))

记录生活

发表于 2025-04-09 00:24:01 回复(0)

Python3

Linzs

a=list(map(int,input().split()))
b=[]
c=[[0,0]] #路径
silu=[] #死路集
for i in range(a[0]):
    b.append(list(map(int,input().split())))

while c[-1] != [a[0]-1,a[1]-1] :
    z=c[-1]
    y=c[-1][0]
    x=c[-1][1]
    if 0 <= c[-1][0] +1 <= a[0] - 1 and b[c[-1][0] +1][c[-1][1]] != 1 and [y+1,x] not in silu and c.count(z) < 2:
        c.append([y+1,x])
    elif 0 <= c[-1][1] +1 <= a[1] - 1 and b[c[-1][0]][c[-1][1] +1] != 1 and [y,x+1] not in silu and c.count(z) < 2:
        c.append([y,x+1])
    elif 0 <= c[-1][0] -1 <= a[0] - 1 and b[c[-1][0] -1][c[-1][1]] != 1 and [y-1,x] not in silu and c.count(z) < 2:
        c.append([y-1,x])
    elif 0 <= c[-1][1] -1 <= a[1] - 1 and b[c[-1][0]][c[-1][1] -1] != 1 and [y,x-1] not in silu and c.count(z) < 2:
        c.append([y,x-1])
    else:
        silu.append(c.pop())
for i in c :
    print(str(tuple(i)).replace(' ',''))

发表于 2025-02-20 16:03:19 回复(0)

Python3

Do_my_best

import sys
def node_nei(node:tuple):
    dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    i, j = node
    neis = []
    for dir in dirs:
        next_node = (i + dir[0], j + dir[1])
        if 0 <= next_node[0] <= m-1 and 0 <= next_node[1] <= n-1 and maze[next_node[0]][next_node[1]] == 0 and next_node not in visited:
            neis.append(next_node)
    return neis
def dfs(start:tuple, goal:tuple):
    queue = [[start]]
    while queue:
        path = queue.pop()
        node = path[-1]
        if node == goal:
            return path
        neis = node_nei(node)
        if neis != []:
            for nei in neis:
                new_path = list(path)
                new_path.append(nei)
                queue.append(new_path)
                visited.add(nei)
    return 'no way'
m ,n = map(int, input().split())
maze = []
for line in sys.stdin:
    a = line.split()
    if a != []:
        maze.append(list(map(int, a)))
start = (0,0)
goal = (m-1, n-1)
visited = set()
visited.add(start)
a = dfs(start, goal)
for loc in a:
    print (f'({loc[0]},{loc[1]})')

发表于 2024-11-22 09:40:55 回复(0)

Python3

说什么AI

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]})")

发表于 2024-10-14 18:14:58 回复(0)

Python3

Afterland

import sys

n,m = map(int,input().split())

p = []

for line in sys.stdin:

p.append(line.split())

# dfs找最短路径，记录路径，例如字典 i:j 表示从j到i

p[0][0]='1'

def dfs(n,m):

a = [[0,0,0]] #存放路径,i,j,k

road = dict()

diretions =[(0,1),(1,0),(0,-1),(-1,0)]

while a:

b = a.pop(0)

if b[0]==n-1 and b[1]==m-1:

break

for i,j in diretions:

di = i+b[0]

dj = j+b[1]

if 0<=di<n and 0<=dj<m and p[di][dj]=='0':

p[di][dj]='1'

a.append([di,dj,b[2]+1])

road[(di,dj)] = (b[0],b[1])

res = []

i,j = n-1,m-1

for _ in range(b[2]):

res.append((i,j))

i,j = road[(i,j)]

res.append((0,0))

res.reverse()

return res

res = dfs(n,m)

for i in res:

print('('+str(i[0])+','+str(i[1])+')')

发表于 2024-09-25 13:43:06 回复(0)

Python3

组合鳄鱼

def getPath(i,j,n,m,mg,path,res):

if not 0<=i<n or not 0<=j<m or mg[i][j]==1 or [i,j] in path:

return

path.append([i,j])

if i==n-1 and j==m-1:

for c in path:

res.append(c)

return

getPath(i,j+1,n,m,mg,path,res)

getPath(i,j-1,n,m,mg,path,res)

getPath(i+1,j,n,m,mg,path,res)

getPath(i-1,j,n,m,mg,path,res)

path.pop()

发表于 2024-09-22 16:56:11 回复(0)

Python3

三天三题

BFS需要保存路径，可以单独写一个数组变量保存，这里我直接保存在队列中。

import collections

m,n = map(int, input().split())

grid = []

for _ in range(m):

grid.append(list(map(int, input().split())))

def bfs(grid, m, n):

visited = set()

visited.add((0,0))

queue = collections.deque()

queue.append((0, 0, [(0,0)]))

directions = [[1,0],[0,1],[-1,0],[0,-1]]

while queue:

r, c, path = queue.popleft()

if r == m -1 and c == n - 1:

return path

for dr, dc in directions:

row, col = dr + r, dc + c

if row in range(m) and col in range(n) and (row,col) not in visited and grid[row][col] == 0:

queue.append((row,col, path + [(row, col)]))

visited.add((row,col))

return []

path = bfs(grid, m, n)

for p in path:

print(f"({p[0]},{p[1]})")

发表于 2024-06-23 13:23:26 回复(1)

Python3

在写日记的鸽子很神奇

# 尝试使用了BFS广度优先的思想

# 1. 每个节点考虑上下左右四个朝向，但是要注意不要和倒数第二个节点的方向相同

# 2. 如果有一条路径被率先搜索到，那他一定是最短的。因为广度优先，其余还没找到终点的路径最多只可能和你当前路径等长

import sys
import copy as cp

def solutation(maze_, n, m):
    routes = [
        [(0, 0)]
    ]
    res = None
    while len(routes) > 0:
        new_routes = []
        for route in routes:
            route:list
            prev_i, prev_j = -1, -1
            i, j = route[-1]
            if len(route) > 1:
                prev_i, prev_j = route[-2]

            if i == n-1 and j == m-1:
                res = route
                break

            # 遭遇墙壁, 剪去该分支
            if maze_[i][j] == 1:
                continue

            # 朝上进行探索
            if i - 1 >= 0 and i - 1 != prev_i:
                route_cp = cp.deepcopy(route)
                route_cp.append((i-1, j))
                new_routes.append(route_cp)

            # 朝下进行探索
            if i + 1 < n and i + 1 != prev_i:
                route_cp = cp.deepcopy(route)
                route_cp.append((i+1, j))
                new_routes.append(route_cp)

            # 朝左探索
            if j -1 >= 0 and j -1 != prev_j:
                route_cp = cp.deepcopy(route)
                route_cp.append((i, j-1))
                new_routes.append(route_cp)

            # 朝右探索
            if j +1 < m and j +1 != prev_j:
                route_cp = cp.deepcopy(route)
                route_cp.append((i, j+1))
                new_routes.append(route_cp)

        if res is not None:
            break
        
        routes = new_routes
    return res

n, m = input().split()
n, m = int(n), int(m)
maze = []
for i in range(0, n):
    maze.append(
    [int(i) for i in sys.stdin.readline().split()]
    )
route = solutation(maze, n, m)
for node in route:
    x, y = node
    print(f"({x},{y})")

发表于 2024-01-05 17:27:09 回复(0)

Python3

铺洒日光

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]})')

发表于 2023-09-25 19:47:17 回复(2)

Python3

YM学渣

广度优先搜索（bfs), 主要还可以用来寻找最短路径，不过本题也只有一条路径

from collections import deque

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

q = deque([[(0,0)]])
visited = [(0,0)] # 记录遍历过的点

while q:
    x = q.popleft()
    # 如果到达终点(m-1,n-1),输出路径
    if x[-1] == (m-1,n-1):
        for i in x:
            print(f"({i[0]},{i[1]})")
        break
    # (r,c)
    # 向上
    if 0<= x[-1][0]-1 and maze[x[-1][0]-1][x[-1][1]] == 0:
        if (x[-1][0]-1,x[-1][1]) not in visited:
            q.append(x+[(x[-1][0]-1,x[-1][1])])
            visited.append((x[-1][0]-1,x[-1][1]))
    # 向下
    if x[-1][0]+1 < m  and maze[x[-1][0]+1][x[-1][1]] == 0:
        if (x[-1][0]+1,x[-1][1]) not in visited:
            q.append(x+[(x[-1][0]+1,x[-1][1])])
            visited.append((x[-1][0]+1,x[-1][1]))
    # 向左
    if 0 <= x[-1][1]-1 and maze[x[-1][0]][x[-1][1]-1] == 0:
        if (x[-1][0],x[-1][1]-1) not in visited:
            q.append(x+[(x[-1][0],x[-1][1]-1)])
            visited.append((x[-1][0],x[-1][1]-1))
    # 向右
    if x[-1][1]+1 < n and maze[x[-1][0]][x[-1][1]+1] == 0:
        if (x[-1][0],x[-1][1]+1) not in visited:
            q.append(x+[(x[-1][0],x[-1][1]+1)])
            visited.append((x[-1][0],x[-1][1]+1))

深度优先搜索（dfs），主要用来遍历所有路径

# 深度优先搜索
def fn(r,c,l=[(0,0)]):
    if 0 <= c-1  and maze[r][c-1] == 0:
        if (r,c-1) not in l:
            fn(r,c-1,l+[(r,c-1)])

    if 0 <= r-1  and maze[r-1][c] == 0:
        if (r-1,c) not in l:
            fn(r-1,c,l+[(r-1,c)])
    
    if c+1 < len(maze[0]) and maze[r][c+1] == 0:
        if (r,c+1) not in l:
            fn(r,c+1,l+[(r,c+1)])

    if r+1 < len(maze) and maze[r+1][c] == 0:
        if (r+1,c) not in l:
            fn(r+1,c,l+[(r+1,c)])
    
    if r==m-1 and c==n-1:
        for i in l:
            print(f"({i[0]},{i[1]})")

m,n = map(int,input().split())

maze = []
for i in range(m):
    maze.append(list(map(int,input().split())))
fn(0,0)

发表于 2023-07-26 14:37:24 回复(1)

Python3

阿左。

bfs

def fn(lq,maze,vis):
    if len(lq) > 0:
        i,j = lq[0]
        vis = maze[i][j]+1
        if i < n-1&nbs***bsp;j < m-1:
            if i+1 < n:
                if maze[i+1][j] == 0:
                    lq.append([i+1,j])
                    maze[i+1][j] = vis
            if j+1 < m:
                if maze[i][j+1] == 0:
                    lq.append([i,j+1])
                    maze[i][j+1] = vis
            if i-1 >= 0:
                if maze[i-1][j] == 0:
                    lq.append([i-1,j])
                    maze[i-1][j] = vis 
            if j-1 >= 0:
                if maze[i][j-1] == 0:
                    lq.append([i,j-1])
                    maze[i][j-1] = vis
            lq.pop(0)
            fn(lq,maze,vis)

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

lqueue = [[0,0]]
maze[0][0] = 2
# 标记路线 每次+1  及路线上的值为[2,3,4,5,6,7,..,n+m]

fn(lqueue,maze,maze[0][0]+1)

ans = [[n-1,m-1]]
# 从右下角遍历回左上角
while ans[-1][0] > 0&nbs***bsp;ans[-1][1] > 0:
    i,j = ans[-1]
    vis = maze[i][j]
    if i-1 >= 0:
        if maze[i-1][j] == vis-1:
            ans.append([i-1,j])
            continue
    if j-1 >=0:
        if maze[i][j-1] == vis-1:
            ans.append([i,j-1])
            continue
    if i+1 < n:
        if maze[i+1][j] == vis-1:
            ans.append([i+1,j])
            continue
    if j+1 < m:
        if maze[i][j+1] == vis-1:
            ans.append([i,j+1])
            continue

ans.reverse()
for item in ans:
    print(f'({item[0]},{item[1]})')

发表于 2023-07-21 21:35:09 回复(0)

Python3

1bit都不剩了

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(" ",""))

发表于 2023-07-21 17:18:22 回复(0)

Python3

小白码代码

#小分享一波思路

# 接收行列参数
a, b = map(int, input().split())
route_list = []
for i in range(a):
    route_list.append(list(map(int, input().split())))

lis = []
lis.append((0,0))

def check_loc(x,y):
    # 防止移动越界
    global a
    global b
    if x < 0:
        x = 0
    elif x >= a-1:
        x = a-1
    if y < 0:
        y = 0
    elif y >= b-1:
        y = b-1
    return x,y

while True:
    x, y = lis[-1]
    if x == a - 1 and y == b -1:
        for i in lis:
            print(f"({i[0]},{i[1]})")
        break
    # 向右移动
    x1,y1 = check_loc(x,y+1)
    if route_list[x1][y1] == 0:
        lis.append((x1,y1))
        route_list[x1][y1] = 2
        continue

    # 向下移动
    x1,y1 = check_loc(x+1,y)
    if route_list[x1][y1] == 0:
        lis.append((x1,y1))
        route_list[x1][y1] = 2
        continue

    # 向上移动
    x1,y1 = check_loc(x-1,y)
    if route_list[x1][y1] == 0:
        lis.append((x1,y1))
        route_list[x1][y1] = 2
        continue
    
    # 向左移动
    x1,y1 = check_loc(x,y-1)
    if route_list[x1][y1] == 0:
        lis.append((x1,y1))
        route_list[x1][y1] = 2
        continue
    lis.pop()

发表于 2023-07-09 12:42:53 回复(2)

Python3

Shiningyoo

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]})")

发表于 2023-06-06 17:42:16 回复(1)