首页 > 网易互娱笔试走迷宫
头像
722525411
编辑于 2020-09-05 17:55
+ 关注

网易互娱笔试走迷宫

题目描述:
给定一个move函数,move(0/1/2/3)分别表示上下左右走,如果成功到达返回1,否则返回-1,给定一串函数的调用序列且最后序列最后停在出口,问知道这些信息后最短路要多少步?

输入:
T:测试样例数
n:函数调用次数
接下来是一串调用move函数的序列,且最后一定能走到出口

输出:
最短路步数

输入样例:

3
10
0 1
0 -1
1 1
1 1
1 -1
0 1
2 1
2 -1
3 1
3 1
2
3 1
3 1
8
0 1
0 1
3 1
3 1
1 1
1 1
2 1
0 1

输出样例:

1
2
2

请问这样写有什么问题吗:
首先模拟函数调用保存地图,然后再用BFS,样例过了提交0%

def bfs(maze):
    dirs=[(-1,0),(1,0),(0,-1),(0,1)]
    queue=[(len(maze)//2, len(maze)//2)]
    visited=set()
    visited.add(queue[0])
    step=0
    while queue:
        tmp=[]
        for x,y in queue:
            if maze[x][y]==2:
                return step
            for dx,dy in dirs:
                x_,y_=x+dx,y+dy
                if 0<=x_<len(maze) and 0<=y_<len(maze[0]) and maze[x_][y_]==1 or maze[x_][y_]==2 and (x_,y_) not in visited:
                    tmp.append((x_,y_))
                    visited.add((x_,y_))
        queue=tmp
        step+=1

dirs=[(-1,0),(1,0),(0,-1),(0,1)]
T=int(input())
ret=[]
for i in range(T):
    n=int(input())
    # -1不能走,0起点,1能走,2出口
    maze=[[-1 for i in range(10)] for j in range(10)]
    x=y=len(maze)//2
    maze[x][y]=0
    for j in range(n):
        op=list(map(int,input().split()))
        if op[1]==-1:
            continue
        if op[1]==1:
            dx,dy=dirs[op[0]]
            x,y=x+dx,y+dy
            if maze[x][y] != 0:
                maze[x][y]=1
            if j==n-1:
                maze[x][y]=2
    step=bfs(maze)
    ret.append(step)
[print(r) for r in ret]

全部评论

(1) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐