El problema de Número Máximo de Movimientos en una Grid es un desafío algorítmico frecuentemente encontrado en plataformas de coding como LeetCode. La tarea consiste en determinar el número máximo de movimientos posibles comenzando desde cualquier célula en la primera columna de una m x n matrix, siguiendo un criterio específico de movimiento.
Enunciado del Problema
Para un m x n matrix indexado desde 0, compuesta por enteros positivos, puedes comenzar en cualquier celda de la primera columna y realizar movimientos a las siguientes celdas: (row – 1, col + 1), (row, col + 1) y (row + 1, col + 1). El valor de la celda nueva debe ser estrictamente mayor que el de la celda actual.
Solución
Para abordar este problema, podemos emplear un algoritmo basado en Dynamic Programming para calcular el número máximo de movimientos. La solución implica iterar sobre todas las filas de la primera columna de la grid y utilizar una recursive function que calcule los movimientos válidos
import java.util.Arrays;
public class MaxMovesInGrid {
public int maxMoves(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
for (int[] row : dp) {
Arrays.fill(row, -1);
}
int maxMoves = 0;
for (int i = 0; i < m; i++) {
maxMoves = Math.max(maxMoves, dfs(grid, dp, i, 0));
}
return maxMoves;
}
private int dfs(int[][] grid, int[][] dp, int row, int col) {
if (col == grid[0].length - 1) {
return 0;
}
if (dp[row][col] != -1) {
return dp[row][col];
}
int maxMoves = 0;
int[] dRow = {-1, 0, 1};
for (int i = 0; i < 3; i++) {
int newRow = row + dRow[i];
int newCol = col + 1;
if (newRow >= 0 && newRow < grid.length && grid[newRow][newCol] > grid[row][col]) {
maxMoves = Math.max(maxMoves, 1 + dfs(grid, dp, newRow, newCol));
}
}
return dp[row][col] = maxMoves;
}
}
Conclusión
Esta solución eficiente aprovecha el poder del Dynamic Programming para garantizar que todos los caminos posibles sean evaluados. La implementación en Java es robusta y se adapta a las restricciones especificadas en el problema.