Re: [obm-l] Um Algoritmo Legal

["Eduardo Casagrande Stabel" <dudasta@xxxxxxxxxxxx>]

Oi Paulo,

talvez não seja o melhor algoritmo, mas uma idéia simples é a seguinte:

*****
Construa uma outra matriz X NxP com um 1 na mesma posição onde a minhoca
está e 0 em todas as outras posições, e uma matriz Y NxP toda zerada.

INICIO

Para cada 1 presente na matriz X verifique na vizinhança dos elementos de
LAB onde existe 1 e marque esses elementos na matriz Y (NxP).

(A matriz Y marca todos os movimentos possíveis, sem morte, da minhoca nesta
rodada)

Acrescente à X os elementos de Y que são 1 e que em X eram 0.

Se as matrizes X e Y forem iguais o programa terminha e devolve "0".

Se a matriz X tiver algum elemento em sua borda igual a 1 então o programa
termina e devolve o número de vezes que executou INICIO.

Zere a matriz Y e repita o procedimento desde INICIO.
*****

Por que o programa funciona? No caso de Y e X serem iguais, é claro que todo
movimento a partir das casas com 1 em X só levam a casas que já eram 1 em X,
portanto não se pode fugir das casas de X, e portanto se está preso no
labirinto.

No caso de haver uma saída do labirinto, na vez K que passamos em INICIO Y
mostra todas as possibilidades de a minhoca estar após o K movimentos, TODAS
as possibilidades, inclusive os K primeiros movimentos do caminho ideal (que
faz sair do labirinto na quantidade mínima de movimentos). Segue que se for
possível sair do labirinto em K movimentos, na K-ésima vez que passamos por
INICIO a matriz  vai incluir um 1 na borda.

Está bom?

Eduardo Casagrande Stabel.
Porto Alegre, RS.


From: "Paulo Santa Rita" <p_ssr@hotmail.com>
> 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
>
>
>
>
>
> =========================================================================
> Instruções para entrar na lista, sair da lista e usar a lista em
> http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
> O administrador desta lista é <nicolau@mat.puc-rio.br>
> =========================================================================
>
>

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================