# 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 = set()
while closer or detour:
if not closer:
f += dh
closer, detour = detour, closer
b = closer.pop()
if b in lookup:
continue
lookup.add(b)
if b == t:
return f
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 nb not in lookup):
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 = set()
while dq:
b, d = dq.popleft()
if b in lookup:
continue
lookup.add(b)
if b == t:
return d
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 nb not in lookup):
continue
if nd == grid[b[0]][b[1]]:
dq.appendleft((nb, d))
else:
dq.append((nb, d+1))
return -1 # never reach here
IyBUaW1lOiAgTyhtICogbikKIyBTcGFjZTogTyhtICogbikKCiMgQSogU2VhcmNoIEFsZ29yaXRobSB3aXRob3V0IGhlYXAKY2xhc3MgU29sdXRpb24ob2JqZWN0KToKICAgIGRlZiBtaW5Db3N0KHNlbGYsIGdyaWQpOgogICAgICAgICIiIgogICAgICAgIDp0eXBlIGdyaWQ6IExpc3RbTGlzdFtpbnRdXQogICAgICAgIDpydHlwZTogaW50CiAgICAgICAgIiIiCiAgICAgICAgZGlyZWN0aW9ucyA9IFsoMCwgMSksICgwLCAtMSksICgxLCAwKSwgKC0xLCAwKV0KICAgICAgICBkZWYgYV9zdGFyKGdyaWQsIGIsIHQpOgogICAgICAgICAgICBmLCBkaCA9IDAsIDEKICAgICAgICAgICAgY2xvc2VyLCBkZXRvdXIgPSBbYl0sIFtdCiAgICAgICAgICAgIGxvb2t1cCA9IHNldCgpCiAgICAgICAgICAgIHdoaWxlIGNsb3NlciBvciBkZXRvdXI6CiAgICAgICAgICAgICAgICBpZiBub3QgY2xvc2VyOgogICAgICAgICAgICAgICAgICAgIGYgKz0gZGgKICAgICAgICAgICAgICAgICAgICBjbG9zZXIsIGRldG91ciA9IGRldG91ciwgY2xvc2VyCiAgICAgICAgICAgICAgICBiID0gY2xvc2VyLnBvcCgpCiAgICAgICAgICAgICAgICBpZiBiIGluIGxvb2t1cDoKICAgICAgICAgICAgICAgICAgICBjb250aW51ZQogICAgICAgICAgICAgICAgbG9va3VwLmFkZChiKQogICAgICAgICAgICAgICAgaWYgYiA9PSB0OgogICAgICAgICAgICAgICAgICAgIHJldHVybiBmCiAgICAgICAgICAgICAgICBmb3IgbmQsIChkciwgZGMpIGluIGVudW1lcmF0ZShkaXJlY3Rpb25zLCAxKToKICAgICAgICAgICAgICAgICAgICBuYiA9IChiWzBdK2RyLCBiWzFdK2RjKQogICAgICAgICAgICAgICAgICAgIGlmIG5vdCAoMCA8PSBuYlswXSA8IGxlbihncmlkKSBhbmQgMCA8PSBuYlsxXSA8IGxlbihncmlkWzBdKSBhbmQgbmIgbm90IGluIGxvb2t1cCk6CiAgICAgICAgICAgICAgICAgICAgICAgIGNvbnRpbnVlCiAgICAgICAgICAgICAgICAgICAgKGNsb3NlciBpZiBuZCA9PSBncmlkW2JbMF1dW2JbMV1dIGVsc2UgZGV0b3VyKS5hcHBlbmQobmIpCiAgICAgICAgICAgIHJldHVybiAtMQoKICAgICAgICByZXR1cm4gYV9zdGFyKGdyaWQsICgwLCAwKSwgKGxlbihncmlkKS0xLCBsZW4oZ3JpZFswXSktMSkpCgoKIyBUaW1lOiAgTyhtICogbikKIyBTcGFjZTogTyhtICogbikKaW1wb3J0IGNvbGxlY3Rpb25zCgoKIyAgMC0xIGJmcyBzb2x1dGlvbgpjbGFzcyBTb2x1dGlvbjIob2JqZWN0KToKICAgIGRlZiBtaW5Db3N0KHNlbGYsIGdyaWQpOgogICAgICAgICIiIgogICAgICAgIDp0eXBlIGdyaWQ6IExpc3RbTGlzdFtpbnRdXQogICAgICAgIDpydHlwZTogaW50CiAgICAgICAgIiIiCiAgICAgICAgZGlyZWN0aW9ucyA9IFsoMCwgMSksICgwLCAtMSksICgxLCAwKSwgKC0xLCAwKV0KICAgICAgICBiLCB0ID0gKDAsIDApLCAobGVuKGdyaWQpLTEsIGxlbihncmlkWzBdKS0xKQogICAgICAgIGRxID0gY29sbGVjdGlvbnMuZGVxdWUoWyhiLCAwKV0pCiAgICAgICAgbG9va3VwID0gc2V0KCkKICAgICAgICB3aGlsZSBkcToKICAgICAgICAgICAgYiwgZCA9IGRxLnBvcGxlZnQoKQogICAgICAgICAgICBpZiBiIGluIGxvb2t1cDoKICAgICAgICAgICAgICAgIGNvbnRpbnVlCiAgICAgICAgICAgIGxvb2t1cC5hZGQoYikKICAgICAgICAgICAgaWYgYiA9PSB0OgogICAgICAgICAgICAgICAgcmV0dXJuIGQKICAgICAgICAgICAgZm9yIG5kLCAoZHIsIGRjKSBpbiBlbnVtZXJhdGUoZGlyZWN0aW9ucywgMSk6CiAgICAgICAgICAgICAgICBuYiA9IChiWzBdK2RyLCBiWzFdK2RjKQogICAgICAgICAgICAgICAgaWYgbm90ICgwIDw9IG5iWzBdIDwgbGVuKGdyaWQpIGFuZCAwIDw9IG5iWzFdIDwgbGVuKGdyaWRbMF0pIGFuZCBuYiBub3QgaW4gbG9va3VwKToKICAgICAgICAgICAgICAgICAgICBjb250aW51ZQogICAgICAgICAgICAgICAgaWYgbmQgPT0gZ3JpZFtiWzBdXVtiWzFdXToKICAgICAgICAgICAgICAgICAgICBkcS5hcHBlbmRsZWZ0KChuYiwgZCkpCiAgICAgICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgICAgIGRxLmFwcGVuZCgobmIsIGQrMSkpCiAgICAgICAgcmV0dXJuIC0xICAjIG5ldmVyIHJlYWNoIGhlcmU=