Robot in a Grid (dynamic programming, puzzle 8.2 from "Cracking the coding interview")

robot_in_a_grid.py

from collections import deque

def check_path(grid, i=0, j=0, failed_points=None, current_path=None):
    """ Find a route between upper-left and lower right corner of the grid,
    if you are only allowed to walk right and down.
    
    Input:
    1 1 1
    0 0 1
    0 0 1
    
    Output: [(0,0), (0,1), (0,2), (1, 2), (2, 2)]
    
    Input:
    1 1 1
    0 0 1
    0 0 0
    
    Output: None
    
    Algo #1: we try every incremental step. If we face dead end, we mark point as failed. 
    If we face finish, we return path we traversed on our way there.
    
    ! It's not a clean solution (i.e. reversed path is returned, missing first point, etc.), rework!
    
    
    Parameters
    ----------
    grid: array
        array, where each element tells whether it blocked or not
    
    Returns
    -------
    path: list
        a path containing coordinates of the grid or None if there is no path.
    
    """
    
    if failed_points is None:
        failed_points = set()
    
    if current_path is None:
        current_path = deque([])
    
    if grid[i][j]==0:
        return None
        
    r = len(grid)
    c = len(grid[0])
    
    if i==r-1 and j==c-1:
        current_path.appendleft((i, j))
        return current_path
        
    else:
        if ((i+1)<r) and ((i+1, j) not in failed_points) :
            if check_path(grid, i+1, j, failed_points, current_path) is not None:
                current_path.appendleft((i, j))
                return current_path
        if ((j+1)<c) and ((i, j+1) not in failed_points) :
            if check_path(grid, i, j+1, failed_points, current_path) is not None:
                current_path.appendleft((i, j))
                return current_path
                
    failed_points.add((i, j))
    
    return None

#DEMO.

grid=[[1, 1, 1], 
      [0, 0, 1],
      [0, 0, 1]]
print("path: %s" % check_path(grid))

grid=[[1, 1, 1], 
      [0, 0, 1],
      [0, 0, 0]]
print("path: %s" % check_path(grid))

grid=[[1]]
print("path: %s" % check_path(grid))

grid=[[0]]
print("path: %s" % check_path(grid))

grid=[[1, 1, 1, 1], 
      [1, 1, 1, 1],
      [1, 1, 1, 1],
      [1, 1, 1, 1]]
print("path: %s" % check_path(grid))


grid=[[1, 0, 0, 1], 
      [1, 0, 1, 1],
      [1, 1, 0, 1],
      [0, 1, 1, 1]]
print("path: %s" % check_path(grid))