python - 优化算法以找到到所有建筑物的最短距离

Question

问题是找到给定网格的 0 值点到所有建筑物的最短距离。您只能向上、向下、向左和向右移动。您可能会遇到以下值:

0 - 空白空间1 - 建筑2 - 障碍

我用 Python 编写的解决方案如下:

import sys

class Solution(object):
    def shortestDistance(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if grid is None:
            return -1

        tup = self.findPoints(grid)
        buildings = tup[0]
        zeroPoints = tup[1]
        distances = []
        for points in zeroPoints:
            dist = self.bfs(grid, points, buildings)
            distances += [dist]

        return self.select(distances)

    def findPoints(self, grid):
        buildings = 0
        zeroPoints = []
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 0:
                    zeroPoints += [[i,j]]
                elif grid[i][j] == 1:
                    buildings += 1
        return (buildings, zeroPoints)

    def bfs(self, grid, root, targets):
        hits, sumDist = 0, 0
        targetsFound = []

        while hits < targets:
            q = []
            q.append((root, 0))
            found = False
            visited = []
            while(len(q) > 0):
                tup = q.pop(0)
                curr = tup[0]
                dist = tup[1]

                if grid[curr[0]][curr[1]] == 1 and curr not in targetsFound:
                    found = True
                    sumDist += dist
                    targetsFound += [curr]
                    break

                if grid[curr[0]][curr[1]] == 0:
                    if (curr[0] - 1) >= 0 and grid[curr[0] -1][curr[1]] != 2 and [curr[0] - 1, curr[1]] not in visited:
                        q.append(([curr[0] - 1, curr[1]], dist + 1))
                        visited += [[curr[0] - 1, curr[1]]]
                    if (curr[0] + 1) < len(grid) and grid[curr[0] + 1][curr[1]] != 2 and [curr[0] + 1, curr[1]] not in visited:
                        q.append(([curr[0] + 1, curr[1]], dist + 1))
                        visited += [[curr[0] + 1, curr[1]]]
                    if (curr[1] - 1) >= 0 and grid[curr[0]][curr[1] - 1] != 2 and [curr[0], curr[1] - 1] not in visited:
                        q.append(([curr[0], curr[1] - 1], dist + 1))
                        visited += [[curr[0], curr[1] - 1]]
                    if (curr[1] + 1) < len(grid[0]) and grid[curr[0]][curr[1] + 1] != 2 and [curr[0], curr[1] + 1] not in visited:
                        q.append(([curr[0], curr[1] + 1], dist +1))
                        visited += [[curr[0], curr[1] + 1]]

            if found:
                hits += 1
            else:
                return - 1

        return sumDist

    def select(self, distances):
        min = sys.maxsize
        for dist in distances:
            if dist < min and dist != -1:
                min = dist

        if min == sys.maxsize:
            return -1
        else:
            return min

我的问题是:

如何提高解决方案的效率？现在我在以下输入上超过了 Leetcode 的时间限制，但它对所有其他测试输入都是正确的:

[[2,0,0,2,0,0,0,0,0,2,2,0,0,0,0,0,0,0,0,0,1,2,0,2,0,1,1,0],[0,1,0,1,1,2,0,0,2,0,0,2,0,2,2,0,2,0,2,0,0,0,0,0,0,0,0,0],[1,0,0,1,2,0,0,2,0,2,0,0,0,0,0,0,0,0,0,2,0,2,0,0,0,0,0,2],[0,0,2,2,2,1,0,0,2,0,0,0,0,0,0,0,0,0,2,2,2,2,1,0,0,0,0,0],[0,2,0,2,2,2,2,1,0,0,0,0,1,0,2,0,0,0,0,2,2,0,0,0,0,2,2,1],[0,0,2,1,2,0,2,0,0,0,2,2,0,2,0,2,2,2,2,2,0,0,0,0,2,0,2,0],[0,0,0,2,1,2,0,0,2,2,2,1,0,0,0,2,0,2,0,0,0,0,2,2,0,0,1,1],[0,0,0,2,2,0,0,2,2,0,0,0,2,0,2,2,0,0,0,2,2,0,0,0,0,2,0,0],[2,0,2,0,0,0,2,0,2,2,0,2,0,0,2,0,0,2,1,0,0,0,2,2,0,0,0,0],[0,0,0,0,0,2,0,2,2,2,0,0,0,0,0,0,2,1,0,2,0,0,2,2,0,0,2,2]]

注意:更改 visited 和 targetsFound 可以提高效率，但不足以通过所有测试用例。

更新:

通过更改算法以从每个建筑物而不是每个零点开始搜索，我能够在某些大输入上将算法改进 96% 并通过所有测试用例。更新后的算法如下。感谢 Nether 的建议。

def shortestDistanceWalk(grid):

    onePoints = findPointsWalk(grid)

    for point in onePoints:
        bfsWalk(grid, point)

    shortestDistance = sys.maxsize
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] < 0 and shortestDistance > (grid[i][j] * -1):
                shortestDistance = (grid[i][j] * -1)

    if shortestDistance == sys.maxsize:
        return -1
    else:
        return shortestDistance

def findPointsWalk(grid):
    onePoints = []
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == 1:
                onePoints += [[i,j]]
    return onePoints

def bfsWalk(grid, root):
    q = []
    q.append((root, 0))
    found = False
    visited = set()
    while(len(q) > 0):
        tup = q.pop(0)
        curr = tup[0]
        dist = tup[1]

        if grid[curr[0]][curr[1]] <= 0:
            grid[curr[0]][curr[1]] += dist

        if (curr[0] - 1) >= 0 and grid[curr[0] -1][curr[1]] <= 0  and (curr[0] - 1, curr[1]) not in visited:
            q.append(([curr[0] - 1, curr[1]], dist - 1))
            visited.add((curr[0] - 1, curr[1]))
        if (curr[0] + 1) < len(grid) and grid[curr[0] + 1][curr[1]] <= 0 and (curr[0] + 1, curr[1]) not in visited:
            q.append(([curr[0] + 1, curr[1]], dist - 1))
            visited.add((curr[0] + 1, curr[1]))
        if (curr[1] - 1) >= 0 and grid[curr[0]][curr[1] - 1] <= 0 and (curr[0], curr[1] - 1) not in visited:
            q.append(([curr[0], curr[1] - 1], dist - 1))
            visited.add((curr[0], curr[1] - 1))
        if (curr[1] + 1) < len(grid[0]) and grid[curr[0]][curr[1] + 1] <= 0 and (curr[0], curr[1] + 1) not in visited:
            q.append(([curr[0], curr[1] + 1], dist - 1))
            visited.add((curr[0], curr[1] + 1))

    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if (i, j) not in visited:
                grid[i][j] = 3

    return

Answer 1

将您的 targetsFound 变量更改为 set .您使用该变量的原因是查找单元格是否已被访问并且列表中的查找时间很慢 O(N)。集合支持快速查找 O(1)，因此应该可以显着提高算法的性能。

有关 O(N) 和 O(1) 含义的更多信息:https://www.youtube.com/watch?v=v4cd1O4zkGw&t=1s