Difference between revisions of "Problema do menor custo para percorrer a matriz"
From AdonaiMedrado.Pro.Br
(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...) |
(→Retorno) |
||
| (4 intermediate revisions by 3 users not shown) | |||
| Line 5: | Line 5: | ||
#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). | #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 | + | Faça uma classe ProblemaMenorCusto 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 === | === Exemplo de Entrada === | ||
==== Entrada ==== | ==== Entrada ==== | ||
| − | {{ 1 8 9 10 11 }, | + | {{ 1, 8, 9, 10, 11 }, |
| − | { 2 7 5 1 4 }, | + | { 2, 7, 5, 1, 4 }, |
| − | { 13 2 81 9 20 }, | + | { 13, 2, 81, 9, 20 }, |
| − | { 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) | |
Latest revision as of 12:14, 26 November 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 ProblemaMenorCusto 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)
