minimum-cost-to-make-at-least-one-valid-path-in-a-grid.py

# Time:  O(m * n)
# Space: O(m * n)

# A* Search Algorithm without heap
class Solution(object):
    def minCost(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        def a_star(grid, b, t):
            f, dh = 0, 1
            closer, detour = [b], []
            lookup = [[False]*len(grid[0]) for _ in xrange(len(grid))]
            while closer or detour:
                if not closer:
                    f += dh
                    closer, detour = detour, closer
                b = closer.pop()
                if b == t:
                    return f
                if lookup[b[0]][b[1]]:
                    continue
                lookup[b[0]][b[1]] = True
                for nd, (dr, dc) in enumerate(directions, 1):
                    nb = (b[0]+dr, b[1]+dc)
                    if not (0 <= nb[0] < len(grid) and 0 <= nb[1] < len(grid[0]) and not lookup[nb[0]][nb[1]]):
                        continue
                    (closer if nd == grid[b[0]][b[1]] else detour).append(nb)
            return -1

        return a_star(grid, (0, 0), (len(grid)-1, len(grid[0])-1))


# Time:  O(m * n)
# Space: O(m * n)
import collections


#  0-1 bfs solution
class Solution2(object):
    def minCost(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        b, t = (0, 0), (len(grid)-1, len(grid[0])-1)
        dq = collections.deque([(b, 0)])
        lookup = [[False]*len(grid[0]) for _ in xrange(len(grid))]
        while dq:
            b, d = dq.popleft()
            if b == t:
                return d
            if lookup[b[0]][b[1]]:
                    continue
            lookup[b[0]][b[1]] = True
            for nd, (dr, dc) in enumerate(directions, 1):
                nb = (b[0]+dr, b[1]+dc)
                if not (0 <= nb[0] < len(grid) and 0 <= nb[1] < len(grid[0]) and not lookup[nb[0]][nb[1]]):
                    continue
                if nd == grid[b[0]][b[1]]:
                    dq.appendleft((nb, d))
                else:
                    dq.append((nb, d+1))
        return -1  # never reach here