Problema do menor custo para percorrer a matriz
From AdonaiMedrado.Pro.Br
Revision as of 09:04, 15 October 2008 by 189.105.26.34 (Talk) (New page: == 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...)
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)