题目描述:
给定一个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) 回帖