#! /usr/bin/python3
# Last edited on 2018-06-07 22:03:50 by stolfilocal

import random

def testa_cursor():
  print("\033[2J", end="") # Limpa a tela e vai para "home".
  print("\033[H", end="")  # Vai para "home".
  for i in range(10):
    for j in range(10):
      print(j, end="")
    print("")
  print("\033[H", end="")  # Vai para "home".
  print("***")
  print("\033[5;7H", end="")  # Vai para linha 5 coluna 7.
  print("@@@")
  print("\033[11;1H", end="")  # Vai para linha 11 coluna 1.
  for i in range(16):
    for j in range(16):
      print("[%s] " % chr(16*i + j), end="")
    print("")
  
def mostra_labirinto(L):
  print("\033[H", end="") # Move o cursor para o canto superior da tela.
  nlin = len(L)
  ncol = len(L[0])
  for i in range(nlin):
    for j in range(ncol):
      print(L[i][j], end="")
    print("") # Muda de linha.
    
def gera_labirinto(nlin, ncol, semente):
  """Devolve (L,i0,j0,i1,j1) onde {L} eh
  um labirinto aleatorio com tamanho {nlin,ncol},
  {L[i0][j0]} eh a entrada, e {L[i1][j1]} eh a saida.""" 
  
  assert nlin >= 3 and ncol >= 3  # Senao nao consegue.
  
  random.seed(semente)  # "Embaralha" o gerador {random}.
  L = [ None ] * nlin;  # Cria a lista de linhas.
  Lant = None
  for i in range(nlin):
    L[i] = [ None ] * ncol
    preenche_linha_labirinto(L, i)
    Lant = L[i]
  # Entrada e saida:
  imed = nlin//2
  L[imed][0] = " "
  L[imed][ncol-1] = " "
  return (L, imed,0, imed,ncol-1)
      
def preenche_linha_labirinto(L, i):
  """Preenche a linha {i} de um labirinto de
  tamanho {nlin x ncol}m levando em conta a linha
  anterior (se houver), suposta ja preenchida."""
  
  nlin = len(L)
  ncol = len(L[0])
  for j in range(ncol):
    # Get the three neighbors {a,b} above and the 
    # neighbor {c} to the left:
    if i <= 0:
      a = "?"; b = "?";
    else:
      b = L[i-1][j]
      if j <= 0:
        a = "?"; c = "?"
      else:
        a = L[i-1][j-1]; c = L[i][j-1]
    # Choose {L[i][j] = e} so as to avoid bad patterns.
    # See if it can be room:
    room_ok = True
    if a == " " and b == "@" and c == "@": room_ok = False
    if a == " " and b == " " and c == " ": room_ok = False
    # See if it can be wall:
    wall_ok = True
    if a == "@" and b == " " and c == " ": wall_ok = False
    if a == "@" and b == "@" and c == "@": wall_ok = False
    assert room_ok or wall_ok
    if not room_ok:
      e = "@"
    elif not wall_ok:
      e = " "
    else:
      if random.random() < 0.75:
        e = " "
      else:
        e = "@"
    L[i][j] = e

def encontra_caminho(L, i,j, i1, j1):
  """Tenta encontrar um caminho no labirinto {L} de
  {L[i][j]} para a porta de saida {L[i1][j1]}. 
  Supoe que as casas ja percorridas, desde a porta 
  de entrada ate logo antes da casa {i,j}, estao
  marcadas com "*".  Supoe que as casas jah visitadas
  sem sucesso estao marcadas com ".".
  
  Se existir o caminho acima, preenche o mesmo com "*"
  e devolve {True}.
  
  Se nao existir o caminho acima, devolve {False},
  deixando o tabuleiro como estava no momento da chamada,
  a menos de casas marcadas "."."""
  
  nlin = len(L)
  ncol = len(L[0])
  if i < 0 or i >= nlin or j < 0 or j >= ncol \
  or L[i][j] == "@" or L[i][j] == "*" or L[i][j] == ".":
    return False
  elif i == i1 and j == j1:
    L[i][j] = "*"; mostra_labirinto(L)
    return True
  else:
    # Estamos numa casa livre mas nao eh a porta de saida.
    # Marca esta casa como percorrida:
    L[i][j] = "*"; mostra_labirinto(L)
    # Tenta as casas vizinhas:
    r = random.randrange(4)
    for k in range(4):
      kr = (k + r) % 4
      di = (00, 00, -1, +1)[kr]
      dj = (-1, +1, 00, 00)[kr]
      if encontra_caminho(L, i+di,j+dj, i1, j1):
        # O caminho ja esta marcado.
        return True
    # Nenhuma das casas vizinhas deu certo.
    # Apaga a marca de caminho:
    L[i][j] = "."; mostra_labirinto(L)
    return False 

# testa_cursor()

print("\033[2J", end="") # Limpa a tela e vai para "home".
nlin = 15
ncol = 40
(L,i0,j0,i1,j1) = gera_labirinto(nlin,ncol,4615)
mostra_labirinto(L)
encontra_caminho(L,i0,j0,i1,j1)
for i in range(nlin):
  for j in range(ncol):
    if L[i][j] == ".":
      L[i][j] = " "
mostra_labirinto(L)