Robot in a Grid

Modified from CCI.

Imagine a robot sitting on the upper left hand corner of a grid with r rows and c columns. The robot can move in four directions: right, left, down and up, but certain cells are “off limits” such that the robot cannot step on them. Design an algorithm to find a if a grid is traversible for the robot.

Solution

The recursive solution to this problem involves computing each possible path. If a path reaches the destination, we will append that path to the solution set. We can traverse the grid using the row and column indices. The base case will terminate the recursion for the following conditions:

• the cell is outside of the grid
• the cell is the destination
• the cell has not already been visited
• the cell has a value of 0

The traversal can move in four directions,

• (r-1, c)
• (r+1, c)
• (r, c-1)
• (r, c+1)

Notice that we are keeping track of the cells we have visited. This is another application of memoization - and it makes this solution more efficient. Since we cannot visit any cell more than once, the solution has a runtime of \(O(n)\) where \(n\) is the number of cells in the matrix.

def traverse(grid, r, c, visited=set()):
  if(r > grid.shape[0]-1) or (c > grid.shape[1]-1) or (r < 0) or (c < 0):
    return False
  elif((r,c) in visited):
    return False
  elif(grid[r][c] == 0):
    return False
  elif(r == grid.shape[0] - 1) and (c == grid.shape[1] - 1):
    return True

  visited.add((r,c))

  flag = False
  flag = flag or traverse(grid, r, c+1, visited)
  flag = flag or traverse(grid, r, c-1, visited)
  flag = flag or traverse(grid, r+1, c, visited)
  flag = flag or traverse(grid, r-1, c, visited)

  return flag