“葡萄城杯”牛客周赛 Round 53 F 小红走矩阵

当年用python写的代码

193.18pts TLE 3/22 WA 2/22

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=70565258

from collections import deque

# 输入
y_, x_ = map(int, input().split())
maze = [list(input()) for _ in range(y_)]

# 各个方向都能走  不能走上       不能走下     不能走左      不能走右
qList = [(0, 0, 0, 4, 1), (0, 0, 0, 3, 1), (0, 0, 0, 2, 1), (0, 0, 0, 1, 1), (0, 0, 0, 0, 1)]  # x, y, d, 健全, 穿墙次数
direction5 = [[(-1, 0), (0, 1), (0, -1)], [(1, 0), (0, 1), (0, -1)], [(1, 0), (-1, 0), (0, 1)], 
              [(1, 0), (-1, 0), (0, -1)], [(1, 0), (-1, 0), (0, 1), (0, -1)]]

def bfs():
    visited = [[[False] * 2 for _ in range(x_)] for _ in range(y_)]
    q = deque(qList)
    while q:
        x0, y0, d, dI, throughAb = q.popleft()
        if visited[y0][x0][throughAb]:
            continue
        visited[y0][x0][throughAb] = True

        for dx, dy in direction5[dI]:
            nx, ny = x0 + dx, y0 + dy
            if 0 <= nx < x_ and 0 <= ny < y_:
                # 终点判断
                if nx == x_ - 1 and ny == y_ - 1:
                    if maze[ny][nx] == '.' or (maze[ny][nx] == 'X' and throughAb == 1):
                        return d + 1
                
                # 走路与穿墙判断
                if maze[ny][nx] == '.' and not visited[ny][nx][throughAb]:
                    q.append((nx, ny, d + 1, dI, throughAb))
                elif maze[ny][nx] == 'X' and throughAb == 1 and not visited[ny][nx][0]:
                    q.append((nx, ny, d + 1, dI, 0))
                
    return -1

print(bfs())