Todos los desafíos
Difícil 1 resuelto 100.0% de aceptación

Corta un rectángulo en cuadrados

Encuentra el menor número de cortes rectos necesarios para obtener solo cuadrados.

Lo que aprenderás

  • Definir una tabla DP por ancho y alto
  • Probar cada corte horizontal y vertical
  • Reutilizar resultados de rectángulos más pequeños

Problema

Ver original (inglés)

En cada movimiento, elige un rectángulo y córtalo completamente, en línea recta y paralelo a uno de sus lados, dividiéndolo en dos rectángulos con lados de longitud entera positiva. Continúa hasta que cada pieza sea un cuadrado. Los cuadrados pueden ser de diferentes tamaños. Cuenta los cortes, no las piezas.

Implementa rectangle_cutting(height, width).

Entrada

height: La altura inicial del rectángulo.

width: El ancho inicial del rectángulo.

Salida

Devuelve el número mínimo de cortes.

Restricciones

1 ≤ height, width ≤ 500. Rotar el rectángulo no cambia la respuesta.

Ejemplos

Ejemplo 1
Entrada:
height = 2
width = 3

Salida esperada:
expected = 2
Entrada:
long long height = 2;
long long width = 3;

Salida esperada:
long long expected = 2;
Entrada:
long height = 2;
long width = 3;

Salida esperada:
long expected = 2;

Explicación

Corta un cuadrado de 2 × 2, dejando un rectángulo de 2 × 1. Un corte más divide el resto en dos cuadrados de 1 unidad.

Ejemplo 2
Entrada:
height = 4
width = 4

Salida esperada:
expected = 0
Entrada:
long long height = 4;
long long width = 4;

Salida esperada:
long long expected = 0;
Entrada:
long height = 4;
long width = 4;

Salida esperada:
long expected = 0;

Explicación

El rectángulo inicial ya es un cuadrado.

Cómo abordarlo

Inténtalo primero por tu cuenta y luego abre las pistas una a una.

Pista 1

Un rectángulo se puede resolver dividiéndolo en dos rectángulos más pequeños y combinando sus mejores respuestas.

Pista 2

Prueba cada corte horizontal y vertical posible para encontrar el mínimo.

Pista 3

La memoización o una tabla ayudan porque muchos subrectángulos se repiten.

Complejidad esperada

tiempo O(h*w*(h+w)), espacio extra O(h*w)

Referencias

Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

# Programador Lenguaje Tiempo Memoria Revisión de IA Solución
1 ННикита Python 954 ms - 4/5 Ver código

Aprende de otros

Soluciones de la comunidad

Alerta de spoiler: 1 solución completa abajo Intenta resolverlo tú mismo primero. Igual puedes ver el código de otros desarrolladores y las reseñas de IA. Inicia sesión y resuelve el reto para unirte a la discusión.