关注
def bfs(grid, begin, end):
'''
bfs方法能求得最短路径
:param grid:
:param begin:
:param end:
:return:
'''
n= len(grid)
seen = []
dx = [1, 0, -1, 0] # 四个方位
dy = [0, 1, 0, -1]
level = []
level.append(begin)
seen.append(begin)
step = 0
while level:
queue = []
step += 1
for q in level:
for i in range(4):
nx, ny = q[0] + dx[i], q[1] + dy[i]
if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] != '#':
if [nx, ny ] in end:
return step
if [nx, ny] not in queue and [nx, ny] not in seen:
queue.append([nx, ny])
seen.append([nx, ny])
level = queue
print(level)
return -1
if __name__ == '__main__':
n = int(input())
grid = [['' for _ in range(n)] for _ in range(n)]
g3 = []
begin = []
end = []
# 复制9块迷宫 从中间那块迷宫的起点'S'出发,直到到达任意9块迷宫中的'E'
for i in range(n):
s = input()
g3.append(s*3)
grid[i] = list(s)
if 'S' in s:
begin.append(i+n)
begin.append(s.index('S')+n)
if 'E' in s:
for x in range(0,2*n+1,n):
for y in range(0,2*n+1,n):
end.append([i + x,s.index('E') + y])
maze = []
for i in range(3):
for j in range(len(g3)):
maze.append(g3[j])
print(bfs(maze, begin, end)) 考试完后想到的一种思路: 1、将复制9块迷宫图组装在一起 2、从中间迷宫图的起点到达任意迷宫图的终点即为到达终点,步进方式用bfs
查看原帖
点赞 评论
相关推荐
牛客热帖
正在热议
# 牛客帮帮团来啦!有问必答 #
726473次浏览 11686人参与
# 海康威视求职进展汇总 #
91271次浏览 1091人参与
# 浅聊一下我实习的辛苦费 #
81426次浏览 761人参与
# 非技术岗是怎么找实习的 #
74518次浏览 1392人参与
# 如何写一份好简历 #
262526次浏览 3962人参与
# 硬件人求职现状 #
184586次浏览 2705人参与
# 通信硬件人笔面经互助 #
111192次浏览 2234人参与
# 机械制造面试记录 #
37555次浏览 505人参与
# 24届营销人拿到了几个offer #
4222次浏览 62人参与
# 铜五铁六真的存在吗? #
28173次浏览 298人参与
# 打工人的辛酸 #
8586次浏览 134人参与
# 实习生应该准时下班吗 #
76639次浏览 569人参与
# 美的求职进展汇总 #
38838次浏览 417人参与
# 产品实习,你更倾向大公司or小公司 #
36357次浏览 556人参与
# 数据人offer决赛圈怎么选 #
44728次浏览 727人参与
# 实习与准备秋招该如何平衡 #
171541次浏览 3105人参与
# 投了多少份简历才上岸 #
57342次浏览 951人参与
# 通信硬件薪资爆料 #
200107次浏览 1813人参与
# 面试中的破防瞬间 #
83355次浏览 1029人参与
# 找工作,你会甘心进小厂还是猛冲大厂 #
35568次浏览 355人参与