すべての建物との最短距離を求める最適化アルゴリズム

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]] 

注：変更訪れ、targetsFoundは、効率を上げますが、すべてのテストケースに合格するのに十分ではありません。

更新：

各建物の代わりに、それぞれゼロ点から検索するためのアルゴリズムを変更することにより、私は、特定の大入力に96％によって、アルゴリズムを改善し、すべてのテストケースを通過することができました。更新されたアルゴリズムは以下の通りです。彼の提案に対するネザーランドのおかげです。

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

setにご targetsFound変数を変更

。 その変数を使用する理由は、セルが訪問されてリストの検索が遅い場合にルックアップすることです。O（N）時間です。セットは高速ルックアップO（1）をサポートしているため、アルゴリズムのパフォーマンスが大幅に向上するはずです。

（1）どのようなO（N）とOの詳細については、意味：助けたが、まだすべてのテストケースに合格するのに十分ではありませんhttps://www.youtube.com/watch?v=v4cd1O4zkGw&t=1s