fork download
  1. # Time: O(m * n)
  2. # Space: O(m * n)
  3.  
  4. # A* Search Algorithm without heap
  5. class Solution(object):
  6. def minCost(self, grid):
  7. """
  8. :type grid: List[List[int]]
  9. :rtype: int
  10. """
  11. directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
  12. def a_star(grid, b, t):
  13. f, dh = 0, 1
  14. closer, detour = [b], []
  15. lookup = set()
  16. while closer or detour:
  17. if not closer:
  18. f += dh
  19. closer, detour = detour, closer
  20. b = closer.pop()
  21. if b in lookup:
  22. continue
  23. lookup.add(b)
  24. if b == t:
  25. return f
  26. for nd, (dr, dc) in enumerate(directions, 1):
  27. nb = (b[0]+dr, b[1]+dc)
  28. if not (0 <= nb[0] < len(grid) and 0 <= nb[1] < len(grid[0]) and nb not in lookup):
  29. continue
  30. (closer if nd == grid[b[0]][b[1]] else detour).append(nb)
  31. return -1
  32.  
  33. return a_star(grid, (0, 0), (len(grid)-1, len(grid[0])-1))
  34.  
  35.  
  36. # Time: O(m * n)
  37. # Space: O(m * n)
  38. import collections
  39.  
  40.  
  41. # 0-1 bfs solution
  42. class Solution2(object):
  43. def minCost(self, grid):
  44. """
  45. :type grid: List[List[int]]
  46. :rtype: int
  47. """
  48. directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
  49. b, t = (0, 0), (len(grid)-1, len(grid[0])-1)
  50. dq = collections.deque([(b, 0)])
  51. lookup = set()
  52. while dq:
  53. b, d = dq.popleft()
  54. if b in lookup:
  55. continue
  56. lookup.add(b)
  57. if b == t:
  58. return d
  59. for nd, (dr, dc) in enumerate(directions, 1):
  60. nb = (b[0]+dr, b[1]+dc)
  61. if not (0 <= nb[0] < len(grid) and 0 <= nb[1] < len(grid[0]) and nb not in lookup):
  62. continue
  63. if nd == grid[b[0]][b[1]]:
  64. dq.appendleft((nb, d))
  65. else:
  66. dq.append((nb, d+1))
  67. return -1 # never reach here
Success #stdin #stdout 0.01s 7508KB
stdin
Standard input is empty
stdout
Standard output is empty