Labirinto Perfeito 20x10
- Autor:
- Marco A. Manetta
Um labirinto perfeito é aquele que se pode ir de qualquer ponto a qualquer outro ponto por um caminho único.
Entendendo o algoritmo utilizado
O algoritmo de busca em profundidade frequentemente segue as etapas abaixo:
Numa malha quadriculada, cada quadrícula será chamada de célula. Uma matriz do tamanho do quadriculado é preenchida inicialmente com zeros, indicando células não visitadas.
Cria-se uma lista de células que, inicialmente, está vazia.
- Escolhe-se aleatoriamente uma célula inicial, tornando-a a célula corrente e marca-se como célula visitada, fazendo o elemento correspondente na matriz igual a 1.
- Enquanto existirem células não visitadas, procede-se da seguinte maneira:
- Se a célula corrente tem alguma célula vizinha que ainda não foi visitada (0 na matriz):
- Escolhe-se aleatoriamente uma das células vizinhas não visitadas
- Insere-se a célula corrente no final da lista de células
- Remove-se a parede entre a célula corrente e a célula escolhida
- Faz-se a célula escolhida ser a célula corrente e marque-a como visitada (1 na matriz)
- Se todas as células vizinhas foram visitadas:
- Remove-se a última célula da lista de células
- Faz-se dessa célula a célula corrente