Desafío
Dada una cuadrícula como esta,
1 2 3 4 5 6 7 8
1 . . . . . . . .
2 . # . . . # . .
3 . . . . . . . .
4 . . . . . . . .
5 . . . . . . . .
6 . . # . . . . .
7 . . . . . . . .
8 . . . . . . . .
escriba un fragmento de código que pueda determinar el tamaño del cuadrado más grande que no incluye un '#'. (La respuesta a esta entrada es 5x5 ya que la cuadrícula inferior derecha de 5x5 es el cuadrado más grande posible).
El cuadrado debe tener lados paralelos a los ejes x e y.
Como algunos pequeños detalles: la cuadrícula original siempre es un cuadrado y se le da su longitud lateral. También se le dan las coordenadas de los símbolos '#'.
Detalles de entrada
Primera línea: N (1 <= N <= 1000), la longitud lateral de la cuadrícula cuadrada y T (1 <= T <= 10,000) el número de signos '#'.
Próximas líneas T: las coordenadas de cada una de las T #
Casos de prueba
Entrada # 1:
8 3
2 2
2 6
6 3
Resultado 1: 5
================
Entrada # 2:
8 4
1 1
1 8
8 1
8 8
Resultado 2: 6
================
Entrada # 3:
5 1
3 3
Resultado 3: 2
Este es un problema de código más rápido , por lo que gana el código más rápido probado en el compilador rextester .
¡Que te diviertas!
fuente
fastest-code
embargo, para 1000x1000 es demasiado pequeñoRespuestas:
Node.js
Toma la entrada como (w, l) , donde w es el ancho y l es una matriz de coordenadas [x, y] . (Esto puede cambiarse si el formato de entrada es realmente tan estricto como se describe). Funciona en O (w²) .
Pruébalo en línea!
fuente
console.log(f( 1000, [...Array(10000)].map(_=>[Math.random()*1000+1|0,Math.random()*1000+1|0]) ));
costó 114ms, aunque podría ser la baja eficiencia del lenguajeC (gcc)
No hay un algoritmo sofisticado aquí, solo fuerza bruta ... pero bueno, C es rápido.
Entrada: toma la entrada de stdin .
Salida: escribe la salida en stdout .
Pruébalo en línea!
fuente