走迷宫

[编程题]走迷宫

热度指数：3994 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

NowCoder最喜欢游乐场的迷宫游戏，他和小伙伴们比赛谁先走出迷宫。
现在把迷宫的地图给你，你能帮他算出最快走出迷宫需要多少步吗？

输入描述:

输入包含多组数据。

每组数据包含一个10*10，由“#”和“.”组成的迷宫。其中“#”代表墙；“.”代表通路。

入口在第一行第二列；出口在最后一行第九列。

从任意一个“.”点都能一步走到上下左右四个方向的“.”点。

输出描述:

对应每组数据，输出从入口到出口最短需要几步。

示例1

输入

#.########
#........#
#........#
#........#
#........#
#........#
#........#
#........#
#........#
########.#
#.########
#........#
########.#
#........#
#.########
#........#
########.#
#........#
#.######.#
########.#

输出

16
30

算法知识视频讲解

Python

萌大仙

import sys
inp=''
for l in sys.stdin:
inp+=l.replace('\n', '')
manylines=[]

lines = []
count=0

for i in range(0,len(inp)+1,10):
    if count==10:
        manylines.append(lines)
        lines=[]
        count=0
    line = list(inp[i:i + 10])
    lines.append(line)
    count+=1

graphs=[]
for lines in manylines:
    graph={}
    for i in range(len(lines)):
        for j in range(len(lines[i])):
            graph[str(i)+str(j)]=[]
            if lines[i][j]=='#':
                continue
            if j>0:
                if lines[i][j-1] =='.': graph[str(i)+str(j)].append(str(i)+str(j-1))
            if j+1<len(lines[i]):
                if lines[i][j+1] == '.': graph[str(i) + str(j)].append(str(i) + str(j + 1))
            if i > 0:
                if lines[i-1][j] == '.': graph[str(i) + str(j)].append(str(i-1) + str(j))
            if i+1<len(lines):
                if lines[i+1][j] == '.': graph[str(i) + str(j)].append(str(i+1) + str(j))
    graphs.append(graph)

def BFS(graph,start,end):
    queue=[]
    queue.append(start)
    seen=set()
    seen.add(start)
    parent={start:None}
    while len(queue)>0:
        vertex=queue.pop(0)
        nodes=graph[vertex]
        for w in nodes:
            if w not in seen:
                queue.append(w)
                seen.add(w)
                parent[w]=vertex
    rall=[]
    while end!=None:
        rall.append(end)
        end=parent[end]
    return rall
for g in graphs:
    # print(g)
    lj=BFS(g,'01','98')
    print(len(lj)-1)

发表于 2022-04-06 09:43:37 回复(0)

Python

顾浩然

from collections import deque
def f(maze):
    start = [0,1,0]
    end = [9,8]
    directions = [[1,0],[0,1],[-1,0],[0,-1]]
    queue = deque()
    visit = [[True]*len(maze[0]) for i in range(len(maze))]
    queue.append(start)
    visit[start[0]][start[1]] = False
    while len(queue) > 0:
        cur = queue.popleft()
        if cur[0] == end[0] and cur[1] == end[1]:
            return cur[2]
        for i in range(4):
            x = cur[0] + directions[i][0]
            y = cur[1] + directions[i][1]
            if x >=0 and x < len(maze) and y >= 0 and y < len(maze[0]) and maze[x][y] == '.' and visit[x][y]:
                queue.append([x,y,cur[2]+1])
                visit[x][y] = False
#解决输出为空的问题！
while True:
    try:
        maze = []
        for i in range(10):
            tmp = raw_input()
            maze.append(tmp)
        print f(maze)
    except:
        break

发表于 2017-08-30 23:17:29 回复(0)