print("Ola Mundo!")

Ola Mundo!

• Apresentação = demonstrar o "algoritmo funcionando"
• Compactar os arquivos e enviar até 5/12
• Desenvolver um algoritmos de busca que ajude um determinado agente a encontrar a saida de um labirinto

Regras:
1) O aluno escolhe o Labirinto e classifica como fácil, médio ou difícil
2) Mostra da tela os passos e a quantidade de passos dados para encontrar a saída;
3) "Ensinar" qual seria o melhor caminho para a saída

Enviar por e-mail para: dcicillini@yahoo.com.br

Aulas de Sábado:

• 19/10 26/10
• 09/11 23/11 30/11
• 07/12 14/12

import numpy
from matplotlib import pyplot as plt

labirinto = numpy.array(
[[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
[1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
[1,0,1,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,1,0,1,0,1,0,0,0,1,1,0,0,1,1,1,0,1],
[1,0,1,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,1,0,1,0,0,1,0,0,1,0,0,0,1,0,1],
[1,0,1,0,1,0,0,1,1,1,0,0,0,0,0,0,0,0,0,1,1,1,0,1,0,1,0,1,0,1,0,1,1,0,0,1,1,0,0,1,0,1],
[1,0,1,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,0,1,0,0,1,0,1],
[1,0,1,0,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,1,0,1,0,0,1,0,1],
[1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,0,0,0,1,0,0,1,0,1],
[1,0,1,0,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,0,0,0,1,0,0,1,0,1],
[1,0,1,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,1],
[1,0,1,0,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,1],
[1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,1,1,1,1,1,0,0,1,0,1],
[1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,1,0,1,0,0,0,0,1,0,0,1,0,1],
[1,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,1,0,0,1,0,1],
[1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,1,0,1,1,1,1,1,1,0,0,1,0,1],
[1,0,1,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,1,1,0,0,0,0,1,0,1],
[1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,1,0,1,0,0,1,1,0,0,0,1,0,1],
[1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,1,0,1,0,0,0,1,1,0,0,1,0,1],
[1,0,1,0,1,0,1,0,1,0,1,1,0,1,1,1,0,1,1,1,0,1,1,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1],
[1,0,1,0,1,0,1,0,1,0,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1],
[1,0,1,0,1,0,1,0,1,0,0,1,1,1,1,1,0,1,1,1,1,1,0,0,0,1,0,0,0,1,0,0,1,1,1,0,0,1,0,1,0,1],
[1,0,1,0,1,0,1,0,1,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1],
[1,0,1,0,1,0,1,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1],
[1,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1],
[1,0,1,0,1,0,1,0,0,1,0,0,1,1,1,0,0,0,1,1,1,0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1],
[1,0,1,0,1,0,1,0,0,1,0,1,1,0,1,0,0,0,1,0,1,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1],
[1,0,1,0,1,0,1,0,0,0,0,1,0,0,1,1,1,1,1,0,0,1,0,0,0,1,0,0,0,1,0,0,1,1,1,0,0,1,0,1,0,1],
[1,0,1,0,1,0,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,1,0,1],
[1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,0,0,1,1,1,1,1,1,1,1,1,0,1,1,1],
[1,0,1,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[1,0,1,0,1,0,1,0,1,0,1,1,1,1,1,0,0,0,0,0,0,1,0,1,0,1,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1],
[1,0,1,0,1,0,1,0,1,0,0,0,0,0,1,1,1,1,1,1,1,1,0,1,1,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1],
[1,0,1,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1],
[1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1],
[1,0,1,0,1,0,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,1],
[1,0,1,0,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,1,1,0,0,0,0,1],
[1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1],
[1,1,1,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
[1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,1,1,1],
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]]
    
)

print(labirinto)

[[1 1 1 ... 1 1 1]
 [1 0 0 ... 0 0 1]
 [1 0 1 ... 1 1 1]
 ...
 [1 1 1 ... 0 0 1]
 [1 1 1 ... 1 1 1]
 [1 1 1 ... 1 1 1]]

fig, ax = plt.subplots()
fig.set_size_inches(18.5, 10.5)
im = ax.imshow(labirinto)
plt.show()

def locPortas(labirinto):
  alt, larg = labirinto.shape
  i = 0
  while(i<alt):
    if(labirinto[i,0]==0):
      ini = [i,0]
    if(labirinto[i,alt-1]==0):
      fim = [i,alt]
    i += 1
  return ini, fim
  

#labirinto = get_primeiro_labirinto()
#print(locPortas(labirinto))

#Gerador de labirintos aleatório
#Baseado neste código: http://code.activestate.com/recipes/578356-random-maze-generator/

import random
import numpy as np
from matplotlib import pyplot


def salva_maze(maze,nm):
    nome = "out/"+nm
    fig0, ax0 = pyplot.subplots(nrows=1, ncols=1)
    ax0.imshow(maze).set_cmap("gray")
    ax0.get_xaxis().set_ticks([])
    ax0.get_yaxis().set_ticks([])
    pyplot.savefig(nome+".jpg", bbox="none")
    pyplot.close(fig0)

    
def get_labirinto():
  mx = 41; my = 41 # tamanho do labirinto
  maze = [[0 for x in range(mx)] for y in range(my)]
  pixels = maze
  dx = [0, 1, 0, -1]; dy = [-1, 0, 1, 0] # 4 para mover-se no labirinto
  color = [0, 1] # valores adicionados ao labirinto
  #inicial de uma célula aleatória
  cx = random.randint(0, mx - 1); cy = random.randint(0, my - 1)
  maze[cy][cx] = 1; stack = [(cx, cy, 0)] # empilhar elementos: (x, y, direction)

  while len(stack) > 0:
      (cx, cy, cd) = stack[-1]
      # prevenir zigzag pro labirinto ficar mais bonito
      if len(stack) > 2:
          if cd != stack[-2][2]: dirRange = [cd]
          else: dirRange = range(4)
      else: dirRange = range(4)

      # achar nova clelula pra adicionar
      nlst = [] # lista de vizinhança disponível
      for i in dirRange:
          nx = cx + dx[i]; ny = cy + dy[i]
          if nx >= 0 and nx < mx and ny >= 0 and ny < my:
              if maze[ny][nx] == 0:
                  ctr = 0 # vizinhos ocupados deve ser 1
                  for j in range(4):
                      ex = nx + dx[j]; ey = ny + dy[j]
                      if ex >= 0 and ex < mx and ey >= 0 and ey < my:
                          if maze[ey][ex] == 1: ctr += 1
                  if ctr == 1: nlst.append(i)

      # sem tem mais de um vizinho disponível seleciona aleatoriamente
      if len(nlst) > 0:
          ir = nlst[random.randint(0, len(nlst) - 1)]
          cx += dx[ir]; cy += dy[ir]; maze[cy][cx] = 1
          stack.append((cx, cy, ir))
      else: stack.pop()


  #Insere as portas
  def criaportas(maze):
    posl = 1; posc = 0;

    #entrada
    fim = False
    while(not fim):
      if(maze[(posc+1),posl] == 0):
        maze[posl,posc] = 0
        fim = True
      else:
        posl +=1

    #saída
    posl = maze.shape[0] - 1
    posc = maze.shape[0] - 1
    fim = False
    while(not fim):
      if(maze[(posc-1),posl] == 0):
        maze[posl,posc] = 0
        fim = True
      else:
        posl -=1


    return maze  




  cont = 0
  maze = np.array(maze)
  
  #Inverte os valores do labirinto 
  for x in range(maze.shape[0]):
    for y in range(maze.shape[1]):
      if (maze[x,y] == 1):
        maze[x,y] = 0
      else:
        maze[x,y] = 1

  maze = np.pad(maze,1,'constant', constant_values=(1))
  maze = criaportas(maze)
  return maze

Aê seus arrombado, se liga nisso:

import numpy
from matplotlib import pyplot as plt

#Definindo uma função pra retoprnar aquele primeiro labirinto
def get_primeiro_labirinto():

    labirinto = numpy.array(
    [[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
    [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
    [0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,0,1,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,1,0,1,0,1,0,0,0,1,1,0,0,1,1,1,0,1],
    [1,0,1,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,1,0,1,0,0,1,0,0,1,0,0,0,1,0,1],
    [1,0,1,0,1,0,0,1,1,1,0,0,0,0,0,0,0,0,0,1,1,1,0,1,0,1,0,1,0,1,0,1,1,0,0,1,1,0,0,1,0,1],
    [1,0,1,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,0,1,0,0,1,0,1],
    [1,0,1,0,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,1,0,1,0,0,1,0,1],
    [1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,0,0,0,1,0,0,1,0,1],
    [1,0,1,0,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,0,0,0,1,0,0,1,0,1],
    [1,0,1,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,1],
    [1,0,1,0,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,1],
    [1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,1,1,1,1,1,0,0,1,0,1],
    [1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,1,0,1,0,0,0,0,1,0,0,1,0,1],
    [1,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,1,0,0,1,0,1],
    [1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,1,0,1,1,1,1,1,1,0,0,1,0,1],
    [1,0,1,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,1,1,0,0,0,0,1,0,1],
    [1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,1,0,1,0,0,1,1,0,0,0,1,0,1],
    [1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,1,0,1,0,0,0,1,1,0,0,1,0,1],
    [1,0,1,0,1,0,1,0,1,0,1,1,0,1,1,1,0,1,1,1,0,1,1,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1],
    [1,0,1,0,1,0,1,0,1,0,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1],
    [1,0,1,0,1,0,1,0,1,0,0,1,1,1,1,1,0,1,1,1,1,1,0,0,0,1,0,0,0,1,0,0,1,1,1,0,0,1,0,1,0,1],
    [1,0,1,0,1,0,1,0,1,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1],
    [1,0,1,0,1,0,1,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1],
    [1,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1],
    [1,0,1,0,1,0,1,0,0,1,0,0,1,1,1,0,0,0,1,1,1,0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1],
    [1,0,1,0,1,0,1,0,0,1,0,1,1,0,1,0,0,0,1,0,1,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1],
    [1,0,1,0,1,0,1,0,0,0,0,1,0,0,1,1,1,1,1,0,0,1,0,0,0,1,0,0,0,1,0,0,1,1,1,0,0,1,0,1,0,1],
    [1,0,1,0,1,0,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,1,0,1],
    [1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,0,0,1,1,1,1,1,1,1,1,1,0,1,1,1],
    [1,0,1,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
    [1,0,1,0,1,0,1,0,1,0,1,1,1,1,1,0,0,0,0,0,0,1,0,1,0,1,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1],
    [1,0,1,0,1,0,1,0,1,0,0,0,0,0,1,1,1,1,1,1,1,1,0,1,1,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,0,1,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1],
    [1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1],
    [1,0,1,0,1,0,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,1],
    [1,0,1,0,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,1,1,0,0,0,0,1],
    [1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1],
    [1,1,1,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,1,1,1],
    [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]]

    )
    return labirinto
  

#definindo uma função pra localizar as portas
def locPortas(labirinto):
    alt, larg = labirinto.shape
    i = 0
    while(i<alt):
        if(labirinto[i,0]==0):
            ini = [i,0]
        if(labirinto[i,alt-1]==0):
            fim = [i,alt]
        i += 1
    return ini, fim
  

#Definindo o contexto, pra saber se estamos indo pro norte, pro sul, leste....
#Isso é necessário pra saber qual operação devemos fazer para virar à esquerda

def get_contexto(pos,nova_pos):
    #recebe duas posições da matriz (x e y, x2 e y2)
    #O dicionário foi ordenado seguindo a regra da mão esquerda
    contexto = {
        "norte" : {
            "esquerda" : (0,-1),
            "frente"   : (-1,0),
            "direita"  : (0,1),
            "retorno"  : (1,0)
        },
        "sul" : {
            "esquerda" : (0,1),
            "frente"   : (1,0),
            "direita"  : (0,-1),
            "retorno"  : (-1,0)
        },
        "oeste" : {
            "esquerda" : (1,0),
            "frente"   : (0,-1),
            "direita"  : (-1,0),
            "retorno"  : (0,1)
        },
        "leste" : {
            "esquerda" : (-1,0),
            "frente"   : (0,1),
            "direita"  : (1,0),
            "retorno"  : (0,-1)
        }
    }
    #verifica pra onde foi o passo
    if (nova_pos[0]<pos[0]):
        return contexto['norte']
    elif (nova_pos[0]>pos[0]):
        return contexto['sul']
    elif (nova_pos[1]<pos[1]):
        return contexto['oeste']
    elif (nova_pos[1]>pos[1]):
        return contexto['leste']
    else:
        return "Mesma Posição"
    
    

#Função para achar o caminho possível
def olha(labirinto,pos,contexto):
    '''
        Recebe Labirinto, a posição e o contexto
        percorre o contexto verificando se há caminho
        retorna uma tupla de direção assim que encontrar um caminho possível
    '''
    a,l = labirinto.shape
    for c in contexto:
        
        temp = [pos[0]+contexto[c][0],pos[1]+contexto[c][1]]
        if(temp[0] > (a-1)):
            temp[0] = (a-1)
        if(temp[1] > (l-1)):
            temp[1] = (l-1)
        if( (labirinto[temp[0],temp[1]]) == 0 ):
            return (contexto[c])
        
        
            

#Função para achar a nova posição a partir do passo
def anda(pos,passo):
    nova_pos = [pos[0]+passo[0],pos[1]+passo[1]]
    return nova_pos

#Função que vai resolver o labirinto
def maoEsquerda(labirinto):
    #cria uma lista para armazenar o caminho
    caminho = []
    #Encontra as portas do labirinto
    ini, fim = locPortas(labirinto)
    #salva o iníciona lista do caminho
    caminho.append(ini)
    #Define o primeiro passo
    primeiro_passo = [ini[0],ini[1]+1]
    #pega o contexto do primeiro passo
    contexto = get_contexto(ini,primeiro_passo)
    #posiciona no primeir passo
    pos = primeiro_passo[:]
    #salva o iníciona lista do caminho
    caminho.append(pos)
    while(pos!=fim):
        #define o proximo passo
        passo = olha(labirinto,pos,contexto)
        #define a nova posição
        nova_pos = anda(pos,passo)
        #pega o novo contexto
        contexto = get_contexto(pos,nova_pos)
        #posiciona o cursos na nova posição
        pos = nova_pos[:]
        #Adiciona nova posição à lista de caminho
        caminho.append(pos)
    #retira a última entrada da lista de caminhos pois ela extrapola o labirinto    
    caminho.pop(-1)
    #retorna o caminho percorrido
    return caminho

        
    
    

#

def classifica(caminho):
  tam = len(caminho)
  dif = ''
  if tam < 500:
    dif = 'Fácil'
  elif (tam > 500 and tam < 1000):
    dif = 'Médio'
  else:
    dif = 'Difícil'
  return dif

labirinto = get_primeiro_labirinto()
caminho = maoEsquerda(labirinto)

#Trocando os valores do caminho para podemor observar
for c in caminho:
    labirinto[c[0],c[1]] = -1
    
fig, ax = plt.subplots()
fig.set_size_inches(18.5, 10.5)
im = ax.imshow(labirinto)
plt.show()    
print(len(caminho))

184

#Medindo desempenho
from timeit import default_timer as timer

#labirinto = get_primeiro_labirinto()
labirinto = get_labirinto()
start = timer()
caminho = maoEsquerda(labirinto)
end = timer()
tempo_gasto = end - start

dificuldade = classifica(caminho)

print(f"Nível de Dificuldade: {dificuldade}")
print(f"resolvido com {len(caminho)} passos em {tempo_gasto} segundos")


#Altera valores do caminho percorrido para podermos visualizar
for c in caminho:
    labirinto[c[0],c[1]] = -1
    
#Plota o labirinto com o caminho realçado
fig, ax = plt.subplots()
fig.set_size_inches(18.5, 10.5)
im = ax.imshow(labirinto)
plt.show()    

Nível de Dificuldade: Fácil
resolvido com 469 passos em 0.003280600000000078 segundos

#labirinto = get_primeiro_labirinto()
labirinto = get_labirinto()
#print(labirinto)

def olha2(labirinto, pos):
  movimentos = {
            "n" : (-1,0),
            "s"   : (1,0),
            "l"  : (0,1),
            "o"  : (0,-1)
        }  
  #print(labirinto[pos[0],pos[1]])
  caminhos_possiveis = []
  a_lab, l_lab = labirinto.shape
  
  for m in movimentos:
    #print(movimentos[m][0])
    l = pos[0]+movimentos[m][0]
    c = pos[1]+movimentos[m][1]
    pos_testada = [l,c]
    if(l < a_lab and c < l_lab):
      if(labirinto[pos_testada[0],pos_testada[1]]==0):
        # print("por aqui senhorita")
        # print(m)
        caminhos_possiveis.append(pos_testada)
  return caminhos_possiveis
olha2(labirinto,[3,1])

[[2, 1], [4, 1]]

ini, fim = locPortas(labirinto)


def aestrela(labirinto, caminho, pos, ini, fim, todos_os_caminhos_levam_a_roma):
  #print("estrela21estrelaoutravetelefonedeondeeuvou#eterminou")
  '''
    A função será responsável por fazer a busca pelo labirinto, ela receberá o labirinto, o caminho percorrido até agora, a posição*(retirar) o final 
    e a lista de caminhos que ela manipulará.
    Existem três possibilidades:
      Entrar em um poço (possibilidades = 1)
      Estar em uma reta (possibilidades = 2)
      Estar em uma esquina (possibilidades > 2)

  '''
  #Adiciona posição atual para o caminho
  caminho.append(pos)
  
  #verifica se é o primeiro passo
  if(ini==pos):
    pos = [pos[0],pos[1]+1]
    aestrela(labirinto, caminho, pos, ini, fim, todos_os_caminhos_levam_a_roma)    
 
  #************************************************************************************************
  #Verifica se chegou no final do labirinto
  pre_fim = [fim[0],fim[1]-1]
  if(pos[0]==pre_fim[0] and pos[1]==pre_fim[1]):
    todos_os_caminhos_levam_a_roma.append(caminho)
    return todos_os_caminhos_levam_a_roma  
  #************************************************************************************************
  #se não chegou continua procurando
  else:
    possibilidades = olha2(labirinto,pos)
    #--------------------------------------------------------------------------------------------------------------------------
    #POÇO (possibilidades = 1)
    if (len(possibilidades) == 1):
      caminho.append([None,None])
      todos_os_caminhos_levam_a_roma.append(caminho)
      return todos_os_caminhos_levam_a_roma  
    
    #--------------------------------------------------------------------------------------------------------------------------
    #RETA (possibilidades = 2)
    elif (len(possibilidades) == 2):
      
      #ANDAR
      while(len(possibilidades) == 2):
        for p in possibilidades:
          if(p not in caminho):
            pos = p[:]
            caminho.append(pos)
            possibilidades = olha2(labirinto,pos)
      #Aqui as possibilidade não são mais = 2 então chama-se novamente para tomar uma nova decisão 
      aestrela(labirinto, caminho, pos, ini, fim, todos_os_caminhos_levam_a_roma)

    #--------------------------------------------------------------------------------------------------------------------------
    #ESQUINA (possibilidades > 2)
    else:
      #CHAMADA RECURSIVA
      for p in possibilidades:
        if(p not in caminho):
          #print(caminho)
          aestrela(labirinto, caminho, p, ini, fim, todos_os_caminhos_levam_a_roma)
      #Se não estiver caminha pra frente
      
  return todos_os_caminhos_levam_a_roma  

        
def verificaviaveis(lista_de_caminhos):
  caminhos_viaveis = []
  for c in lista_de_caminhos:
    if (c[-1] != [None,None]):
      print("certo")
      print(c)
      print("------------")
#     else:
#       print("errado")
#       print(c)
#       print("------------")
      


caminho = []
lista_de_caminhos = []
lista_de_caminhos = aestrela(labirinto, caminho, ini, ini, fim, lista_de_caminhos)
verificaviaveis(lista_de_caminhos)

# def move(labirinto, caminho):
#  
#  
#   ini, fim = locPortas(labirinto)


#   if(len(caminho)==0):
#     pos = ini[:]
#   else:
#     if(caminho[-1] == fim):
#       return caminho
#     pos = caminho[-1]
#     print(caminho[-1])
#   possibilidades = olha2(labirinto, pos)
#   for p in possibilidades:
#      novo_caminho = caminho[:]
#      novo_caminho.append(p)
#      move(labirinto, novo_caminho)

# c = []
# resultado = move(labirinto,c)
#print(resultado)

# class no:
#   def __init__(self, pai, pos):
#     self.pai = pai
#     self.pos = pos
  

# def achacaminho(no):
#   caminho = []
#   while(no.pai != None):
#     caminho.append(no.pos)
#     no = no.pai
#   return caminho





  




# raiz = no(None,[0,0])
# n1 = no(raiz,[0,1])
# n2 = no(raiz,[0,2])
# n3 = no(n1,[1,3])

# print(str(achacaminho(n3)))

  

_fig, ax = plt.subplots()
fig.set_size_inches(30, 30)
im = ax.imshow(labirinto)
plt.show()