Advertisement
Guest User

Untitled

a guest
Feb 11th, 2016
114
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.29 KB | None | 0 0
  1. #!/usr/bin/python
  2. def sumTuple(a, b):
  3. return tuple([sum(x) for x in zip(a, b)])
  4.  
  5. def dfs( r, c, pacman_r, pacman_c, food_r, food_c, grid):
  6. pacman = (pacman_r, pacman_c)
  7. food = (food_r, food_c)
  8. stack = [([pacman], pacman)]
  9. visited = []
  10. explored = []
  11. while len(stack) > 0:
  12. path, current = stack.pop()
  13. if current in explored:
  14. continue
  15. explored.append(current)
  16. if current == food:
  17. return explored, path
  18.  
  19. for next_move in [(-1,0),(0,-1), (0, 1),(1, 0)]:
  20. next_block = sumTuple(current, next_move)
  21. if next_block in visited or grid[next_block[0]][next_block[1]] == "%":
  22. continue
  23. visited.append(next_block)
  24. new_path = list(path)
  25. new_path.append(next_block)
  26. stack.append((new_path, next_block))
  27.  
  28. pacman_r, pacman_c = [ int(i) for i in raw_input().strip().split() ]
  29. food_r, food_c = [ int(i) for i in raw_input().strip().split() ]
  30. r,c = [ int(i) for i in raw_input().strip().split() ]
  31.  
  32. grid = []
  33. for i in xrange(0, r):
  34. grid.append(raw_input().strip())
  35.  
  36. explored, result = dfs(r, c, pacman_r, pacman_c, food_r, food_c, grid)
  37.  
  38. print len(explored)
  39. for x in explored:
  40. print "%d %d" % x
  41. print len(result)-1
  42. for x in result:
  43. print "%d %d" % x
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement