题解 | 走迷宫

import sys
from collections import deque

r , c = map(int,input().split())
sx,sy,ex,ey = map(int,input().split())
grid = []
for _ in range(r):
    grid.append(list(input()))
# print(grid)
if grid[sx-1][sy-1] == '*' or  grid[ex-1][ey-1] == '*':
    print('-1')
    exit()
dirs = [(1,0), (-1,0), (0,1), (0,-1)]

# BFS
q = deque()
q.append((sx-1, sy-1))
grid[sx-1][sy-1] = '*'  # 标记走过
dist = [[0]*c for _ in range(r)]  # 记录到起点的距离

while q:
    x,y = q.popleft()
    if x == ex-1 and y==ey-1:
        print(dist[x][y])
        exit()

    for dx, dy in dirs:
        nx, ny = x+dx, y+dy
        if 0<=nx<r and 0<=ny<c and grid[nx][ny]=='.':
            q.append((nx,ny))
            dist[nx][ny] = dist[x][y]+1
            grid[nx][ny] = '*'
print('-1')
exit()