题解 | 迷宫

from collections import deque

def bfs(start_x:int, start_y:int, maze:list, n:int, m:int):
    dist = [[-1]*m for _ in range(n)]
    dist[start_x][start_y] = 0
    q = deque()
    q.append((start_x, start_y))
    while q:
        x, y = q.popleft()
        for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
            nx, ny = x+dx, y+dy
            if 0<=nx<n and 0<=ny<m and maze[nx][ny] != '#' and dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx, ny))
    return dist


def can_connect_by_laser(n: int, m: int, maze: list, dist_S: list, dist_E: list) -> bool:
    # 收集S可达点的所有行和列编号
    X = set()
    Y = set()
    for i in range(n):
        for j in range(m):
            if dist_S[i][j] >= 0:
                X.add(i)
                Y.add(j)
    # 遍历所有E可达点，看其周围行/列是否与S的集合有交集
    for i in range(n):
        for j in range(m):
            if dist_E[i][j] >= 0:
                for dx in [-1, 0, 1]:
                    if 0 <= i + dx < n and (i + dx) in X:
                        return True
                for dy in [-1, 0, 1]:
                    if 0 <= j + dy < m and (j + dy) in Y:
                        return True
    return False

                
def main():
    n, m = map(int, input().split())
    maze = [list(input().strip()) for _ in range(n)]
    Sx = Sy = Ex = Ey = -1
    for i in range(n):
        for j in range(m):
            if maze[i][j] == 'S':
                Sx, Sy = i, j
                maze[i][j] = '.'
            elif maze[i][j] == 'E':
                Ex, Ey = i, j
                maze[i][j] = '.'

    dist_S = bfs(Sx, Sy, maze, n, m)
    dist_E = bfs(Ex, Ey, maze, n, m)
    # 如果起点终点本身连通，无需激光
    if dist_S[Ex][Ey] != -1:
        print("YES")
        return
    # 不连通的话，就要判断激光
    if can_connect_by_laser(n, m, maze, dist_S, dist_E):
        print("YES")
        return
    else:
        print("NO")
        return

if __name__ == "__main__":
    main()