static int[] myArray = { 1, 2, 9, 2, 5, 3, 5, 1, 5 };
static int n = 3;
Se tiene una matriz de n x n que contiene números del 1 al 9, simulando una matriz unidimensional, por ejemplo:
1 2 9
2 5 3
5 1 5
Se representaría como {1, 2, 9, 2, 5, 3, 5, 1, 5}. El objetivo es identificar el camino que de la menor suma al recorrer el arreglo bi-dimensional de izquierda a derecha. Se empieza en la columna izquierda y se mueve siempre una columna a la derecha de la misma fila o a una fila hacia arriba o hacia abajo. En el ejemplo, si parte de 1, puede pasar al 2 o al 5. De ahí, si pasó al 5 puede pasar al 9 al 3 o al 5. Por otro lado, si pasa del 1 al 2, desde el 2 de la columna del medio no podría pasar al 5 de la última fila en la columna derecha. El valor de n puede ser entre 1 y 4.
Es necesario encontrar el camino que produce el número más bajo al sumar los valores de cada número que visita. Así que para el ejemplo, la ruta con la menor suma sería 1, 2, 3.
El resultado del programa debe ser los n números por los que pasó para obtener la menor suma separados por un espacio, para el ejemplo, la salida sería exactamente así:
1 2 3
En el momento tengo convertido el arreglo uni-dimensional en una matriz bi-dimensional, así:
static int[] myArray = { 1, 2, 9, 2, 5, 3, 5, 1, 5 };
static int n = 3;
public static void main(String args[]) {
int valorRaiz = 1;
for(int i = 1; i < 10; i++){
valorRaiz = (valorRaiz + myArray.length/valorRaiz) / 2;
}
int nuevaMatriz[][] = new int[valorRaiz][valorRaiz];
int cont = 0;
for (int i = 0; i < valorRaiz; i++) {
for (int j = 0; j < valorRaiz; j++) {
nuevaMatriz[i][j] = myArray[cont];
cont++;
}
}
calcularMenores(nuevaMatriz, n, valorRaiz);
}
public static void calcularMenores(int[][] matriz, int cantidadNumeros, int valorRaiz) {
int valoresSuma[] = new int[cantidadNumeros];
int menor = 50;
// 2 x 2
if(n == 2){
int[] posibilidades = new int[n*2];
for(int i=0; i<matriz.length; i++){
for(int j=0; j<matriz.length; j++){
posibilidades[2*i+j] = matriz[i][0] + matriz[j][1];
if(posibilidades[2*i+j]<menor) {
menor = posibilidades[2*i+j];
valoresSuma[0] = matriz[i][0];
valoresSuma[1] = matriz[j][1];
}
}
}
}
}
Por lo tanto, tengo ahora una matriz, para cuando es 2x2 me funciona, sin embargo para nxn no sé como continuar el algoritmo para tener lo requerido.