“葡萄城杯”牛客周赛 Round 53 F 小红走矩阵 · znzryb
当年用python写的代码
193.18pts TLE 3/22 WA 2/22
[https://ac.nowcoder.com/acm/contest/view-submission?submissionId=70565258](https://ac.nowcoder.com/acm/contest/view-submission?submissionId=70565258)
```python
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())
```