Re: [obm-l] Um Algoritmo Legal

[Vinicius José Fortuna <vinicius.fortuna@xxxxxxxxxxxxx>]

Olá Paulo,

 

O melhor algoritmo que se pode obter para esse problema é O(NxP), já que se gasta isso só para ler a matriz e procurar a minhoca (cuja posição inicial não é dada diretamente). Dessa forma descreverei um algoritmo com tal complexidade.

 

Podemos visualizar o tabuleiro como um grafo onde há um nó para cada casa com valor 1 ou 2. Há arestas entre dois nós se e somente se um nó é adjacente ao outro, o que significa que podemos alcançar um a partir do outro por um único movimento da minhoca. Temos então um problema de caminho mínimo em grafo não direcionado com arestas de peso 1. Podemos então usar uma busca em largura que, em um grafo, o tempo é O(n+m), onde n é o número de nós e m o número de arestas. Como n é O(NxP) e m é <(8n)/2, portanto tb O(NxP), temos que a busca em largura funciona em O(NxP).

 

Como funciona?

Marcamos todos os nós como não visitados, exceto onde está a minhoca, cuja distância a ela mesma é zero:

.#.#.#.#.#.#
##..##..###.
....0.#..#..
.##.......#.
.....###....
# : casa com brasa

. casa não visitada

Número : distância à minhoca

 

Colocamos a posição inicial em uma lista L .

Repetimos então, até visitarmos uma casa da borda, os seguintes passos:

início

Se a lista L é vazia, termina o programa sem solução

 

Para cada elemento p da lista L:

    Para cada vizinho f de p não brasa e não visitado

        Marque f com 1 mais o valor de p

        Coloque f em uma nova lista NL

 

Substitua a lista L pela nova lista NL

fim

Se terminarmos alcançando uma casa da borda, o valor dessa casa será a solução.

 

Por exemplo:

 

Na primeira execução teremos:

.#.#.#.#.#.#
##.1##..###.
...101#..#..
.##111....#.
.....###....

Na segunda execução teremos:

.#2#2#.#.#.#
##21##2.###.
..2101#..#..
.##1112...#.
..222###....

E o programa terminará com a solução 2.

 

Um abraço

 

Vinicius Fortuna

 

 

----- Original Message -----

From: "Paulo Santa Rita" <p_ssr@hotmail.com>

To: <obm-l@mat.puc-rio.br>

Sent: Thursday, July 04, 2002 5:10 PM

Subject: [obm-l] Um Algoritmo Legal

> Ola Pessoal,
> 
> Segue abaixo a traducao de um problema 
de computacao que recebi de outra 
> lista e que achei interessante e 
digno de figurar nesta nostra lista OBM-L.
> 
> O Algoritmo e de 
IA.
> 
> Uma minhoca esta em uma celula de um labirinto quadriculado 
NxP ( N linhas, 
> P colunas ). Ela almeja sair do labirinto. Todavia, 
sabe-se que nalgumas 
> celulas ha brasa, noutras, terra. A minhoca se 
movimenta como o rei em um 
> tabuleiro de xadrex.
> 
> Os 
dados de entrada sao : N ,P e LAB(N,P).
> 
> LAB(N,P) uma matriz da 
forma :
> 
> 0 (zero) -> casa com brasa
> 1 (um) -> casa 
com terra
> 2 (dois) -> a minhoca
> 
> Exemplo :
> 
> 101010101010
> 001100110001
> 111121011011
> 
100111111101
> 111110001111
> 
> O programa ( function ) deve 
devolver :
> 
> 1) 0 ( zero ) se nao houver um caminho de 
saida
> 2) N ( numero inteiro positivo ) se houver. Neste caso N e o menor 
numero de 
> passos que a minhoca deve dar para sair do labirinto sem se 
queimar.
> 
> O programa pode estar em qualquer linguagem padrao ou 
em pseudo-codigo.
> 
> OBS : O tempo de resposta ( inteligencia do 
algoritmo ) sera o principal 
> fator na classifucacao final dos 
algoritmos.
> 
> Um Abraco a Todos
> Paulo Santa Rita
> 
5,1709,040702