迷宫问题

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

def dfs(x,y,k):
    if not 0 <= x < n&nbs***bsp;not 0 <= y < m&nbs***bsp;matrix[x][y] == 1&nbs***bsp;(x,y) in k:
        return False 
    if x == n-1 and y == m-1:
        k = k+[(x,y)]
        for i in range(len(k)):
            print('('+str(k[i][0])+","+str(k[i][-1])+')')

    res = dfs(x+1,y,k+[(x,y)])&nbs***bsp;dfs(x-1,y,k+[(x,y)])&nbs***bsp;dfs(x,y+1,k+[(x,y)])&nbs***bsp;dfs(x,y-1,k+[(x,y)])
    return res 

dfs(0,0,[])

'''简单易懂，就是从起始点宽度优先往后探索没有探索过的点，直到终点被探索到'''

class luji:
    def __init__(self, lujin):
        self.lujin=lujin;

def explore(n,l,a,i,j,tt):
    if (i+1<n[0] and a[i+1][j]=='0'):
        a[i+1][j]='1'
        l[i+1][j].lujin=l[i][j].lujin+[[i+1,j]]
        tt.append([i+1,j])
    if (i-1>=0 and a[i-1][j]=='0'):
        a[i-1][j]='1'
        l[i-1][j].lujin=l[i][j].lujin+[[i-1,j]]
        tt.append([i-1,j])
    if (j+1<n[1] and a[i][j+1]=='0'):
        a[i][j+1]='1'
        l[i][j+1].lujin=l[i][j].lujin+[[i,j+1]]
        tt.append([i,j+1])
    if (j-1>=0 and a[i][j-1]=='0'):
        a[i][j-1]='1'
        l[i][j-1].lujin=l[i][j].lujin+[[i,j-1]]
        tt.append([i,j-1])
    
while True:
    try:
        n=input().strip(' ').split(' ')
        n[0]=eval(n[0])
        n[1]=eval(n[1])
        a=[]
        for i in range(n[0]):
            t=input().strip(' ').strip('\r').split(' ')
            a.append(t)
        a[0][0]='1'
        ting=[[0,0]]
        l=[]
        for i in range(n[0]):
            l.append([])
            for j in range(n[1]):
                l[i].append(luji([]))
        l[0][0].lujin=[[0,0]]
        while a[-1][-1]=='0':
            tt=[]
            for i in ting:
                explore(n,l,a,i[0],i[1],tt)
            ting=tt
        for i in l[-1][-1].lujin:
            print("({},{})".format(i[0],i[1]))
    except:
        break

因为题目说了，只有一条有效路径，那么我们可以直接使用 dfs 搜索，而可以不用标准的 bfs 来找最短路径。

下面是不带剪枝策略的 dfs 回溯算法，非常直观，直接套用回溯算法模板即可。
代码清晰可读。

import sys


def print_result(path):
    for item in path:
        print('({},{})'.format(item[0], item[1]))


def min_path(maze, visited, path, m, n, i, j):
    if i >= m or j >= n or i < 0 or j < 0:
        return
    if visited[i][j]:
        return 
    if maze[i][j] == 1:
        return
    if i == m-1 and j == n-1 and maze[i][j] == 0:
        path.append((i, j))
        print_result(path)
        return

    path.append((i, j))
    visited[i][j] = True
    min_path(maze, visited, path, m, n, i+1, j)
    min_path(maze, visited, path, m, n, i-1, j) 
    min_path(maze, visited, path, m, n, i, j+1)
    min_path(maze, visited, path, m, n, i, j-1)
    path.pop()
    visited[i][j] = False


def get_input():
    m, n = list(map(int, input().strip().split()))

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

    return maze, m, n


if __name__ == '__main__':
    try:
        while True:
            maze, m, n = get_input()
            row = [False for _ in range(n)]
            visited = [row.copy() for _ in range(m)]    
            path = []
            min_path(maze, visited, path, m, n, 0, 0)
    except Exception:
        pass

鄙人认为本题出的一般，只有一条路径走得通为什么还要说求最短路径，而且只有一条路径走得通也让大家可以投机取巧，不用广度、深度优先搜索就能出结果（看已通过的代码）；

附上本人的广度优先搜索代码：

def bfs(maze,x1,y1,x2,y2):
    directions = [(1,0),(-1,0),(0,1),(0,-1)]
    queue = [(x1,y1,-1)]
    path = []
    while queue:
        path.append(queue.pop(0))
        cur = (path[-1][0],path[-1][1])
        if cur == (x2,y2):
            res = [(path[-1][0],path[-1][1])]
            loc = path[-1][2]
            while loc != -1:
                res.append((path[loc][0],path[loc][1]))
                loc = path[loc][2]
            return res

        for d in directions:
            next_node = (cur[0]+d[0],cur[1]+d[1])
            if 0 <= next_node[0] < len(maze) and \
               0 <= next_node[1] < len(maze[0]) and \
               maze[next_node[0]][next_node[1]] == 0:
                maze[next_node[0]][next_node[1]] == 2
                queue.append((next_node[0],next_node[1],len(path)-1))
while True:
    try:
        m,n = list(map(int, input().split()))
        maze = []
        for i in range(m):
            maze.append(list(map(int, input().split())))
        res = bfs(maze, 0, 0, m-1, n-1)[::-1]
        for i in res:
            print('(%d,%d)'%(i[0],i[1]))
    except:
        break

def solve(maze,n,m):
    #标准回溯法解，用yield
    #mark标记走过的点
    mark=[[0 for i in range(m)]  for j in range(n)]
    #path表示当前路径
    path=[]
    #迭代器求解，x，y是下一步的坐标
    def subsolve(x,y):
        #到终点
        if (x,y)==(n-1,m-1):
            path.append((x,y))
            #这里特别重要！
            #一定要深复制！
            yield path[:]
            #注意pop回溯
            path.pop()
        #非法路径
        elif x>=n&nbs***bsp;y>=m&nbs***bsp;x<0&nbs***bsp;y<0 :
            yield []
        elif maze[x][y]==1&nbs***bsp;mark[x][y]==1:
            yield []
        #当前步合法
        else:
            path.append((x,y))
            mark[x][y]=1
            for i,j in ((0,1),(1,0),(-1,0),(0,-1)):
                #遍历迭代器！
                for tem in  subsolve(x+i, y+j):
                    if  tem:
                        #迭代器
                        yield tem
            #弹出
            path.pop()
            mark[x][y]=0

    minpathl = n*m
    minpath = []
    for tem in subsolve(0, 0):
        if len(tem)<minpathl:
            minpathl=len(tem)
            minpath=tem
    return(minpath)

while True:
    try:
        line=input().strip().split()
        n=int(line[0])
        m=int(line[1])
        maze=[]
        for i in range(n):
            line=input().strip().split()
            maze.append([int(i) for i in line])
        ans=solve(maze, n, m)
        for i in ans:
            print('({0},{1})'.format(i[0],i[1]))
    except:
        break
        

while True:
    try:
        lines, rows = map(int, input().split())
        matrix = []
        for i in range(lines):
            matrix.append(list(map(int, input().split())))
            
        def find(l, r):
            if (l, r) == (lines-1, rows-1):
                return ["({},{})".format(l, r)]
            if matrix[l][r] == 1:
                return []
            if l<lines-1 and find(l+1, r):
                return ["({},{})".format(l, r)] + find(l+1, r)
            elif r<rows-1 and find(l, r+1):
                return ["({},{})".format(l, r)] + find(l, r+1)
            else:
                return []
            
        root = find(0, 0)
        for p in root:
            print(p)
    except:
        break

while True:
    try:
        r,c = map(int,input().split())
        arr = [list(map(int, input().split())) for i in range(r)]

        nl=[]
        vl=[]
        nl.append([(0,(0,0))])
        vl.append((0,0))
        sl=[]
        index=0
        while True:
            l=nl[-1]
            ll=[]
            for i,node in enumerate(l):
                no = node[1]
                if no[0]+1<r and arr[no[0]+1][no[1]] !=1 and (no[0]+1,no[1]) not in vl:
                    ll.append((i,(no[0]+1,no[1])))
                    vl.append((no[0]+1,no[1]))
                if no[1]+1<c and arr[no[0]][no[1]+1] !=1 and (no[0],no[1]+1) not in vl:
                    ll.append((i,(no[0],no[1]+1)))
                    vl.append((no[0],no[1]+1))
                if no[0]-1>=0 and arr[no[0]-1][no[1]] !=1 and (no[0]-1,no[1]) not in vl:
                    ll.append((i,(no[0]-1,no[1])))
                    vl.append((no[0]-1,no[1]))
                if no[1]-1>=0 and arr[no[0]][no[1]-1] !=1 and (no[0],no[1]-1) not in vl:
                    ll.append((i,(no[0],no[1]-1)))
                    vl.append((no[0],no[1]-1))
            nl.append(ll)
            if (r-1,c-1) in vl:
                break
        sl.append((r-1,c-1))
        ln=nl[-1]
        for e in ln:
            if e[1]==(r-1,c-1):
                index=e[0]
        for i in range(2,len(nl)+1):
            tarn=nl[-i]
            tar = tarn[index]
            sl.append(tar[1])
            index=tar[0]
        for e in sl[::-1]:
            print('(' + str(e[0]) + ',' + str(e[1]) + ')')
    except:
        break

import sys
import copy


def get_miniest_path(migong, cur_row, cur_col, cur_path):
    n_row = len(migong)
    n_col = len(migong[0])

    migong[cur_row][cur_col] = 1
    cur_path.append((cur_row, cur_col))
    if cur_row == n_row - 1 and cur_col == n_col - 1:
        return
    # right
    if (cur_col + 1 < n_col and migong[cur_row][cur_col + 1] == 0):
        get_miniest_path(migong, cur_row, cur_col + 1, cur_path)
    # left
    elif (cur_col - 1 >= 0 and migong[cur_row][cur_col - 1] == 0):
        get_miniest_path(migong, cur_row, cur_col - 1, cur_path)
    # down
    elif (cur_row + 1 < n_row and migong[cur_row+1][cur_col] == 0):
        get_miniest_path(migong, cur_row + 1, cur_col, cur_path)
    # up
    elif (cur_row - 1 >= 0 and migong[cur_row-1][cur_col] == 0):
        get_miniest_path(migong, cur_row - 1, cur_col, cur_path)
    else:
        # a dead zone, restore.
        migong[cur_row][cur_col] = 0
        cur_path.pop(-1)


migongs = []
shapes = []
while True:
    try:
        num_row, num_col = tuple(map(int, sys.stdin.readline().strip().split()))
        shapes.append((num_row, num_col))
        for _ in range(num_row):
            migongs.append(list(map(int, sys.stdin.readline().strip().split())))
    except:
        break

start = 0
for (num_row, num_col) in shapes:
    migong = migongs[start: start + num_row]
    start += num_row
    cur_path = []

    get_miniest_path(migong, 0, 0, cur_path)
    for p in cur_path:
        print("({},{})".format(*p))

from collections import deque
MAX_VALUE = float('inf')

class Point:
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y

def bfs(maps, begin, end):
    # 用来保存起点到各个位置的最小距离,同时还能用来判断某个点是否被访问过
    dist = [[MAX_VALUE] * m for _ in range(n)]
    # 当前点的上一个点,用于输出路径轨迹
    pre = [[None]*m for _ in range(n)]

    dx = [1, 0, -1, 0]  # 四个方位
    dy = [0, 1, 0, -1]
    # 起点坐标
    startx, starty = begin.x, begin.y
    # 终点坐标
    endx, endy = end.x, end.y

    # 起点到起点的距离初始化为0
    dist[startx][starty] = 0
    queue = deque()
    # 将起点入队列
    queue.append(begin)
    while queue:
        curr = queue.popleft()
        find = False  # 标志位，用于标志是否能够找到一个路径
        # 向四个方向进行试探
        for k in range(4):
            newx, newy = curr.x + dx[k], curr.y + dy[k]
            # 在迷宫内，且当前位置可走，且没有访问过，将其压入队列
            if 0 <= newx < n and 0 <= newy < m and maps[newx][newy] != 1 and dist[newx][newy] == MAX_VALUE:
                dist[newx][newy] = dist[curr.x][curr.y] + 1  # 更新最短距离
                pre[newx][newy] = curr  # 记录前继节点
                # print(pre[newx][newy].x, pre[newx][newy].y)
                queue.append(Point(newx, newy))  # 将该点压入队列中
                # 如果已经到达终点位置
                if newx == endx and newy == endy:
                    find = True
                    break
        if find:
            break

    stack = []
    curr = end

    while True:
        # 先把最后一个点压入栈中
        stack.append(curr)
        if curr.x == begin.x and curr.y == begin.y:
            break
        prev = pre[curr.x][curr.y]

        curr = prev

    while stack:
        curr = stack.pop()
        #print('(%d, %d)' % (curr.x, curr.y))
        print('(' + str(curr.x) + ',' + str(curr.y) + ')')


if __name__ == "__main__":
    # 输入
    n, m = map(int, input().split())
    # maps是地图，visit是访问过的数组
    maps = [[0]*m for _ in range(n)]
    begin = Point()
    end = Point()
    for i in range(n):
        nums = list(map(int, input().split()))
        maps[i] = nums

    # 起点坐标和终点坐标
    begin.x, begin.y = 0,0
    end.x, end.y = n-1, m-1

    bfs(maps, begin, end)

请问我这个在本地打印输出没问题，提交通过是0%,是很么原因？

def dfs(data, i, j, m, n, tmp, res):
    if i > m or j > n or i < 0 or j < 0 or data[i][j] == 1:
        return 0
    tmp.append([i, j])
    if i == m and j == n:
        res.append(tmp)
        return 1

    return dfs(data, i + 1, j, m, n, tmp[:], res) or dfs(data, i, j + 1, m, n, tmp[:], res)

while True:
    try:
        
        m, n = list(map(int, input().split()))
        data = []
        for i in range(m):
            data.append(list(map(int, input().split())))
        tmp = []
        res = []
        dfs(data, 0, 0, m - 1, n - 1, tmp, res)
        for i, j in res[0]:
            print("(%d,%d)" % (i, j))
    except:
        break

deals = [
    lambda x, y: [x + 1, y],  # 向下
    lambda x, y: [x, y + 1],  # 向右
    lambda x, y: [x - 1, y],  # 向上
    lambda x, y: [x, y - 1],  # 向左
]
# 这个顺序有讲究，下右上左可以保证最短路径的节点总是会被优先尝试

def deal_maze(start, end, maze):
    path = [start]  # 走过的路径
    maze[0][0] = 2  # 走过的路径标记为2
    while len(path) > 0:
        cur_node = path[-1]
        if cur_node[0] == end[0] and cur_node[1] == end[1]:
            # 如果当前节点已经到end位置，说明走出了迷宫
            for i in path:
                print("(" + str(i[0]) + "," + str(i[1]) + ")")
        for deal in deals:  # 从上下左右四个方向尝试一遍
            next_node = deal(cur_node[0], cur_node[1])
            if 0 <= next_node[0] <= end[0] and 0 <= next_node[1] <= end[1]:
                # 判断有没有出迷宫
                if maze[next_node[0]][next_node[1]] == 0:  # 坐标为（0,0）的为未走过的通道
                    path.append(next_node)
                    maze[next_node[0]][next_node[1]] = 2  # 走过的路径标记为（2,2）
                    break
        else:
            path.pop()  # 如果for循环正常结束而非break跳出，说明此路不通或者已经找到完整路径了


while True:
    try:
        [a, b] = list(map(int, input().split()))  # a为行，b为列
        input_maze = []  # 迷宫矩阵
        for i in range(a):
            input_maze.append([int(j) for j in input().split()])
        deal_maze([0, 0], (a - 1, b - 1), input_maze)
    except:
        break

这是一段其他作者的代码，在提交的python3答案中排在首位，可惜原创是谁已经无从查证了，非常佩服作者的精妙的思维，因此根据自己的理解添加了一些注释。

def path(maze):
    all_path = []
    N,M = len(maze),len(maze[0])
    range_x = list(range(0,N))
    range_y = list(range(0,M))
    def search(route:list,now:tuple):
        if now==(N-1,M-1):
            all_path.append(route)
            return
        x,y = now
        if x+1 in range_x:
            if maze[x+1][y] != 1 and (x+1,y) not in route:
                newroute = route.copy()
                newroute.append((x+1,y))
                search(newroute,(x+1,y))
        if y+1 in range_y:
            if maze[x][y+1] != 1 and (x,y+1) not in route:
                newroute = route.copy()
                newroute.append((x,y+1))
                search(newroute,(x,y+1))
    search([(0,0)],(0,0))
    return all_path
while 1:
    try:       
        M,N = tuple(map(int,input().split()))
        mylist = []
        for i in range(M):
            mylist.append(list(map(int,input().split())))
        Path = path(mylist)
        for i,j in Path[0]:
            print('({0},{1})'.format(i,j))
    except:
        break

dirs = [(0,1),(1,0),(0,-1),(-1,0)]    
def mark(maze,pos):                  
    maze[pos[0]][pos[1]] = 2
def passable(maze,pos):              
    if pos[0]>m-1 or pos[1]>n-1 or pos[0]<0 or pos[1]<0:            
    return maze[pos[0]][pos[1]] == 0
def find_path(maze,pos,end):
    mark(maze,pos)
    if pos == end:                                      
        res.append(pos)                               
        return True                                    
    for i in range(4):                                  
        nextp = pos[0]+dirs[i][0],pos[1]+dirs[i][1]
        if passable(maze,nextp):                        
            if find_path(maze,nextp,end):
                res.append(pos)
                return True
    return False
while True:
    try:
        m, n = input().strip().split()
        m, n = int(m), int(n)
        maze = []
        res=[]
        for i in range(m):
            maze.append(list(map(int, input().strip().split())))
        find_path(maze,pos=(0,0),end=(m-1,n-1))
        for i in range(len(res)-1,-1,-1):
            print('({},{})'.format(res[i][0], res[i][1]))
    except:
        break

while True:
    try:
        R, C = map(int, input().split())
        mat = [[] for _ in range(R)]
        for i in range(R):
            mat[i] = list(map(int, input().split()))
        res = [[99 for _ in range(C+1)] for _ in range(R+1)]
        res[0][1] = 0
        res[1][0] = 0
        for i in range(1,R+1):
            for j in range(1,C+1):
                if mat[i-1][j-1] == 0:
                    res[i][j] = min(res[i-1][j], res[i][j-1])+1
                    if res[i][j]<99:
                        print('('+str(i-1)+','+str(j-1)+')')
    except:
        break