1101. 献给阿尔吉侬的花束
摘要
Title: 1101. 献给阿尔吉侬的花束
Tag: BFS
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
1101. 献给阿尔吉侬的花束
-
题意
见原题
-
思路
BFS即可
-
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38'''
Author: NEFU AB-IN
Date: 2022-03-28 21:23:05
FilePath: \ACM\Acwing\1101.py
LastEditTime: 2022-03-28 21:23:06
'''
from collections import deque
for _ in range(int(input())):
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
n, m = map(int, input().split())
st = [[0] * m for _ in range(n)]
g = []
for i in range(n):
g.append(list(input()))
for i in range(n):
for j in range(m):
if g[i][j] == 'S':
sx, sy = i, j
if g[i][j] == 'E':
ex, ey = i, j
q = deque()
q.appendleft([sx, sy, 0])
st[sx][sy] = 1
while q:
x, y, cnt = q.pop()
if x == ex and y == ey:
print(cnt)
break
for i in range(4):
x1 = x + dx[i]
y1 = y + dy[i]
if x1 >= 0 and x1 < n and y1 >= 0 and y1 < m and (
g[x1][y1] == '.' or g[x1][y1] == 'E') and st[x1][y1] == 0:
q.appendleft([x1, y1, cnt + 1])
st[x1][y1] = 1
if st[ex][ey] == 0:
print("oop!")