associação pythonbrasil[11] django zope/plone planet Início Logado como (Entrar)

Revisão 2e 2005-04-12 14:08:02

Excluir mensagem

ResolvedorLabirinto

Este código utiliza recursão para resolver um labirinto.

O mapa deve ser dado em formato texto, vide exemplo no fim do código.

A versão mais atual encontra-se em: http://gsbarbieri.sytes.net/labirinto.py

   1 #!/usr/bin/env python
   2 # -*- coding: utf-8 -*-
   3 # -*- mode: python -*-
   4 
   5 
   6 # Configuração de caracteres do mapa
   7 parede     = '#'
   8 corredor   = '.'
   9 percorrido = '='
  10 errado     = 'x'
  11 solucao    = '@'
  12 entrada    = 'E'
  13 saida      = 'S'
  14 
  15 
  16 class Labirinto( object ):
  17     def __init__( self ):
  18         self.mapa    = None
  19         self.entrada = None
  20         self.saida   = None
  21     # __init__()
  22 
  23 
  24     def le_mapa( self, texto ):
  25         """Lê um mapa, este deve ter uma entrada e uma saída."""
  26         self.mapa = texto.split( '\n' )
  27 
  28         for i, l in enumerate( self.mapa ):
  29             # encontra entrada:
  30             p = l.find( entrada )
  31             if p >= 0:
  32                 self.entrada = ( i, p )
  33             # encontra saida:
  34             p = l.find( saida )
  35             if p >= 0:
  36                 self.saida = ( i, p )
  37 
  38             # converte string para lista
  39             self.mapa[ i ] = list( l )
  40 
  41         if not self.entrada:
  42             raise ValueError( "O mapa não possui uma entrada!" )
  43         if not self.saida:
  44             raise ValueError( "O mapa não possui uma saída!" )
  45     # le_mapa()
  46 
  47 
  48     def le_mapa_arquivo( self, arquivo ):
  49         """Lê um mapa de um arquivo"""
  50         f = open( arquivo )
  51         self.le_mapa( f.read() )
  52         f.close()
  53     # le_mapa_arquivo()
  54 
  55 
  56 
  57     def __str__( self ):
  58         m = []
  59         for l in self.mapa:
  60             m.append( ''.join( l ) )
  61         return '\n'.join( m )
  62     # __str__()
  63 
  64 
  65     def resolve( self ):
  66         """Resolve o labirinto, tenta encontrar a saída.
  67 
  68         Se a saída foi encontrada, retorna True, caso contrário False.
  69         """
  70         def posicao_valida( linha, coluna ):
  71             "Função utilizada para conferir se a posição está dentro do mapa"
  72             if linha > len( self.mapa ) or \
  73                    coluna > len( self.mapa[ linha ] ):
  74                 "Posição inválida, sai fora do mapa"
  75                 return False
  76             else:
  77                 return True
  78         # posicao_valida()
  79 
  80 
  81         def encontra_saida( linha, coluna ):
  82             """Função recursiva para encontrar a saída."""
  83 
  84             if self.mapa[ linha ][ coluna ] == saida:
  85                 "Caso base da recursão, estamos em cima da saída"
  86                 return True
  87             else:
  88                 """Marque como percorrido e entre em recursão
  89 
  90                 No caso iremos pela direita, depois para cima, para esquerda e
  91                 então para baixo.
  92 
  93                 Lembrando que isto é uma recursão e que marcamos nosso caminho,
  94                 temos magicamente a lembrança dos caminhos já testados.
  95                 """
  96                 self.mapa[ linha ][ coluna ] = percorrido
  97                 achou = False
  98 
  99                 if not achou and \
 100                        posicao_valida( linha, coluna + 1 ) and \
 101                        self.mapa[ linha ][ coluna + 1 ] in ( corredor, saida ):
 102                     """Ainda não encontrou e
 103                     a posição à direita é corredor ou é a saída.
 104                     Prossiga pela direita."""
 105                     achou = encontra_saida( linha, coluna + 1 )
 106 
 107                 if not achou and \
 108                        posicao_valida( linha - 1, coluna ) and \
 109                        self.mapa[ linha - 1 ][ coluna ] in ( corredor, saida ):
 110                     """Ainda não encontrou e
 111                     a posição acima é corredor ou é a saída.
 112                     Prossiga para cima."""
 113                     achou = encontra_saida( linha - 1, coluna )
 114 
 115                 if not achou and \
 116                        posicao_valida( linha, coluna - 1 ) and \
 117                        self.mapa[ linha ][ coluna - 1 ] in ( corredor, saida ):
 118                     """Ainda não encontrou e
 119                     a posição à esquerda é corredor ou é a saída.
 120                     Prossiga para esquerda."""
 121                     achou = encontra_saida( linha, coluna - 1 )
 122 
 123                 if not achou and \
 124                        posicao_valida( linha + 1, coluna ) and \
 125                        self.mapa[ linha + 1 ][ coluna ] in ( corredor, saida ):
 126                     """Ainda não encontrou e
 127                     a posição abaixo é corredor ou é a saída.
 128                     Prossiga para baixo."""
 129                     achou = encontra_saida( linha + 1, coluna )
 130 
 131                 # Caso o caminho adotado foi correto, marque como solução
 132                 # senão marque como errado
 133                 if achou:
 134                     self.mapa[ linha ][ coluna ] = solucao
 135                 else:
 136                     self.mapa[ linha ][ coluna ] = errado
 137                     
 138                 return achou
 139         # encontra_saida()
 140         
 141         return encontra_saida( self.entrada[ 0 ], self.entrada[ 1 ] )
 142     # resolve()
 143 # Labirinto
 144 
 145 
 146 # Exemplo de uso:
 147 l = Labirinto()
 148 l.le_mapa(
 149     """
 150 ############## ####################
 151 #E.#.S#..#...###.....#.#..........#
 152 #..#.............###.#............#
 153 ##...##...######## #...#..........# 
 154 ##############     ################
 155 """ )
 156 print l
 157 print "achou?",l.resolve()
 158 print l

Por GustavoBarbieri.