3
\$\begingroup\$

I was given this problem in a mock interview. I would appreciate a review of my implementation.


Shortest Cell Path In a given grid of 0s and 1s, we have some starting row and column sr, sc and a target row and column tr, tc. Return the length of the shortest path from sr, sc to tr, tc that walks along 1 values only.

Each location in the path, including the start and the end, must be a 1. Each subsequent location in the path must be 4-directionally adjacent to the previous location.

It is guaranteed that grid[sr][sc] = grid[tr][tc] = 1, and the starting and target positions are different.

If the task is impossible, return -1.

Examples:

input: grid = [[1, 1, 1, 1], [0, 0, 0, 1], [1, 1, 1, 1]] sr = 0, sc = 0, tr = 2, tc = 0 output: 8 (The lines below represent this grid:) 1111 0001 1111

grid = [[1, 1, 1, 1], [0, 0, 0, 1], [1, 0, 1, 1]] sr = 0, sc = 0, tr = 2, tc = 0 output: -1 (The lines below represent this grid:) 1111 0001 1011


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

  return -1 if len(path_lengths) == 0 else min(path_lengths)

def shortestCellPathHelper(grid, r, c, tr, tc, path_len, path_lengths):
  if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]):
    return

  if grid[r][c] != 1:
    return

  if r == tr and c == tc:
    path_lengths.append(path_len)
    return

  grid[r][c] = -1

  #4 directions
  shortestCellPathHelper(grid, r, c - 1, tr, tc, path_len + 1, path_lengths)
  shortestCellPathHelper(grid, r, c + 1, tr, tc, path_len + 1, path_lengths)
  shortestCellPathHelper(grid, r - 1, c, tr, tc, path_len + 1, path_lengths)
  shortestCellPathHelper(grid, r + 1, c, tr, tc, path_len + 1, path_lengths)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.