The Maze II

There is aballin a maze with empty spaces and walls. The ball can go through empty spaces by rollingup,down,leftorright, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction.

Given the ball'sstart position, thedestinationand themaze, find the shortest distance for the ball to stop at the destination. The distance is defined by the number ofempty spacestraveled by the ball from the start position (excluded) to the destination (included). If the ball cannot stop at the destination, return -1.

The maze is represented by a binary 2D array. 1 means the wall and 0 means the empty space. You may assume that the borders of the maze are all walls. The start and destination coordinates are represented by row and column indexes.

Example 1

Input 1:
 a maze represented by a 2D array

0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
1 1 0 1 1
0 0 0 0 0


Input 2:
 start coordinate (rowStart, colStart) = (0, 4)

Input 3:
 destination coordinate (rowDest, colDest) = (4, 4)

Output:
 12

Explanation:
 One shortest way is : left -> down -> left -> down -> right -> down -> right.
             The total distance is 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12.

Solution:

keep variable.

Hashmap of child to parent: key is child node, value is parent node. So we can trace back all the way to start coordinate

Hashmap of coordinates and steps to immediate parent: key is coordinate, value is a tuple of (step to immediate parent, cumulated steps all the way to start). Note cumulated step number may be dirty and we should trace from immediate parent for final return.

BFS approach to store all current level coordinates.

two bugs/errors made

1. storing only the total length of each coordinate's visit assume this visit won't be updated with a future visit of fewer steps. Because even when future step arrives here, it won't expand from such node anymore
2. updating by the steps to the immediate parent is erroneous because, this immediate step could be of length 1, but the chain of parent could add up to large number.

class Solution(object):
    def shortestDistance(self, maze, start, destination):
        """
        :type maze: List[List[int]]
        :type start: List[int]
        :type destination: List[int]
        :rtype: int
        """

        # same idea with the Maze I, but use a hashmap to store parent node, another map to store how much distance 
        # each step travels thru
        r,c = start
        frontier = [start]
        visited = {(r,c):(0,0)}
        parent = {(r,c): None}
        while frontier:
            nextF = []
            for [row, col] in frontier:
                moves = self.getNextMoves(maze, [row, col], visited, parent)
                nextF.extend(moves)

            frontier = nextF

        # because you want to find the shortest path, you have to exhaust all possible directions anyway
        row,col = destination
        if (row,col) in visited:
            steps = 0
            while [row,col] != start:
                steps += visited[(row,col)][0] # update the steps needed for current step
                (row,col) = parent[(row,col)]
            return steps
        return -1

    def getNextMoves(self, maze, start, visited, parent):
        res = []
        rowNum = len(maze)
        colNum = len(maze[0])
        r,c = start

        # roll up
        row,col = start
        steps = 0
        while row >= 0 and maze[row][col] != 1:
            steps += 1
            row -= 1
        self.updateVisited((row+1, col), visited, steps - 1, start, parent, res)

        # roll down
        row,col = start
        steps = 0
        while row < rowNum and maze[row][col] != 1:
            steps += 1
            row +=1
        self.updateVisited((row-1, col), visited, steps - 1, start, parent, res)

        # roll left
        row,col = start
        steps = 0
        while col >= 0 and maze[row][col] != 1:
            steps += 1
            col -= 1
        self.updateVisited((row, col +1), visited, steps - 1, start, parent, res)

        # roll right
        row,col = start
        steps = 0
        while col < colNum and maze[row][col] != 1:
            steps += 1
            col +=1
        self.updateVisited((row, col -1), visited, steps - 1, start, parent, res)

        return res

    def updateVisited(self, newPosition, visited, steps, start, parent, res):
        row, col = newPosition
        r, c = start
        if (row,col) not in visited:
            visited[(row,col)] = (steps, visited[(r,c)][1]+steps)
            parent[(row,col)] = (r,c)
            res.append([row,col])
        elif (row,col) != (r,c) and visited[r,c][1]+steps < visited[(row, col)][1]: 
            # if current processed coordinate is not the same as start
            visited[(row,col)] = (steps, visited[(r,c)][1]+steps) # update the parent and visited steps
            parent[(row,col)] = (r,c)