题解 | #迷宫问题#

import sys


s = list(map(int,input().split())) 
n,m =s[0],s[1]


L=[]
L3=[]

L4=[]
i=1
while  i <=n:
    s = list(map(int,input().split())) 
    L.append(s)
    i+=1

x=[-1,0,1,0]
y=[0,-1,0,1]
def bfs(i,j,n,m):
    distance=[[0 for i in range(m+1)] for j in range(n+1)]
    father = [[0 for i in range(m+1)] for j in range(n+1)]
    distance[i][j]=0
    father[0][0]=[-1,-1]
    L3.append([i,j])

    while L3:
        num=L3.pop(0)
        i,j =num[0],num[1]
        L[i][j]=1
        k=0
        while k<4:
            
            l=i+x[k]
            h=j+y[k]
            k+=1        
            if 0<=l<=n and 0<=h<=m:
                if L[l][h]!=1:
                    distance[l][h]=distance[i][j]+1
                    #添加father二维数组，记录每一个遍历节点的父节点，最后从终点，回朔父节点
                    father[l][h]=[i,j]
                    L3.append([l,h])
    

    #print(father)
    #for a in father:
      #  print()
     #   for i in range(len(a)):
     #       print(a[i],end=" ")
    return father
father = bfs(0,0,n-1,m-1)

#print(father[1][0])

i=n-1
j=m-1
L4=[]
#回朔的时候将当前节点存储的父节点的i,j，然后在father数组中取父节点
while father[i][j]!=[-1,-1]:
    k=father[i][j][0]
    l=father[i][j][1]
    i=k
    j=l
    res = ",".join([str(i),str(j)])
    res =("("+res+")")
    L4.append((res))

for x in L4[::-1]:
    print(x)
res =(",".join([str(n-1),str(m-1)]))
res =("("+res+")")
print(res)