Difícil · simulación
Recorrido en espiral
Pela la cuadrícula como una cebolla: escribe la fila superior, luego la columna derecha, luego la inferior al revés, luego la izquierda hacia arriba — y antes de cada una de las dos últimas, pregúntate si queda algo que pelar. Toda la dificultad está en esa pregunta.
En una fraseMantén <code>top/bottom/left/right</code>; barre la fila superior, la columna derecha, luego la inferior al revés y la izquierda hacia arriba — pero solo <em>si</em> aún quedan filas y columnas.
El problema
Entrada: La primera línea trae n y m (1 ≤ n, m ≤ 10). Luego n líneas de m enteros (−100 a 100).
Salida: El recorrido en espiral empezando en la esquina superior izquierda hacia la derecha, valores separados por un espacio en una sola línea.
Ejemplos:
| Entrada | Salida |
|---|---|
3 3 | 1 2 3 6 9 8 7 4 5 |
1 4 | 1 2 3 4 |
El ejemplo de una sola fila está ahí a propósito: tras barrer la fila superior, top sobrepasa bottom, así que el barrido de la fila inferior debe saltarse por completo — o la fila se escribiría dos veces. El segundo ejemplo del juez es el detector de trampas.
Tu solución
Entrada personalizada para «Ejecutar mi entrada»
La corrección corre en tu navegador contra pruebas ocultas. Un bucle infinito se corta a los 3 segundos — aun así, asegúrate de que todo bucle tenga salida. Tu código se guarda solo mientras escribes.
¿Atascado? Pistas
Pista 1 — Una vuelta = cuatro barridos
Fila superior izquierda→derecha, columna derecha arriba→abajo, fila inferior derecha→izquierda, columna izquierda abajo→arriba. Tras cada barrido, encoge el borde correspondiente: top++, right--, bottom--, left++. Repite mientras top <= bottom && left <= right — cuando los rangos se cruzan, la cebolla está pelada.
Pista 2 — Las dos re-comprobaciones son el problema
Tras top++, la fila inferior puede ya no existir (cuadrículas de una fila, o espirales que terminan en una franja horizontal) — resguarda el barrido inferior con if (top <= bottom). Simétricamente, el barrido izquierdo con if (left <= right). Sin estas dos, los tests de una fila y una columna fallan por visitas duplicadas.
Pista 3 — Sigue a mano una cuadrícula no cuadrada
Las cuadrículas cuadradas esconden los bugs de borde de maravilla — todo cierra fino. Una de 2×3 y una de 3×2 seguidas una vez en papel exponen cualquier error en los cuatro bucles. Si tu espiral funciona en cuadrados y falla en el juez, este es el motivo.
Solución (¡inténtalo primero!)
#include <iostream>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
int a[12][12];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> a[i][j];
int top = 0, bottom = n - 1, left = 0, right = m - 1;
bool first = true;
while (top <= bottom && left <= right) {
for (int j = left; j <= right; j++) {
if (!first) cout << " ";
cout << a[top][j]; first = false;
}
top++;
for (int i = top; i <= bottom; i++) {
if (!first) cout << " ";
cout << a[i][right]; first = false;
}
right--;
if (top <= bottom) {
for (int j = right; j >= left; j--) {
if (!first) cout << " ";
cout << a[bottom][j]; first = false;
}
bottom--;
}
if (left <= right) {
for (int i = bottom; i >= top; i--) {
if (!first) cout << " ";
cout << a[i][left]; first = false;
}
left++;
}
}
cout << endl;
return 0;
}La simulación con bordes que se encogen es el esqueleto detrás de los problemas de rotación, recorrido y relleno por inundación. Compárala con la otra forma de tratar cuadrículas — reindexar filas enteras en Transponer una matriz — y nota la diferencia: la transposición mueve índices, la espiral mueve *bordes*. La siguiente habilidad tras ambas es preguntar por rectángulos: Sumas por rangos 2D.
Análisis profundo
Por qué funciona
Cuatro bordes (top/bottom/left/right) definen el anillo sin visitar; cada vuelta escribe una revolución completa y encoge un borde por barrido. Las dos re-comprobaciones tras encoger existen porque un anillo puede quedar de una sola fila o columna — escribir su parte inferior y luego la izquierda recorrería las mismas celdas dos veces.
El coste
O(n·m): cada celda se escribe exactamente una vez y la aritmética de bordes es constante por barrido. Espacio O(1) además de la cuadrícula.
Dónde falla
- Perder la guarda
if (top <= bottom)antes del barrido inferior (o la de la izquierda): las cuadrículas de una fila o columna se escriben dos veces — los tests no cuadrados del juez existen justo para esto. - Barrer la fila inferior izquierda→derecha o la columna izquierda arriba→abajo: la espiral alterna el sentido, y los bucles invertidos (
j--,i--) son obligatorios en la segunda mitad de cada vuelta. - Confiar en los tests cuadrados: un 3×3 cierra fino y esconde todos los bugs. Solo un 2×3 y un 3×2 seguidos a mano exponen los cuatro límites de bucle.
Siguiente paso
Manejo de cuadrículas hasta ahora: reindexar filas en Transponer una matriz, combinar cuadrículas en Multiplicación de matrices, caminar bordes aquí. Luego, preguntar por rectángulos: Sumas por rangos 2D.
Dos cosas para recordar
- Una vuelta = cuatro barridos; tras cada uno, encoge ese borde.
- Las dos re-comprobaciones (¿quedan filas? ¿quedan columnas?) son lo que compran los tests no cuadrados.
🐞 Esta versión falla: ábrela y pruébala
Sin re-comprobaciones antes de los barridos inferior e izquierdo — las filas únicas se escriben dos veces
#include <iostream>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
int a[12][12];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> a[i][j];
int top = 0, bottom = n - 1, left = 0, right = m - 1;
bool first = true;
while (top <= bottom && left <= right) {
for (int j = left; j <= right; j++) { if (!first) cout << " "; cout << a[top][j]; first = false; }
top++;
for (int i = top; i <= bottom; i++) { if (!first) cout << " "; cout << a[i][right]; first = false; }
right--;
for (int j = right; j >= left; j--) { if (!first) cout << " "; cout << a[bottom][j]; first = false; } // bug: no guard
bottom--;
for (int i = bottom; i >= top; i--) { if (!first) cout << " "; cout << a[i][left]; first = false; } // bug: no guard
left++;
}
cout << endl;
return 0;
}