问答

当前位置

求助: Knight Shortest Path 超时

  • Ta: 胡助教

我的code在lintcode里超时,帮我看看怎么减小time complexity吧,谢谢!

def shortestPath(self, grid, source, destination):
    if not source or not destination:
        return -1
    if not grid or not grid[0]:
        return -1
    if source == destination:
        return 0
    queue = [[source.x, source.y]]
    count = 0
    visited = [[source.x, source.y]]
    while queue:
        temp = []
        count += 1
        for t in queue:
            for i, j in ((1,2), (1,-2), (-1,2), (-1,-2), (2,1), (2,-1), (-2,1), (-2,-1)):
                new_x = t[0] + i
                new_y = t[1] + j

                if self.notValid(new_x, new_y, visited, grid):
                    continue
                if new_x == destination.x and new_y == destination.y:
                    return count
                visited.append([new_x, new_y])
                if grid[new_x][new_y] == 0:
                    temp.append([new_x, new_y])
        queue = temp

    return -1

def notValid(self, new_x, new_y, visited, grid):
    if new_x < 0 or new_x >= len(grid):
        return True
    if new_y < 0 or new_y >= len(grid[0]):
        return True  
    if [new_x, new_y] in visited:
        return True
    return False

1 个回复

2019-09-17 carry

建议你这个可以去九章的solution里找到这道题的题解,然后看看题解的思路,建议看第二份的BFS代码,那份的题解和你思路cha'bu'd

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1