Difference between revisions of "Problema do menor custo para percorrer a matriz"
From AdonaiMedrado.Pro.Br
(→Entrada) |
(→Entrada) |
||
Line 14: | Line 14: | ||
{ 15 6 4 11 3 }, | { 15 6 4 11 3 }, | ||
{ 13 22 50 29 11 }, | { 13 22 50 29 11 }, | ||
− | { 13 1 8 5 4 } } | + | { 13 1 8 5 4 } } |
==== Retorno ==== | ==== Retorno ==== | ||
51 | 51 | ||
(Elementos percorridos: 1, 2, 7, 2, 6, 4, 11, 3, 11, 4) | (Elementos percorridos: 1, 2, 7, 2, 6, 4, 11, 3, 11, 4) |
Revision as of 09:05, 15 October 2008
Dificuldade 1
Considere uma matriz MxN que representa um labirinto, cuja entrada é o elemento (1,1) e a sáida o elemento (M,N). Sabendo que
- a saída sempre poderá ser encontrada seguindo-se os menores valores das casas vizinhas (desconsiderando, evidentemente, o último visitado);
- em nenhum caso haverá na entrada dois elementos nas casas vizinhas que tenham o mesmo valor (exceto se este valor for igual ao último que deveria ter sido visitado).
- só é possível "andar" na horizontal e na vertical, assim, considera-se como casa vizinha do elemento a(i,j) o elemento a(i-1,j), a(i+1,j), a(i,j-1) e a(i, j+1).
Faça uma classe ProblemaMenorCurto com o método público Dificuldade1 que receberá como parâmetro uma matriz de inteiros (int[][]). O retorno será um int com a soma dos elementos percorridos para do início do labirinto (1,1) chegar-se até ao final (M,N).
Exemplo de Entrada
Entrada
{{ 1 8 9 10 11 }, { 2 7 5 1 4 }, { 13 2 81 9 20 }, { 15 6 4 11 3 }, { 13 22 50 29 11 }, { 13 1 8 5 4 } }
Retorno
51 (Elementos percorridos: 1, 2, 7, 2, 6, 4, 11, 3, 11, 4)