题解 | #迷宫问题#

def find_mg(start_x, start_y, end_x, end_y, mg_list, step_list):
    step_list_tmp = step_list
    if start_x == end_x and start_y == end_y:   # 结束条件
        return step_list

    list_tmp = []   # 存储上下左右的返回值
    # 往4个放下走
    # 上     # 没有越界，且可走，并且不是已走过的
    if start_x > 0 and mg_list[start_x-1][start_y] == 0 and (start_x-1, start_y) not in step_list_tmp:
        up = find_mg(start_x-1, start_y, end_x, end_y, mg_list, step_list+[(start_x-1, start_y)])
    else:
        up = None
    if up:
        step_list.append((start_x-1, start_y))
        list_tmp.append(up)
    # 下     # 没有越界，且可走，并且不是已走过的
    if start_x < end_x and mg_list[start_x+1][start_y] == 0 and (start_x+1, start_y) not in step_list_tmp:
        down = find_mg(start_x+1, start_y, end_x, end_y, mg_list, step_list+[(start_x+1, start_y)])
    else:
        down = None
    if down:
        step_list.append((start_x+1, start_y))
        list_tmp.append(down)
    # 左     # 没有越界，且可走，并且不是已走过的
    if start_y > 0 and mg_list[start_x][start_y-1] == 0 and (start_x, start_y-1) not in step_list_tmp:
        left = find_mg(start_x, start_y-1, end_x, end_y, mg_list, step_list+[(start_x, start_y-1)])
    else:
        left = None
    if left:
        step_list.append((start_x, start_y - 1))
        list_tmp.append(left)
    # 右     # 没有越界，且可走，并且不是已走过的
    if start_y < end_y and mg_list[start_x][start_y+1] == 0 and (start_x, start_y+1) not in step_list_tmp:
        right = find_mg(start_x, start_y+1, end_x, end_y, mg_list, step_list+[(start_x, start_y+1)])
    else:
        right = None
    if right:
        step_list.append((start_x, start_y + 1))
        list_tmp.append(right)
    res = []
    for i in list_tmp:
        if i[-1][0] == end_x and i[-1][1] == end_y:
            res.append(i)
    if len(res) >= 1:
        return sorted(res, key=lambda x: -len(x))[0]
    else:
        return None


def func():
    while True:
        try:
            m, n = map(int, input().split())
            mg = []
            for i in range(m):  # 迷宫矩阵
                mg.append(list(map(int, input().split())))

            step_list = [(0, 0)]
            min_path = find_mg(0, 0, m-1, n-1, mg, step_list)
            for i in min_path:
                print('({},{})'.format(i[0], i[1]))
        except:
            break


if __name__ == '__main__':
    func()