AcWing 1101. 献给阿尔吉侬的花束
原题链接
简单
作者:
喜欢日奈大可爱
,
2024-04-05 20:36:41
,
所有人可见
,
阅读 1
python3 bfs
t = int(input())
def bfs(start, end):
q = []
dist[start[0]][start[1]] = 0
q.append(start)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
while(len(q)):
t = q.pop(0)
if t == end:
return dist[t[0]][t[1]]
for i in range(4):
x = t[0] + dx[i]
y = t[1] + dy[i]
if (x < 0) or (x >= r) or (y < 0) or (y >= c):
continue # 出界
if g[x][y] == '#':
continue # 墙
if dist[x][y] != -1:
continue # 走过
dist[x][y] = dist[t[0]][t[1]] + 1
q.append((x, y))
return 'oop!'
for i in range(t):
r, c = map(int, input().split())
g = []
for i in range(r):
a = input()
g.append([i for i in a])
dist = [[-1 for i in range(c)] for j in range(r)]
for i in range(r):
for j in range(c):
if g[i][j] == 'S':
start = (i, j)
elif g[i][j] == 'E':
end = (i, j)
print(bfs(start, end))