Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #!/usr/bin/python
- def sumTuple(a, b):
- return tuple([sum(x) for x in zip(a, b)])
- def dfs( r, c, pacman_r, pacman_c, food_r, food_c, grid):
- pacman = (pacman_r, pacman_c)
- food = (food_r, food_c)
- stack = [([pacman], pacman)]
- visited = []
- explored = []
- while len(stack) > 0:
- path, current = stack.pop()
- if current in explored:
- continue
- explored.append(current)
- if current == food:
- return explored, path
- for next_move in [(-1,0),(0,-1), (0, 1),(1, 0)]:
- next_block = sumTuple(current, next_move)
- if next_block in visited or grid[next_block[0]][next_block[1]] == "%":
- continue
- visited.append(next_block)
- new_path = list(path)
- new_path.append(next_block)
- stack.append((new_path, next_block))
- pacman_r, pacman_c = [ int(i) for i in raw_input().strip().split() ]
- food_r, food_c = [ int(i) for i in raw_input().strip().split() ]
- r,c = [ int(i) for i in raw_input().strip().split() ]
- grid = []
- for i in xrange(0, r):
- grid.append(raw_input().strip())
- explored, result = dfs(r, c, pacman_r, pacman_c, food_r, food_c, grid)
- print len(explored)
- for x in explored:
- print "%d %d" % x
- print len(result)-1
- for x in result:
- print "%d %d" % x
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement