题解 | 走迷宫

import sys

n, m = map(int, input().split(' '))
vis = [[0 for i in range(1100)] for i in range(1100)]
mp = []
xs, ys, xt, yt = map(int, input().split(' '))
for i in range(n):
    r = input()
    mp.append(r)
xs, ys, xt, yt = xs-1, ys-1, xt-1,yt-1
q = []
q.append((xs, ys, 0))
nxt = ((1, 0), (-1, 0), (0, 1), (0, -1))

while q:
    pos = q.pop(0)
    x, y, z = pos[0], pos[1], pos[2]
    if vis[x][y]: continue
    vis[x][y] = z
    if x == xt and y == yt:
        print(z)
        break
    for i in range(4):
        xx, yy = x + nxt[i][0], y + nxt[i][1]
        if xx < 0 or yy < 0 or xx == n or yy == m: continue 
        if vis[xx][yy] or mp[xx][yy] == '*' : continue
        q.append((xx, yy, z+1))


if vis[xt][yt] == 0:
    print(-1)

bfs模板题目，注意起始坐标和数组的对应，我这里的数组都是下标从0开始，而起始坐标从1开始，所以有：

xs, ys, xt, yt = xs-1, ys-1, xt-1, yt-1