Test case wrong?


  • 2
    L

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

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

  • 0
    L

    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


  • 0
    L

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


  • 0

    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.


  • 0

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


Log in to reply
 

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