grid_value.py

# https://classroom.udacity.com/courses/cs373/lessons/48646841/concepts/487174190923
# populate the value of grid starting from the goal.
# ----------
# User Instructions:
# 
# Create a function compute_value which returns
# a grid of values. The value of a cell is the minimum
# number of moves required to get from the cell to the goal. 
#
# If a cell is a wall or it is impossible to reach the goal from a cell,
# assign that cell a value of 99.
# ----------

grid = [[0, 1, 0, 0, 0, 0],
        [0, 1, 0, 0, 0, 0],
        [0, 1, 0, 0, 0, 0],
        [0, 1, 0, 0, 0, 0],
        [0, 0, 0, 0, 1, 0]]
goal = [len(grid)-1, len(grid[0])-1]
cost = 1 # the cost associated with moving from a cell to an adjacent one

delta = [[-1, 0 ], # go up
         [ 0, -1], # go left
         [ 1, 0 ], # go down
         [ 0, 1 ]] # go right

delta_name = ['^', '<', 'v', '>']

def compute_value(grid,goal,cost):
    # ----------------------------------------
    # insert code below
    # ----------------------------------------
    
    value = [[99 for col in range(len(grid[0]))] for row in range(len(grid))]
    visited = [[99 if grid[row][col] else 0 for col in range(len(grid[0]))] for row in range(len(grid))]
    cx,cy = goal
    value[cx][cy] = 0
    g = 0
    opened = []

    done = False
    while not done :
        
        for d in delta:
            dx,dy = d
            new_x = cx+dx
            new_y = cy+dy
            # within range
            if (0 <= new_x <= goal[0]) and (0 <= new_y <= goal[1]) :
                # not goal
                if (new_x!=goal[0]) or (new_y !=goal[1]):
                    # not visited 
                    if visited[new_x][new_y] == 0 :
                        opened.append([g+1, new_x, new_y])
                        value[new_x][new_y] = g+1
                        visited[new_x][new_y] = 1
                    
        #print opened       
        if len(opened) == 0 :
            done = True
        
        # select block with shorted cost
        else:
            opened.sort()
            opened.reverse()
            nxt = opened.pop()
            
            g,cx,cy = nxt
        
        # if cnt > 18:
        #     break
    # make sure your function returns a grid of values as 
    # demonstrated in the previous video.
    return value 

print compute_value(grid,goal,cost)