fork(3) download 
  1.  
  2. def vaiCavalo( origemX, origemY, destinoX, destinoY ):
  3.  
  4. 	# criamos uma matriz 8x8 preenchida com False
  5. 	# para anotar as casas ja testadas
  6. 	casasTestadas = [[False]*8 for i in range(8)]
  7.  
  8. 	# todos os movimentos possiveis do cavalo
  9. 	movimentos = [[-1,-2],[-2,-1],[-2,1],[-1,2],[1,2],[2,1],[2,-1],[1,-2]]
  10.  
  11. 	# o primeiro passo e a origem do cavalo
  12. 	# X, Y e caminho percorrido ate entao (vazio no comeco)
  13. 	passos = [[origemX, origemY,[]]]
  14.  
  15. 	while True:
  16. 		proximosPassos = []
  17. 		for passo in passos:
  18. 			print("Cavalo atualmente em [", passo[0], ",", passo[1], "], vindo de", passo[2])
  19.  
  20. 			# vamos testar todos os movimentos possiveis a partir deste passo
  21. 			for movimento in movimentos:
  22. 				x = passo[0]+movimento[0]
  23. 				y = passo[1]+movimento[1]
  24.  
  25. 				# armazenamos o caminho feito ate chegar aqui
  26. 				caminho = (list(passo[2]))
  27. 				caminho.append([passo[0],passo[1]])
  28.  
  29. 				# o cavalo chegou ao destino, retornamos o caminho completo
  30. 				if x == destinoX and y == destinoY:
  31. 					print("  PRONTO! Chegamos em [", x, y, "]")
  32. 					caminho.append([x,y])
  33. 					return caminho
  34.  
  35. 				# senao, armazenamos a posicao para a proxima rodada
  36. 				elif 0 <= x < 8 and 0 <= y < 8 and not casasTestadas[x][y]:
  37. 					print("  Destino nao encontrado em [", x, y, "], coordenadas na pilha")
  38. 					proximosPassos.append([x,y,caminho])
  39.  
  40. 					# vamos descartar novas tentativas partindo daqui
  41. 					casasTestadas[x][y] = True
  42.  
  43. 		# todos os passos realizados, vamos para os seguintes
  44. 		passos = proximosPassos
  45.  
  46. print("\nCaminho feito:", vaiCavalo(3, 2, 3, 3))
  47.  
Success #stdin #stdout 0.01s 9992KB
comments (?)
stdin 
Standard input is empty
stdout 
Cavalo atualmente em [ 3 , 2 ], vindo de []
  Destino nao encontrado em [ 2 0 ], coordenadas na pilha
  Destino nao encontrado em [ 1 1 ], coordenadas na pilha
  Destino nao encontrado em [ 1 3 ], coordenadas na pilha
  Destino nao encontrado em [ 2 4 ], coordenadas na pilha
  Destino nao encontrado em [ 4 4 ], coordenadas na pilha
  Destino nao encontrado em [ 5 3 ], coordenadas na pilha
  Destino nao encontrado em [ 5 1 ], coordenadas na pilha
  Destino nao encontrado em [ 4 0 ], coordenadas na pilha
Cavalo atualmente em [ 2 , 0 ], vindo de [[3, 2]]
  Destino nao encontrado em [ 0 1 ], coordenadas na pilha
  Destino nao encontrado em [ 1 2 ], coordenadas na pilha
  Destino nao encontrado em [ 3 2 ], coordenadas na pilha
  Destino nao encontrado em [ 4 1 ], coordenadas na pilha
Cavalo atualmente em [ 1 , 1 ], vindo de [[3, 2]]
  Destino nao encontrado em [ 0 3 ], coordenadas na pilha
  Destino nao encontrado em [ 2 3 ], coordenadas na pilha
  Destino nao encontrado em [ 3 0 ], coordenadas na pilha
Cavalo atualmente em [ 1 , 3 ], vindo de [[3, 2]]
  Destino nao encontrado em [ 0 5 ], coordenadas na pilha
  Destino nao encontrado em [ 2 5 ], coordenadas na pilha
  Destino nao encontrado em [ 3 4 ], coordenadas na pilha
  Destino nao encontrado em [ 2 1 ], coordenadas na pilha
Cavalo atualmente em [ 2 , 4 ], vindo de [[3, 2]]
  Destino nao encontrado em [ 1 6 ], coordenadas na pilha
  Destino nao encontrado em [ 3 6 ], coordenadas na pilha
  Destino nao encontrado em [ 4 5 ], coordenadas na pilha
  Destino nao encontrado em [ 4 3 ], coordenadas na pilha
Cavalo atualmente em [ 4 , 4 ], vindo de [[3, 2]]
  Destino nao encontrado em [ 5 6 ], coordenadas na pilha
  Destino nao encontrado em [ 6 5 ], coordenadas na pilha
  Destino nao encontrado em [ 6 3 ], coordenadas na pilha
  Destino nao encontrado em [ 5 2 ], coordenadas na pilha
Cavalo atualmente em [ 5 , 3 ], vindo de [[3, 2]]
  Destino nao encontrado em [ 7 4 ], coordenadas na pilha
  Destino nao encontrado em [ 7 2 ], coordenadas na pilha
  Destino nao encontrado em [ 6 1 ], coordenadas na pilha
Cavalo atualmente em [ 5 , 1 ], vindo de [[3, 2]]
  Destino nao encontrado em [ 7 0 ], coordenadas na pilha
Cavalo atualmente em [ 4 , 0 ], vindo de [[3, 2]]
Cavalo atualmente em [ 0 , 1 ], vindo de [[3, 2], [2, 0]]
  Destino nao encontrado em [ 2 2 ], coordenadas na pilha
Cavalo atualmente em [ 1 , 2 ], vindo de [[3, 2], [2, 0]]
  Destino nao encontrado em [ 0 0 ], coordenadas na pilha
  Destino nao encontrado em [ 0 4 ], coordenadas na pilha
  PRONTO! Chegamos em [ 3 3 ]

Caminho feito: [[3, 2], [2, 0], [1, 2], [3, 3]]
https://ideone.com/5c2SpA
language:
Python 3 (python  3.9.5)
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!