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 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)