python
move = [[0, 1], [1, 0], [-1, 0], [0, -1]] # 方向数组,只朝四个方向移动
def bfs(start,end,g):
queue=[start] # 先将初始状态存到队列
dist=[[-1] *len(g[0]) for _ in range(len(g))] # 初始化距离数组为负一
dist[start[0]][start[1]]=0 # 起点的距离为零
# 开始BFS框架
while queue: # 先判断队列是否非空
x,y=queue.pop(0) # 取队头赋值给x,y
for i in range(4): # 朝四个方向各移动一次试试
a,b=x+move[i][0],y+move[i][1]
# 判断是否需要跳过
if a<0 or a>=len(g) or b<0 or b>=len(g[0]):
continue # 出界,跳过
if dist[a][b]!=-1:
continue # 已经访问过,跳过
if g[a][b]=='#':
continue # 碰到障碍物,跳过
dist[a][b]=dist[x][y]+1 # 记录一下距离
if [a,b]==end:
return dist[a][b] # 到达终点,返回距离
queue.append([a,b]) # 将新节点添加到队列中
return -1 # 无法到达终点,返回负一
t=int(input())
while t:
n,m=map(int,input().split())
start,end=0,0
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':
start=[i,j]
if g[i][j]=='E':
end=[i,j]
distance=bfs(start,end,g)
if distance==-1:
print('oop!')
else:
print(distance)
t-=1
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla