题解 | #迷宫问题#

import math
#乱写一通，。。想了很久，感觉有bug，，可能会卡在迷宫里，测试案例是通过了。。。
n,m = map(int,input().split())
a =[[i for i in range(m)] for i in range(n)]
for i in range(n):
    a[i] = list(map(int,input().split()))
#取可移动方向
def D(i,j):
    if  i+1 <n and a[i+1][j]==0:
        return [[i+1,j],[(n-(i+1))**2+(m-j)**2]]
    else:
        return [0]
def L(i,j):
    if j-1>=0 and a[i][j-1]==0:
        return [[i,j-1],[(n-i)**2+(m-j+1)**2]]
    else:
        return [0]
def R(i,j):
    if j+1<m and a[i][j+1]==0:
        return [[i,j+1],[(n-i)**2+(m-j-1)**2]]
    else:
        return [0]
def U(i,j):
    if i-1 >=0 and a[i-1][j]==0:
        return [[i-1,j],[(n-i+1)**2+(m-j)**2]]
    else:
        return [0]
#想通过距离排序优先走路路线，没什么卵用
def move(i,j):
    k=[U(i,j),L(i,j),R(i,j),D(i,j)]
    while [0] in k:
        k.remove([0])
    f=sorted(k,key =lambda x:x[1])
    return f
jd ={}
#给定每个位置的可以通过的次数，要等于他可以选择移动方向的次数，超过了不给通过了。。
for i in range(n):
    for j in range(m):
        if a[i][j]==0:
            k = move(i, j)
            jd[i, j] = jd.get((i, j), 0) + len(k)
i,j=0,0
l={}
lj =[]
lj.append((0,0))
while i<n and j<m:
    #通过一次计数一次  l是路径经过位置计数列表
    l[i,j]=l.get((i,j),0)+1
    f =move(i,j)
    #通过经过的次数取优先级，次数越少优先取
    k=[[item[0],l.get((item[0][0],item[0][1]),0)] for item in move(i,j)]
    k =sorted(k,key = lambda x:x[1])
    #某个位置通过次数大于限定值，把可选移动方案中的位置删除，不让通过
    for idx,ik in enumerate(k):
        if l.get((ik[0][0],ik[0][1]),0) >0:
            if l.get((ik[0][0],ik[0][1]),0)>=jd.get((ik[0][0],ik[0][1]),0):
                k[idx]=[0]
    if [0] in k:
        k.remove([0])
    i=k[0][0][0]
    j=k[0][0][1]
    lj.append((i,j))
    if i==n-1 and j==m-1:
        break
d ={}
for i in range(len(lj)):
    for j in range(len(lj)-1,i,-1):
        if lj[i] ==lj[j]:
            d[(i,j)] =j-i

a=sorted(d.items(),key = lambda x:x[1])
#如果路径上某2个位置的值相同，重复经过，可以压缩路径取最小路径
if len(a)>0:
    f1,f2 =a[-1][0]
    lj=lj[0:f1]+lj[f2:]

for i in lj:
    print('('+str(i[0])+','+str(i[1])+')')