题解 | 迷宫

import sys
from collections import deque
def judge(rset,cset,visits):
    # 判断从行集合和列集合打激光能不能碰到visits的点
    # 先判断行集合
    for rs in rset:
        if 1 in visits[rs]:
            return 1
        elif rs-1>=0 and 1 in visits[rs-1]:
            return 1
        elif rs+1<r and 1 in visits[rs+1]:
            return 1
    # 再判断列集合
    for cs in cset:
        if 1 in [row[cs] for row in visits] :
            return 1
        elif cs-1>=0 and 1 in [row[cs-1] for row in visits]:
            return 1
        elif cs+1<c and 1 in [row[cs+1] for row in visits]:
            return 1
    return 0

    pass
r, c = map(int,input().split())
data = []
for _ in range(r):
    data.append(list(input()))
dirs = [(1,0),(0,1),(-1,0),(0,-1)]
start = []
end = []
for i in range(r):
    for j in range(c):
        if data[i][j] == 'S':
            start = [i,j]
        elif data[i][j] == 'E':
            end = [i,j]

q = deque()
visits = [[0]*c for _ in range(r)]
q.append(start)
visits[start[0]][start[1]] = 1
while q:
    x, y = q.popleft()
    for dx,dy in dirs:
        nx, ny = x+dx, y +dy
        if nx == end[0] and ny == end[1]:
            print('YES')
            exit()
        if 0<=nx<r and 0<=ny<c and data[nx][ny]=='.':
            q.append([nx,ny])
            visits[nx][ny] = 1
            data[nx][ny] = '#'

q = deque()
# visite = [[0]*c for _ in range(r)]
q.append(end)
rset = set()
cset = set()
rset.add(end[0])
cset.add(end[1])
while q:
    x, y = q.popleft()
    for dx,dy in dirs:
        nx, ny = x+dx, y +dy
        if 0<=nx<r and 0<=ny<c and data[nx][ny]=='.':
            q.append([nx,ny])
            rset.add(nx)
            cset.add(ny)
            data[nx][ny] = '#'
# print(rset,cset)
# print(visits)

res= judge(rset,cset,visits)
if res:
    print('YES')
else:
    print('NO')