题解 | 迷宫

from collections import deque

# Process input
m, n = map(int, input().split())
mat = [None] * m
start = None
end = None
for i in range(m):
    mat[i] = row = [None] * n
    sRow = input()
    for j in range(n):
        ch = sRow[j]
        if ch == '#':
            row[j] = 1
        elif ch == '.':
            row[j] = 0
        elif ch == 'S':
            row[j] = 0
            start = (i, j)
        elif ch == 'E':
            row[j] = 0
            end = (i, j)

# Algo
def update_range(rg, x, y):
    rg[0] = min(rg[0], x)
    rg[1] = max(rg[1], x)
    rg[2] = min(rg[2], y)
    rg[3] = max(rg[3], y)

def is_connected(min1, max1, min2, max2):
    return (min1 <= min2 <= max1 
        or min1 <= max2 <= max1
        or min2 <= min1 <= max2
        or min2 <= max1 <= max2
        or min2-max1 == 1
        or min1-max2 == 1)

def is_rect_connected(rgA, rgB):
    return is_connected(rgA[0], rgA[1], rgB[0], rgB[1]) or \
        is_connected(rgA[2], rgA[3], rgB[2], rgB[3])
# - BFS
def bfs(startP, rg):
    q = deque()
    visited = [[False]*n for _ in range(m)]
    q.append(startP)
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    while q:
        u, v = q.popleft()
        if u < 0 or u >= m or v < 0 or v >= n:
            continue
        if visited[u][v]:
            continue
        visited[u][v] = True
        if mat[u][v]:
            continue
        update_range(rg, u, v)
        for i in range(4):
            q.append((u+dx[i], v+dy[i]))
rgS = [start[0], start[0], start[1], start[1]]
rgE = [end[0], end[0], end[1], end[1]]
res = False
if is_rect_connected(rgS, rgE):
    res = True
if not res:
    bfs(start, rgS)
    res |= is_rect_connected(rgS, rgE)
if not res:
    bfs(end, rgE)
    res |= is_rect_connected(rgS, rgE)
print("YES" if res else "NO")