Problemas de Matrices y Cuadrículas

Relleno de inundación (como la herramienta Bote de pintura): desde una celda inicial, cambia todas las celdas conectadas del mismo color. Tanto DFS como BFS funcionan.

Número de islas: escanea la cuadrícula; cuando encuentre un 1, ejecute DFS/BFS para marcar toda la isla como visitada, luego incremente su recuento.

def num_islands(grid):
    count = 0
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c] == '1':
                dfs(grid, r, c)  # mark island
                count += 1
    return count

Naranjas podridas - BFS de múltiples fuentes

Todas las naranjas inicialmente podridas son fuentes. Empújelos a todos a la cola en el momento 0, luego a BFS. Cada nivel es de un minuto. Cuando la cola se agote, comprueba si quedan naranjas frescas.

Minute 0:  [2, 1, 1]    2 = rotten, 1 = fresh
           [1, 1, 0]
           [0, 1, 1]

Minute 4:  [2, 2, 2]    All reachable oranges rotten
           [2, 2, 0]
           [0, 2, 2]

La idea clave: BFS de múltiples fuentes comienza desde múltiples nodos simultáneamente, no desde uno.

Recorrido de matriz en espiral

Recorra la matriz en orden espiral: derecha → abajo → izquierda → arriba, reduciendo los límites después de cada pasada.

def spiral(matrix):
    res = []
    top, bot = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    while top <= bot and left <= right:
        for c in range(left, right + 1):
            res.append(matrix[top][c])
        top += 1
        for r in range(top, bot + 1):
            res.append(matrix[r][right])
        right -= 1
        if top <= bot:
            for c in range(right, left - 1, -1):
                res.append(matrix[bot][c])
            bot -= 1
        if left <= right:
            for r in range(bot, top - 1, -1):
                res.append(matrix[r][left])
            left += 1
    return res

Rotación de matriz (90°)

Gire una matriz N×N en el sentido de las agujas del reloj: transponer (intercambiar [r][c] con [c][r]), luego invertir cada fila.

Original → Transpose → Reverse rows
1 2 3     1 4 7       7 4 1
4 5 6  →  2 5 8   →   8 5 2
7 8 9     3 6 9       9 6 3

Buscar en una matriz 2D ordenada

Dos variantes comunes:

• Filas y columnas ordenadas de forma independiente: comienza desde la esquina superior derecha. Si el objetivo es más pequeño, muévete hacia la izquierda; si es más grande, baje. O(metro + norte).
• Completamente ordenado (cada fila comienza donde termina la anterior): trátela como una matriz ordenada plana y búsqueda binaria. O(log(m × n)).

Programación dinámica en Grids

Rutas únicas: cuenta las rutas desde arriba a la izquierda hasta abajo a la derecha moviéndose solo hacia la derecha o hacia abajo. dp[r][c] = dp[r-1][c] + dp[r][c-1].

Suma mínima de ruta: la misma idea pero elija la ruta entrante mínima.

Suelen ser la introducción más sencilla a la programación dinámica 2D.

Hoja de referencia de patrones de cuadrícula

| Patrón | Técnica | Problema clave | |---------|-----------|-------------| | Ruta más corta (no ponderada) | BFS | Laberinto camino más corto | | Componentes conectados | DFS/BFS | Número de islas | | Difusión de fuentes múltiples | BFS de múltiples fuentes | Naranjas podridas | | Orden transversal | Indicadores de límites | Matriz espiral | | Transformación in situ | Transponer + invertir | Girar imagen | | Contando caminos | DP | Caminos Únicos | | Buscar en cuadrícula ordenada | Escalera/búsqueda binaria | Buscar matriz 2D |

📚 Lecturas adicionales

• NeetCode - Programación dinámica 2D - problemas de DP de cuadrícula con explicaciones visuales
• Manual de entrevistas técnicas - Matrix - patrones y técnicas comunes
• LeetCode Matrix tag - cientos de problemas de práctica