题解 | 走迷宫

import sys
from collections import deque

n,m = map(int,input().split())
xs,ys,xt,yt = map(int,input().strip().split())
xs-=1; ys-=1; xt-=1; yt-=1
# print(xs,ys,xt,yt)

grid = []
for _ in range(n):
    grid.append(input().strip())

steps = 0
dirs = [(-1,0),(1,0),(0,-1),(0,1)]
# bfs 初始化
queue = deque()
visted = [[False]*m for _ in range(n)]
queue.append((xs,ys,steps))
visted[xs][ys] = True

found = False
result = -1

while queue:
    x,y,steps = queue.popleft()

    if x==xt and y==yt: # 出口
        found = True
        result = steps
    
    for dx,dy in dirs:
        nx,ny = x+dx,y+dy
        if 0<=nx<n and 0<=ny<m:
            if not visted[nx][ny] and grid[nx][ny] == '.':
                queue.append((nx,ny,steps+1))
                visted[nx][ny] = True

if not found:
    print(-1)
else:
    print(result)