04 · Matrices

Aprender a programar · Ruta de Aprendizaje

Antes de empezar. Recorrer un vector con índices: 03 - Arreglos y búsqueda lineal.

🎯 Objetivos

Al terminar este módulo sabes:

  • Crear y leer una matriz de N×M como vector de vectores.
  • Recorrerla con doble ciclo: sumas por fila/columna, búsqueda 2D.
  • No salirte nunca de los bordes.

📖 La lección

Una matriz es un vector de vectores

Una matriz organiza datos en filas y columnas. Aquí usamos dimensiones n >= 1, m >= 1: con n = 2 y m = 3 habrá seis casillas.

int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m)); // n filas, m columnas, todo en 0

a[i][j] es la fila i, columna j. El número de filas es a.size() y el de columnas a[i].size() — útil cuando la matriz viene de otro lado.

El dibujo usa las mismas dimensiones del ejemplo: 2 filas y 3 columnas.

2 filas × 3 columnas: 6 casillas251403j = 0j = 1j = 2i = 0i = 1a[1][2] = 3primero la fila, después la columna

Si el diagrama no cabe, deslízalo horizontalmente.

La forma de no confundirse nunca: a[i] es una fila completa (un vector), y a[i][j] es una casilla dentro de esa fila. Por eso el primer índice es la fila.

El doble ciclo

Leer, procesar y responder por filas:

// supone: int n, m; vector<vector<int>> a;  // la matriz del bloque anterior
for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        cin >> a[i][j];
 
for (int i = 0; i < n; i++) {
    long long suma = 0;
    for (int j = 0; j < m; j++) suma += a[i][j];
    cout << "fila " << i << ": " << suma << "\n";
}

Prueba la entrada 2 3 seguida de las filas 2 5 1 y 4 0 3. El programa imprime fila 0: 8 y fila 1: 7:

ija[i][j]suma de la fila tras sumar
0022
0157
0218
1044 (se reinició a cero)
1104
1237

Si recorres por columnas, las sumas son 6, 5 y 4. En ambos casos visitas seis casillas; cambia qué grupo resume cada acumulador.

Para columnas, invierte los ciclos (for j afuera, for i adentro): el ciclo de afuera decide qué se recorre “de a uno”.

Volvemos al esquema de 2 × 3. Los números indican el orden de visita, no los valores guardados: las casillas conservan sus datos al cambiar el recorrido.

Por filas: i afuera, j adentro123456Por columnas: j afuera, i adentro135246Los números son turnos de visita, no valores guardados.

Si el diagrama no cabe, deslízalo horizontalmente.

En ambos casos se visitan n·m casillas: una matriz de 1000×1000 requiere un millón de visitas. El tiempo depende también de lo que hagas en cada casilla. En 07 - Cuánto se demora tu programa llamaremos O(n·m) a un recorrido que hace una cantidad constante de trabajo por casilla.

Búsqueda en 2D

Buscar en una matriz es extender la búsqueda lineal: visitamos una casilla, comparamos y avanzamos. Definamos el orden: primero toda la fila 0, luego la fila 1, y así sucesivamente. «Primera aparición» se entiende en ese orden. La respuesta ahora necesita dos índices, fila y columna.

Usemos la misma matriz de la entrada anterior, con filas {2, 5, 1} y {4, 0, 3}, y busquemos el 0:

Buscamos 0 en la misma matriz de 2 × 3columna 0columna 1columna 2fila 02paso 15paso 21paso 3fila 14paso 40paso 53sin leerEl número grande es el dato guardado.Los pasos indican en qué orden comparamos.Encontrado: fila 1, columna 1.

Si el diagrama no cabe, deslízalo horizontalmente.

Comparamos 2, 5 y 1 en la primera fila, después 4 y 0 en la segunda. La respuesta es fila 1, columna 1, y ya no necesitamos revisar el 3. Un número mayor que el buscado tampoco permite cortar: las filas no están ordenadas.

Este bloque se coloca dentro de main, después de leer a y x:

// supone: int n, m, x; vector<vector<int>> a;  // la matriz ya leída; x es lo buscado
for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        if (a[i][j] == x) {
            cout << i << " " << j << "\n";
            return 0; // encontrado: terminamos el programa entero
        }
cout << "no esta\n";

Con x = 0, imprime 1 1. Con x = 8, revisa las seis casillas e imprime no esta. El mensaje de ausencia va después de ambos ciclos: no encontrar el dato en la primera fila no demuestra que falte en las demás.

Un break solo sale del ciclo interior: el ciclo de filas continuaría. Aquí usamos return 0 porque la búsqueda es toda la tarea del programa: termina main después de imprimir la respuesta. Si el programa debe seguir con otras tareas o consultas, conviene una función que devuelva las coordenadas; su return termina esa búsqueda y devuelve el control a main.

Si hay varias apariciones, se devuelve la primera por filas. El peor caso revisa n·m casillas: O(n·m) tiempo y O(1) memoria adicional. Para contar todas las apariciones habría que continuar y acumular los aciertos.

Antes de crearla: contar casillas

Una matriz de n filas y m columnas guarda n × m elementos. Con int de 4 bytes, una de 3000 × 3000 usa unos 36 MB solo en datos; con long long de 8 bytes, unos 72 MB. Dos matrices de ese último tamaño necesitan unos 144 MB. Una de 10000 × 10000 de int ya requiere unos 400 MB y no cabe en un límite de 256 MB.

El vector de filas y cada fila tienen un pequeño costo adicional. Suma además las estructuras auxiliares. Para hacer el cálculo en C++ sin que la multiplicación de dos int desborde antes de ampliarse, puedes usar 1LL * n * m * sizeof(int) para dimensiones dentro de estos ejemplos.

Guardar todas las casillas depende de la pregunta. Si solo piden la suma de cada fila y los datos llegan fila por fila, puedes leer y sumar sin conservar la matriz. Si necesitas comparar casillas alejadas más tarde, guardarla puede ser la representación apropiada.

Ejercicios de dedos (sin juez)

  1. Suma de la diagonal principal de una matriz cuadrada (a[i][i]).
  2. ¿Es simétrica? (a[i][j] == a[j][i] para todo par).

🏋️ Práctica

Práctica directa: Una suma por fila

Lee n,m (1 a 20) y la matriz. Imprime solo la suma de cada fila. Entrada: 2 3 / 2 5 1 / 4 0 3. Salida: 8 / 7.

En los ejemplos de entrada y salida, / separa líneas; no se escribe en el archivo.

Variación: Un resumen distinto

Lee una matriz de n×m, con 1 ≤ n,m ≤ 100 y valores entre −1000 y 1000. Imprime el índice desde cero de la columna de mayor suma; en empate, el menor. Para filas -1 2 0 y 4 1 3, la respuesta es 0.

Aplicar en problemas

Los problemas siguientes requieren traducir un enunciado y pueden combinar otras ideas. Su procedencia e idioma no indican un orden obligatorio de dificultad.

Problemas OCI reales, en español (cada nota trae el link a su mirror):

#ProblemaFaseQué practica
1AzulejosRegional 2019los 2 patrones de tablero, costo de cada uno
2Burrito de letrasNacional 2024sopa de letras con filas circulares (índices módulo)
3⭐ Escaleras y SerpientesNacional 2018simular un tablero en zigzag sin perderse

Más aplicaciones (en inglés)

#ProblemaDificultadQué practica
1Beautiful Matrix (263A)★ (800)leer 5×5, ubicar un valor
2George and Accommodation (467A)★ (800)filas como pares de datos
3Magnets (344A)★★ (800)leer por filas, comparar con la anterior
4⭐ Gravity Flip (405A)★★★ (900)una grilla que se resuelve… ordenando (puente al módulo 05)

Un ejemplo para pensar

Las filas de una matriz son {2, 5, 1} y {4, 0, 3}. Queremos imprimir una suma por fila. ¿Qué ocurre si el acumulador se pone en cero antes de ambos ciclos, en vez de al comenzar cada fila?

Compara el código y predice su salida antes de ejecutarlo:

vector<vector<int>> a = {
    {2, 5, 1},
    {4, 0, 3}
};
 
// A: un cero antes de ambos ciclos.
long long sumaA = 0;
for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 3; j++)
        sumaA += a[i][j];
    cout << sumaA << "\n";
}
 
// B: un cero al comenzar cada fila.
for (int i = 0; i < 2; i++) {
    long long sumaB = 0;
    for (int j = 0; j < 3; j++)
        sumaB += a[i][j];
    cout << sumaB << "\n";
}

← 03 - Arreglos y búsqueda lineal · Ruta de Aprendizaje · 05 - Ordenamiento →