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.