# Test case wrong?

• Either the test case is wrong or the distance algorithm description is poorly presented

Input:
[[1,1,1,1,1,0],
[0,0,0,0,0,1],
[0,1,1,0,0,1],
[1,0,0,1,0,1],
[1,0,1,0,0,1],
[1,0,0,0,0,1],
[0,1,1,1,1,0]]

Output:
72 (3, 2)
Expected:
88

``````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[0])):
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:
elif node in lands and node not in bfsLands:
q.append(node)
if len(bfsBuildings) == len(buildings):
for node in bfsLands:
curMin[0] = min(curMin[0], calDis(node[0], node[1], buildings))
visited |= bfsLands

for l in lands:
if l not in visited:
bfs([l], lands, buildings, obstacles, set([l]), set(), visited)

if curMin[0] == sys.maxint:
return -1
else:
return curMin[0]``````

• 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

• Thanks for the help of checking this test case by the way!

• 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.

• Thanks, I've just fixed the description by removing the manhattan distance and mentioning you can only go up, down, left and right.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.