Herausforderung
Bei einem solchen Raster
1 2 3 4 5 6 7 8
1 . . . . . . . .
2 . # . . . # . .
3 . . . . . . . .
4 . . . . . . . .
5 . . . . . . . .
6 . . # . . . . .
7 . . . . . . . .
8 . . . . . . . .
Schreiben Sie einen Code, der die Größe des größten Quadrats ohne '#' bestimmen kann. (Die Antwort auf diese Eingabe lautet 5x5, da das 5x5-Raster unten rechts das größtmögliche Quadrat ist.)
Das Quadrat muss Seiten parallel zur x- und y-Achse haben.
Als kleine Details: Das ursprüngliche Gitter ist immer ein Quadrat und seine Seitenlänge wird Ihnen gegeben. Die Koordinaten der '#' Symbole werden Ihnen ebenfalls gegeben.
Eingabedetails
Erste Zeile: N (1 <= N <= 1000), die Seitenlänge des quadratischen Gitters und T (1 <= T <= 10.000) die Anzahl der '#' - Zeichen.
Nächste T-Linien: Die Koordinaten der einzelnen T #
Testfälle
Eingabe 1:
8 3
2 2
2 6
6 3
Ergebnis 1: 5
================
Eingabe 2:
8 4
1 1
1 8
8 1
8 8
Ergebnis Nr. 2: 6
================
Eingabe 3:
5 1
3 3
Ergebnis # 3: 2
Dies ist ein am schnellsten Code Problem, so der schnellste Code auf der getesteten rextester Compiler gewinnt.
Habe Spaß!
quelle
fastest-code
1000x1000 ist es allerdings zu kleinAntworten:
Node.js
Nimmt die Eingabe als (w, l) an , wobei w die Breite und l ein Array von Koordinaten [x, y] ist . (Dies kann geändert werden, wenn das Eingabeformat wirklich so streng ist wie beschrieben.) Funktioniert in O (w²) .
Probieren Sie es online aus!
quelle
console.log(f( 1000, [...Array(10000)].map(_=>[Math.random()*1000+1|0,Math.random()*1000+1|0]) ));
kostet 114ms, obwohl es die geringe Effizienz der Sprache sein könnteC (gcc)
Kein ausgefallener Algorithmus hier, nur fast Bruteforce ... aber hey, C ist schnell.
Eingabe: Nimmt Eingaben von stdin entgegen .
Ausgabe: Schreibt die Ausgabe in stdout .
Probieren Sie es online aus!
quelle