Algoritmia y Estructuras de Datos Avanzadas · Semana 4 · Sesión 1

Matrices y grillas

Objetivo: trabajar con listas 2D y grillas, que se usan otra vez en prefijas 2D y en grafos
Plan de la sesión

Qué vamos a ver hoy

MinTema
0–15Crear y leer matrices
15–30Recorridos: filas, columnas, diagonales y espiral
30–40Transpuesta, rotación y reflejos
40–60Vecinos con dx, dy y límites
60–70Multiplicación de matrices y aplanar
70–80Beautiful Matrix y Number Spiral
80–85Entrada y salida rápida, con Number Spiral como caso
85–90Formato del Contest 1
Parte 1

Crear y leer matrices

Una matriz en Python es una lista de listas.

Crear una matriz

Por qué [[0]*m]*n falla

M = [[0] * m] * n      # n referencias a la MISMA fila

Haga clic en una celda. Las n filas son la misma lista, así que el cambio aparece en todas.

M = [[0] * m for _ in range(n)]   # n filas distintas

Cada vuelta del for crea una lista nueva. El cambio aparece en una sola celda.

Leer matrices

Matrices de números y grillas de caracteres

# n filas de m números
n, m = map(int, input().split())
M = [list(map(int, input().split())) for _ in range(n)]

# n filas de caracteres '#' y '.'
g = [input() for _ in range(n)]
g[i][j]          # carácter de la fila i, columna j

# si hay que modificar la grilla
g = [list(input()) for _ in range(n)]

Una fila leída como string no se puede modificar. Para cambiar celdas se lee como lista.

Parte 2

Recorridos

El orden en que se visitan las celdas.

Recorridos

Seis formas de recorrer una matriz


    

    

      

      

    

  

  





  
Diagonales

  
Cada diagonal tiene un valor constante

  

    

      

      
Haga clic en una celda.

    

    

      

      
    
        
  • En la diagonal que baja a la derecha, i − j es constante. La principal es i − j = 0.
    • 
        
  • En la diagonal que baja a la izquierda, i + j es constante. La secundaria es i + j = n − 1.
    • 
        
  • Hay n + m − 1 diagonales de cada tipo.
    • 
        
  • Para agruparlas: diag[i - j + m - 1] y anti[i + j].
    • 
      

      
En el problema de las N reinas (semana 11) se usan estos índices para saber si dos reinas se atacan.

    

  






  
Parte 3

  
Transformaciones

  
Transpuesta, rotaciones y reflejos con zip y slicing.






  
Transformaciones

  
Transponer, rotar y reflejar

  

    

      

      

      

    

    

      

      
    

  

  





  
Parte 4

  
Vecinos

  
Moverse a las celdas de al lado sin salirse de la grilla.






  
Vecinos

  
Vecinos con dx, dy

  

    

      

      

      

    

    

      
DX = [-1, 1, 0, 0]         # arriba, abajo,
DY = [0, 0, -1, 1]         # izquierda, derecha

for d in range(4):
    ni, nj = i + DX[d], j + DY[d]
    if 0 <= ni < n and 0 <= nj < m and g[ni][nj] != '#':
        # (ni, nj) es un vecino válido
        ...

# 8 direcciones: todos los (di, dj) salvo (0, 0)
for di in (-1, 0, 1):
    for dj in (-1, 0, 1):
        if di == 0 and dj == 0:
            continue
        ...

      
Primero se revisan los límites y después la celda. Si se revisa la celda primero, g[-1] no da error: lee la última fila.

    

  

  





  
Parte 5

  
Multiplicación y aplanado

  
Producto de matrices en O(n³) y matrices guardadas en una sola lista.






  
Multiplicación

  
Fila de A por columna de B

  

    

      
×
      
=
      

    

    

    

      
# A es n×m, B es m×p, C es n×p
C = [[0] * p for _ in range(n)]
for i in range(n):
    for j in range(p):
        s = 0
        for k in range(m):
            s += A[i][k] * B[k][j]
        C[i][j] = s

      

        
Tres bucles anidados: O(n · m · p). Con matrices n × n es O(n³).

        
Con n = 500 son 1.25·10⁸ multiplicaciones. Con PyPy tardó 0.19 s en un Apple M4; en el juez queda más cerca del límite.

        
Extensión: elevando una matriz 2 × 2 a la potencia k se calcula el k-ésimo Fibonacci en O(log k). Se retoma como reto en la semana 8.

      

    

  






  
Aplanar

  
Una matriz en una sola lista

  

    

      

      

      

    

    

      
k = i * m + j          # (i, j) → k
i, j = divmod(k, m)    # k → (i, j)
vis = bytearray(n * m) # visitados, 1 byte por celda

      
Cada celda queda representada por un solo entero. En BFS (semana 12) la cola guarda enteros en lugar de tuplas (i, j).

      
En PyPy también es más rápido: sumar los 4 vecinos de 10⁶ celdas tardó 0.005 s con M[i][j] y 0.002 s aplanado.

    

  

  





  
Parte 6

  
Problemas

  
Beautiful Matrix, Number Spiral y grillas de AtCoder.






  
Codeforces 263A · Beautiful Matrix

  
Llevar el 1 al centro

  

    

      
Una matriz 5 × 5 tiene un solo 1. Cada movimiento intercambia dos filas vecinas o dos columnas vecinas. ¿Cuántos movimientos hacen falta para llevar el 1 al centro?

      

      

    

    

      
def main():
    for i in range(5):
        fila = input().split()
        for j in range(5):
            if fila[j] == "1":
                print(abs(i - 2) + abs(j - 2))

main()

      
Es la distancia Manhattan al centro (2, 2): cada movimiento cambia la fila o la columna en 1.

    

  

  





  
CSES 1071 · Number Spiral

  
El valor en la fila y, columna x

  

    

      

      
Haga clic en una celda. Las capas se colorean por paridad.

    

    

      

      
def valor(y, x):
    z = max(y, x)              # capa
    if z % 2 == 0:
        if y == z:
            return z * z - x + 1
        return (z - 1) ** 2 + y
    else:
        if x == z:
            return z * z - y + 1
        return (z - 1) ** 2 + x

      
y, x ≤ 10⁹ y hasta 10⁵ consultas: no se puede construir la grilla. Cada consulta es O(1). El resultado llega a 10¹⁸ y Python no se desborda.

    

  

  





  
Entrada y salida rápida

  
Number Spiral con 10⁵ consultas

  

    

      Con input() y print
      
t = int(input())
for _ in range(t):
    y, x = map(int, input().split())
    # ... calcular v ...
    print(v)

    

    

      Con lectura y escritura rápidas
      
import sys
input = sys.stdin.readline
t = int(input())
ans = []
for _ in range(t):
    y, x = map(int, input().split())
    # ... calcular v ...
    ans.append(v)
sys.stdout.write("\n".join(map(str, ans)) + "\n")

    

  

  

    
input() + print
0.14 s

    
rápida
0.04 s

  

  
El cálculo es el mismo en los dos. Cambia solo la forma de leer y escribir. Medido con PyPy 3.11, Apple M4, con 10⁵ consultas aleatorias. El juez suele ser más lento.

  





  
Entrada y salida rápida

  
Por qué es más rápida

  

    

      
    
        
  • input() hace trabajo extra en cada llamada: entre otras cosas, vacía la salida pendiente antes de leer. sys.stdin.readline lee la línea directamente.
    • 
        
  • print hace una escritura por cada línea. join arma un solo string y sys.stdout.write lo escribe una vez.
    • 
        
  • La diferencia se nota desde unas 10⁵ líneas. Con pocas líneas da lo mismo.
    • 
      

      
# leer toda la entrada de una vez
data = sys.stdin.buffer.read().split()
t = int(data[0])
# data[1], data[2], ... son bytes; int() los convierte

    

    

      
Leer 10⁶ enteros, uno por línea

      
input()
0.13 s

      
readline
0.07 s

      
Escribir 10⁶ enteros, uno por línea

      
print
0.025 s

      
join + write
0.014 s

      
PyPy 3.11, Apple M4, salida a /dev/null.

    

  

  





  
AtCoder · grillas

  
Dos problemas B de grillas

  

    

      
ABC075 B · Minesweeper

      
Cambiar cada . por la cantidad de # entre sus 8 vecinos.

      
for i in range(h):
    fila = []
    for j in range(w):
        if g[i][j] == "#":
            fila.append("#")
            continue
        c = 0
        for di in (-1, 0, 1):
            for dj in (-1, 0, 1):
                ni, nj = i + di, j + dj
                if 0 <= ni < h and 0 <= nj < w and g[ni][nj] == "#":
                    c += 1
        fila.append(str(c))
    print("".join(fila))

    

    

      
ABC107 B · Grid Compression

      
Quitar las filas y columnas que solo tienen ..

      
g = [f for f in g if "#" in f]        # filas
cols = [c for c in zip(*g) if "#" in c] # columnas
g = ["".join(f) for f in zip(*cols)]    # volver a filas

      
Las columnas se filtran transponiendo con zip(*g), filtrando y transponiendo otra vez.

    

  






  
Tarea

  
Problemas de matrices

  





  
Sesión 2

  
Contest 1

  

    
    
      
  • Cubre las semanas 1 a 4.
    • 
      
  • Dura 90 minutos y es presencial.
    • 
      
  • Tiene de 4 a 6 problemas, ordenados de menor a mayor dificultad.
    • 
      
  • Vale el 5 % de la nota.
    • 
      
  • Se hace en el grupo del curso: [enlace pendiente].
    • 
    

    

      
Qué repasar

      
    
        
  • Leer la entrada y escribir la salida con el formato pedido.
    • 
        
  • Tabla de restricciones contra complejidad.
    • 
        
  • Slicing, join, frecuencias.
    • 
        
  • Crear matrices, vecinos y límites.
    • 
      

    

  

  





  
Resumen

  
Reglas para matrices en Python

  
    
    
  1. Crear con [[0] * m for _ in range(n)].
    2. 
    
  2. Leer grillas con input(), y como lista si hay que modificarlas.
    3. 
    
  3. Revisar los límites antes de acceder a una celda vecina.
    4. 
    
  4. Transponer con zip(*M) y rotar con zip(*M[::-1]).
    5. 
    
  5. Guardar la fila en una variable dentro de los bucles internos.
    6. 
    
  6. Con 10⁵ líneas o más, leer con sys.stdin.readline y escribir una sola vez con join.
    7.