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
##..##..###.
....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....#.
.....###....
##.1##..###.
...101#..#..
.##111....#.
.....###....
Na segunda execu��o teremos:
.#2#2#.#.#.#
##21##2.###.
..2101#..#..
.##1112...#.
..222###....
##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" <[EMAIL PROTECTED]>
To: <[EMAIL PROTECTED]>
Sent: Thursday, July 04, 2002 5:10 PM
Subject: [obm-l] Um Algoritmo
Legal
>
> 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
