题解 | #迷宫问题#

import re


m, n = map(int, input().split())
A = []
for _ in range(m):
    A.append(input().split())
# '0' '1'

# 标记访问   路径记录  当前点记录
def bfs(A, i, j):
    m = len(A)
    n = len(A[0])

    if i == m-1 and j == n-1:
        return 0, [(i, j)]
    if i < 0 or i >= m or j < 0 or j >= n or A[i][j] == '1':
        return m*n, None
    #标记访问
    A[i][j] = '1'
    
    # 当前点i,j 到终点的最短记录 和路径
    path = []
    d_min = m*n

    for ai, aj in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
        d_ij, p_ij = bfs(A, ai, aj)
        if d_ij < d_min:
            d_min = d_ij
            path = p_ij

    return d_min+1, [(i, j)] + path


d , path = bfs(A,0,0)

for p in path:
    print("({},{})".format(p[0],p[1]))