题解 | #迷宫问题#

# 一种巨踏马麻烦的办法，写到这里其实可以开始优化了，但是懒得搞了
# 核心想法就是把所有的点先拿出来，然后顺着点走，能走通的最长的路即为解（忘了题目说的只有唯一解，后面有部分处理可以省略）。
# 能走通的路即为解，走不通的路需要舍弃。舍弃的方法就是判断后面的路，只取最长的一条，其余为断路。
# 其次在走路的时候要考虑向右向下、向上和向左的走法，这些走法的前提是前一个走过的点不能和下一步有可能的点一样，否则就是走回头路，会导致无限循环
# 每一种走法需要排除掉其他走法的影响，但是也要考虑其他走法的可能性。其中向上走之后不能再向下走，向左走之后不能再向右走，反之亦然。
# 刚开始思路很容易有，但是处理起来特别麻烦，也想不出其他什么比较精妙的办法，只能死磕，想用数组接收返回值然后往上加，发现行不通，因为输出结果不是tree，多种可能性没想好怎么处理，现在看其实也是可行的
# 最后写了三个mutual recursion的函数，耍了一点小聪明，舍弃了数组直接把结果加起来，然后再分开。可谓无所不用其极，过于复杂了。接下来看看大神的题解开开眼界~
m, n = list(map(int, input().split(' ')))


maze = []

for i in range(m):
    inner = list(map(int, input().split(' ')))
    maze.append(inner)

positions = []

for i in range(len(maze)):
    for j in range(len(maze[i])):
        if maze[i][j] == 0:
            positions.append([i, j])

# print(positions)
def find_path_up(pre_position, position, positions):
    pr = pre_position
    p = position
    p2 = [i for i in positions if (i[1] == p[1] + 1 and i [0] == p[0])]
    p3 = [i for i in positions if (i[0] == p[0] - 1 and i[1] == p[1])]
    p4 = [i for i in positions if (i[1] == p[1] - 1 and i[0] == p[0])]
    # print(pr, p, p2, p3, p4)
    if p == positions[-1]:
        return p
    if p2 and [i for i in p2 if i != pr]:
        p = [p+(find_path(p, i, positions)) for i in p2]
        p = sorted(p, key=lambda x : len(x))
        p = p[-1]
        # print(p)
    elif p3 and [i for i in p3 if i != pr]:
        p = [p+(find_path_up(p, i, positions)) for i in p3]
        p = sorted(p, key=lambda x : len(x))
        p = p[-1]
        # for i in p3:
            # positions = [p for p in positions if p[0] >= i[0] and p[1] >= i[1]]
            # p += (find_path_up(i, positions))
    elif p4 and [i for i in p4 if i != pr]:
        p = [p+(find_path_down(p, i, positions)) for i in p4]
        p = sorted(p, key=lambda x : len(x))
        p = p[-1]
    elif not p2 and not p3:
        pass
    # print(p)
    return p

def find_path_down(pre_position, position, positions):
    pr = pre_position
    p = position
    p2 = [i for i in positions if (i[0] == p[0] + 1 and i[1] == p[1])]
    p3 = [i for i in positions if (i[0] == p[0] - 1 and i[1] == p[1])]
    p4 = [i for i in positions if (i[1] == p[1] - 1 and i[0] == p[0])]
    # print(pr, p, p2, p3, p4)
    if p == positions[-1]:
        return p
    if p2 and [i for i in p2 if i != pr]:
        p = [p+(find_path(p, i, positions)) for i in p2]
        p = sorted(p, key=lambda x : len(x))
        p = p[-1]
        # print(p)
    elif p3 and [i for i in p3 if i != pr]:
        p = [p+(find_path_up(p, i, positions)) for i in p3]
        p = sorted(p, key=lambda x : len(x))
        p = p[-1]
        # for i in p3:
            # positions = [p for p in positions if p[0] >= i[0] and p[1] >= i[1]]
            # p += (find_path_up(i, positions))
    elif p4 and [i for i in p4 if i != pr]:
        p = [p+(find_path_down(p, i, positions)) for i in p4]
        p = sorted(p, key=lambda x : len(x))
        p = p[-1]
    elif not p2 and not p3:
        pass
    # print(p)
    return p

def find_path(pre_position, position, positions):
    pr = pre_position
    p = position
    p2 = [i for i in positions if (i[0] == p[0] + 1 and i[1] == p[1])\
                               or (i[1] == p[1] + 1 and i [0] == p[0])]
    p3 = [i for i in positions if (i[0] == p[0] - 1 and i[1] == p[1])]
    p4 = [i for i in positions if (i[1] == p[1] - 1 and i[0] == p[0])]
    # print(pr, p, p2, p3, p4)
    if p == positions[-1]:
        return p
    if p2 and [i for i in p2 if i != pr]:
        p = [p+(find_path(p, i, positions)) for i in p2]
        p = sorted(p, key=lambda x : len(x))
        p = p[-1]
        # print(p)
    elif p3 and [i for i in p3 if i != pr]:
        p = [p+(find_path_up(p, i, positions)) for i in p3]
        p = sorted(p, key=lambda x : len(x))
        p = p[-1]
        # for i in p3:
            # positions = [p for p in positions if p[0] >= i[0] and p[1] >= i[1]]
            # p += (find_path_up(i, positions))
    elif p4 and [i for i in p4 if i != pr]:
        p = [p+(find_path_down(p, i, positions)) for i in p4]
        p = sorted(p, key=lambda x : len(x))
        p = p[-1]
    elif not p2 and not p3 and not p4:
        pass
    # print(p)
    return p

# try:
res = find_path([], [0, 0], positions)
# print(res)
result = []
for i in range(0, len(res), 2):
    result.append(res[i:i+2])

# print(result)

points = []
for i in range(len(result)):
    if result[i] == [0, 0] or result[i] == positions[-1]:
        points.append(i)

# print(points)

result2 = [result[points[i]:points[i+1]+1] for i in range(len(points)-1)]

# print(result2)
x = sorted([[i, len(result2[i])] for i in range(len(result2))], key=lambda x : x[1])
# print(x)
x = x[-1][0]
result3 = [tuple(i) for i in result2[x]]

# print(result3)

for i in result3:
    print(f'({i[0]},{i[1]})')
# except Exception as error:
#     print(error)