题解 | #走迷宫#

因为方向可以上下左右，所以不能用基础的dp方式。可以用BFS的思路，主要是要把访问过的位置过滤

import sys
import collections
lineidx = 0
r = 0
c = 0
points = []
arr = []
for line in sys.stdin:
    if lineidx == 0:
        a = line.split()
        r= int(a[0])
        c = int(a[1])
        arr = [[1 for _ in range(c)] for i in range(r)]
    elif lineidx == 1:
        a = line.split()
        points = [int(i) for i in a]
    else:
        for j in range(len(line)):
            if line[j] == ".":
                arr[lineidx-2][j] = 0
    lineidx = lineidx + 1
#print(arr)
def short(g,point):
    que=collections.deque()
    que.append([(point[0] - 1, point[1] - 1, 0)]) 
    visit=set()
    visit.add((point[0] - 1, point[1] - 1))
    while len(que)>0 and len(que[0])>0:
        tmp=[]
        groupi = que.pop()
        for (x, y, prestep) in groupi: 
            if x == point[2] - 1 and y == point[3] - 1:
                return prestep
            for d in [[0, 1], [0, -1], [1, 0], [-1, 0]]: 
                ni,nj=x+d[0],y+d[1]
                if (ni,nj) not in visit and ni>=0 and ni<r and nj>=0 and nj<c and g[ni][nj]==0:
                    tmp.append((ni,nj,prestep+1))
                    visit.add((ni,nj)) 
        que.append(tmp)
    return -1
print(short(arr,points))