fork download
copy 
  1. from collections import deque
  2.  
  3.  
  4. graph = [[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
  5. 		 [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
  6. 		 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  7. 		 [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
  8. 		 [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
  9. 		 [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
  10. 		 [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
  11. 		 [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
  12. 		 [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
  13. 		 [0, 0, 0, 0, 1, 0, 0, 0, 0, 0]]
  14.  
  15. # To move left, right, up and down
  16. delta_x = [-1, 1, 0, 0]
  17. delta_y = [0, 0, 1, -1]
  18.  
  19. def valid(x, y):
  20. 	if x < 0 or x >= len(graph) or y < 0 or y >= len(graph[x]):
  21. 		return False
  22. 	return (graph[x][y] != 1)
  23.  
  24. def solve(start, end):
  25. 	Q = deque([start])
  26. 	dist = {start: 0}
  27. 	while len(Q):
  28. 		curPoint = Q.popleft()
  29. 		curDist = dist[curPoint]
  30. 		if curPoint == end:
  31. 			return curDist
  32. 		for dx, dy in zip(delta_x, delta_y):
  33. 			nextPoint = (curPoint[0] + dx, curPoint[1] + dy)
  34. 			if not valid(nextPoint[0], nextPoint[1]) or nextPoint in dist.keys():
  35. 				continue
  36. 			dist[nextPoint] = curDist + 1
  37. 			Q.append(nextPoint)
  38.  
  39. print(solve((0,0), (6,7)))
  40.  
Success #stdin #stdout 0.02s 27712KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
13
https://ideone.com/tuBu3G
language:
Python 3 (python  3.12)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!