Problema do menor custo para percorrer a matriz

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

1. a saída sempre poderá ser encontrada seguindo-se os menores valores das casas vizinhas (desconsiderando, evidentemente, o último visitado);
2. 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).
3. 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)