A interview question attempt: Shortest Cell Path

shortestCellPath.py

def shortestCellPath(grid, sr, sc, tr, tc):
    """
    @param grid: int[][]
    @param sr: int
    @param sc: int
    @param tr: int
    @param tc: int
    @return: int
    """

    queue = []
    queue.append([sc, sr, 0])
    # try all directions in grid (t,r,b,l)
    while len(queue) > 0:
        x, y, l = queue.pop()
        if x == tc and y == tr:
            return l

        if is_valid(grid, x, y - 1):  # up
            queue.append([x, y - 1, l + 1])

        if is_valid(grid, x + 1, y):  # right
            queue.append([x + 1, y, l + 1])

        if is_valid(grid, x, y + 1):  # down
            queue.append([x, y + 1, l + 1])

        if is_valid(grid, x - 1, y):  # left
            queue.append([x - 1, y, l + 1])

    return -1  # impossible
  
# O(V + E) V = vertexes, E = edges => O(V)
# count of 1's
# edges = vertexes * 4 = O(V)


def is_valid(grid, x, y):
    num_cols = len(grid[0])
    num_rows = len(grid)
    if x < 0 or x >= num_cols or y < 0 or y >= num_rows:
        return False

    if grid[y][x] != 1:
        return False

    grid[y][x] = 0
    return True
  
def main():
    print(shortestCellPath([[1, 1, 1, 1], [1, 0, 0, 1], [1, 0, 1, 1]], 0, 0, 2, 0)
  
main()