Either the test case is wrong or the distance algorithm description is poorly presented
72 (3, 2)
class Solution(object): def shortestDistance(self, grid): """ :type grid: List[List[int]] :rtype: int """ q =  lands, buildings, obstacles, visited = set(), set(), set(), set() curMin = [sys.maxint] for i in xrange(len(grid)): for j in xrange(len(grid)): if grid[i][j] == 0: lands.add((i, j)) if grid[i][j] == 1: buildings.add((i, j)) if grid[i][j] == 2: obstacles.add((i, j)) def calDis(i, j, buildings): res = 0 for x, y in buildings: res += abs(x - i) + abs(y - j) return res def bfs(q, lands, buildings, obstacles, bfsLands, bfsBuildings, visited): while len(q) > 0: i, j = q.pop(0) surroundings = [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)] for node in surroundings: if node in buildings and node not in bfsBuildings: bfsBuildings.add(node) elif node in lands and node not in bfsLands: bfsLands.add(node) q.append(node) if len(bfsBuildings) == len(buildings): for node in bfsLands: curMin = min(curMin, calDis(node, node, buildings)) visited |= bfsLands for l in lands: if l not in visited: bfs([l], lands, buildings, obstacles, set([l]), set(), visited) if curMin == sys.maxint: return -1 else: return curMin
I don't understand how you get 72. Can you tell where exactly you build the house and the distances to the other buildings?
A B C D E . . . . . . F . R S . . G Q . . T . H P . U . . I O . . . . J . N M L K .
I built the house on (3, 2), under S, on the left of T, on the top of U
Sum of Manhattan distances from (3, 2) to A - U is 72
That's not 72 then, not even close. The distance to A alone already is 15. Because you cannot pass through buildings.
But you're right, it shouldn't say Manhattan distances like that.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.