0
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.

4
  • No se mucho de Java pero el método que yo usaría seria recorrer la matriz con un for loop y en cada iteración checaría los números que estan alrededor. De esos números tomaría el que tiene el valor mas bajo y almacenaría su posición en un array aparte. Commented el 4 abr. 2021 a las 5:01
  • Solo que no es el número más bajo, toca mirar todos los adyacentes, almacenar y hacer la suma, si se tiene la menor suma, se toman los valores y se muestran los n pedidos, pero pues en la cabeza está, en código no lo sé :(
    – Asnaslem
    Commented el 4 abr. 2021 a las 5:06
  • Bienvenido, debes agregar lo que trataste o investigaste por favir , revisa Cómo preguntar, saludos.
    – Jorgesys
    Commented el 4 abr. 2021 a las 22:10
  • @Jorgesys muchas gracias, ya respondí a mi pregunta con lo que hice.
    – Asnaslem
    Commented el 4 abr. 2021 a las 23:03

2 respuestas 2

2

Para resolver este problema, debemos tener en claro las siguientes premisas:

  • Este array simula una matriz, por lo que será mas fácil recorrerla si primero la transformamos a una matriz real, aunque no es obligatorio hacerlo.
  • Ya que el problema es encontrar el camino con la sumatoria mas baja recorriendo la matriz de izquierda a derecha, inferimos que estamos obligados a encontrar todos los posibles caminos a recorrer en la matriz respetando las reglas de desplazamiento. Esto también significa que debemos iniciar un camino nuevo por cada fila de la matriz, puesto que no sabemos por cual camino iniciar.
  • Una vez que hayamos todos los posibles caminos, basta con hacer sumatoria de cada uno y seleccionar el que tenga la suma mas baja.

Los problemas a solucionar son:

  • ¿Cómo convierto el array a matriz?
  • ¿Cómo puedo recorrerlo respetando las reglas de desplazamiento?
  • ¿Cómo puedo registrar cada camino posible en el recorrido?
  • ¿Cómo puedo detectar cual es el camino de sumatoria mas baja? (la cual es la pregunta definitiva)

El siguiente código nos permitirá hacerlo:

import java.util.List;
import java.util.ArrayList;

public class MatrixPaths {
    public static void main(String[] args) {
        // valores a trabajar
        int[] myArray = {1, 2, 9, 2, 5, 3, 5, 1, 5};
        int n = 3;

        // convertimos el array a matriz
        int[][] matrix = convertArrayToMatrix(myArray, n);
        
        // utilizaremos recursión y clones de listas para recorrer la matriz
        List<List<Integer>> allPaths = findAllPaths(matrix);
        
        // variables que nos permitirán capturar el camino adecuado
        int max = Integer.MAX_VALUE;
        List<Integer> currentPath = null;
        
        // Calculamos cuál es el camino con la sumatoria mas baja
        for (List<Integer> path : allPaths) {
            int sum = listSum(path);
            if(sum < max) {
                max = sum;
                currentPath = new ArrayList<>(path);
            }
        }
        
        // Imprimimos el camino encontrado
        System.out.println(currentPath.stream().map(i -> i.toString()).collect(java.util.stream.Collectors.joining(" ")));
    }
    
    // método que nos permitirá convertir el arreglo a matriz
    public static int[][] convertArrayToMatrix(int[] array, int column) {
        int[][] matrix = new int[column][column];
        for(int i = 0; i < column; i++)
            for(int j = 0; j < column; j++)
                matrix[i][j] = array[(i * column) + j];
        return matrix;
    }
    
    // método para calcular la sumatoria de un recorrido
    public static int listSum(List<Integer> values) {
        return values.stream().reduce(0, (a, b) -> a + b);
    }

    // método inicial del recorrido de la matriz
    public static List<List<Integer>> findAllPaths(int[][] matrix) {
        // aquí almacenaremos todas las posibles combinaciones de recorridos
        List<List<Integer>> allPaths = new ArrayList<>();
        // tamaño de la matriz
        int n = matrix.length;
        // iteración sobre la primera columna de la matriz
        for (int i = 0; i < n; i++) {
            // Se inicializa un posible camino con el primer elemento de la fila actual
            List<Integer> path = new ArrayList<>();
            path.add(matrix[i][0]);
            // método recursivo para explorar y registrar todos los posibles caminos
            findPaths(matrix, i, 0, path, allPaths);
        }
        // retorno de resultados
        return allPaths;
    }

    private static void findPaths(int[][] matrix, int row, int col, List<Integer> path, List<List<Integer>> allPaths) {
        // tamaño de la matriz
        int n = matrix.length;
        
        // al alcanzar el final de la matriz, agregamos el recorrido final al registro clonando el camino resultante y terminando la recursión
        if (col >= n - 1) {
            allPaths.add(new ArrayList<>(path));
            return;
        }
        
        // aquí definiremos las posibles direcciones para movernos
        int[][] directions = {{-1, 1}, {0, 1}, {1, 1}};
        
        // iteración de todas las posibles direcciones
        for (int[] dir : directions) {
            // cálculo de la nueva fila y columna para la presente ejecución
            int newRow = row + dir[0];
            int newCol = col + dir[1];
            // si la fila o columna están fuera de la matriz, ignoramos y continuamos con la siguiente dirección
            if (newRow < 0 || newRow >= n || newCol >= n) {
                continue;
            }
            // agregamos el elemento de la matriz en el camino actual
            path.add(matrix[newRow][newCol]);
            // usamos recursión para explorar la siguiente dirección del camino
            findPaths(matrix, newRow, newCol, path, allPaths);
            // removemos un elemento del camino actual para considerar las demás direcciones a tomar
            path.remove(path.size() - 1);
        }
    }
}
1

Buenas tardes @Asnaslem, te dejo la solución al problema planteado en mi Github https://github.com/aabedoya/JavaAndres/blob/main/myArray.java Y la comparto por aquí también.

public class myArray{
    static int[] myArray = { 3, 2, 9, 6, 5, 3, 5, 7, 5, 1, 2, 3, 4, 5, 6, 7};//Valores que nos entregan en el Array
    static int n = 4;//Valor de n, tener en cuenta que si n cambia, el numero de valores del myArray debe aumentar o disminuir

public static void main(String[] args) {
    //boolean encontrado = true;
    int filas = n;
    //Variable filas que es igual al n que nos dan para que se comprenda mejor
    int columnas = n;
    //Variable columnas que es igual al n que nos dan para que se comprenda mejor
    int x = 0; 
    //Variable x para recorrer el myArray inicial que nos dan
    int menor = 9;
    //Variable para guardar el numero mas paqueño, se inicia en 9 que es el más alto que puede tener el Array
    int matriz[][] = new int[filas][columnas];
    //Array de 2 dimensiones que contendrá los valores de MyArray unidimensional
    int[] camino = new int[n];
    //Array que guardara los números que menos suman al pasar la matriz de izquierda a derecha 
    for(int i=0;i<filas;i++){
        for(int j=0; j<columnas;j++){
            matriz[i][j]=myArray[x];
            x=x+1;
            System.out.print(matriz[i][j]);
        }
        System.out.println();
    }
    int control =0;
    //Variable control que guarda la posición de la columna donde esta el menor numero 
    for(int i=0;i<columnas;i++){
        for(int j=0; j<filas;j++){
            if(matriz[j][i]<menor){
                if(control==j){
                    menor=matriz[j][i];
                    camino[i]=menor;
                }
                else if(control+1==j){
                    menor=matriz[j][i];
                    camino[i]=menor;
                }
                else if(control-1==j){
                    menor=matriz[j][i];
                    camino[i]=menor;                      
                }
                    
            
            }
        }
        menor = 9;
        System.out.println();
    }
    
    for(int i=0;i<camino.length;i++){
        System.out.print(camino[i]);
    }
}

} Ejecución en Java

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.