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
vectordevectores. - 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 0a[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.
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:
| i | j | a[i][j] | suma de la fila tras sumar |
|---|---|---|---|
| 0 | 0 | 2 | 2 |
| 0 | 1 | 5 | 7 |
| 0 | 2 | 1 | 8 |
| 1 | 0 | 4 | 4 (se reinició a cero) |
| 1 | 1 | 0 | 4 |
| 1 | 2 | 3 | 7 |
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.
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:
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)
- Suma de la diagonal principal de una matriz cuadrada (
a[i][i]). - ¿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.
Idea para comprobar tu solución
Reinicia el acumulador al comenzar cada fila. Como variación, imprime sumas por columna: 6,5,4.
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.
Una pista, si la necesitas
Las tres columnas del ejemplo suman 3. Decide cómo conservar el primer empate.
Contrastar el razonamiento
Puedes acumular por columna mientras lees por filas. Necesitas m acumuladores, no conservar n×m valores. Inicializa la mejor columna en 0 y cámbiala solo ante una suma estrictamente mayor.
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):
| # | Problema | Fase | Qué practica |
|---|---|---|---|
| 1 | Azulejos | Regional 2019 | los 2 patrones de tablero, costo de cada uno |
| 2 | Burrito de letras | Nacional 2024 | sopa de letras con filas circulares (índices módulo) |
| 3 | ⭐ Escaleras y Serpientes | Nacional 2018 | simular un tablero en zigzag sin perderse |
Más aplicaciones (en inglés)
| # | Problema | Dificultad | Qué practica |
|---|---|---|---|
| 1 | Beautiful Matrix (263A) | ★ (800) | leer 5×5, ubicar un valor |
| 2 | George and Accommodation (467A) | ★ (800) | filas como pares de datos |
| 3 | Magnets (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";
}Qué parte de la matriz resume el acumulador
Las sumas buscadas son 8 y 7. Si no se reinicia entre filas, imprime 8 y luego 15: la segunda respuesta incluye también la primera fila. Reiniciarlo dentro del ciclo de filas, antes del de columnas, hace que cada suma corresponda exactamente a una fila. Para sumar toda la matriz, en cambio, sí tendría sentido inicializarlo una sola vez.
← 03 - Arreglos y búsqueda lineal · Ruta de Aprendizaje · 05 - Ordenamiento →