Wyzwanie
Biorąc pod uwagę taką siatkę,
1 2 3 4 5 6 7 8
1 . . . . . . . .
2 . # . . . # . .
3 . . . . . . . .
4 . . . . . . . .
5 . . . . . . . .
6 . . # . . . . .
7 . . . . . . . .
8 . . . . . . . .
napisz fragment kodu, który może określić rozmiar największego kwadratu, który nie zawiera znaku „#”. (Odpowiedź na to wejście to 5x5, ponieważ prawa dolna siatka 5x5 jest największym możliwym kwadratem).
Kwadrat musi mieć boki równoległe do osi xiy.
Jako kilka drobnych szczegółów: oryginalna siatka jest zawsze kwadratem, a jej długość boku jest podana. Współrzędne symboli „#” są również podane.
Dane wejściowe
Pierwszy wiersz: N (1 <= N <= 1000), długość boku kwadratowej siatki, a T (1 <= T <= 10 000) liczba znaków „#”.
Następne linie T: Współrzędne każdego z T #
Przypadki testowe
Wejście nr 1:
8 3
2 2
2 6
6 3
Wynik # 1: 5
================
Wejście nr 2:
8 4
1 1
1 8
8 1
8 8
Wynik # 2: 6
================
Wejście nr 3:
5 1
3 3
Wynik # 3: 2
Jest to najszybciej kod problemem, więc najszybszy kod testowany na rextester wygrywa kompilatora.
Baw się dobrze!
źródło
fastest-code
1000x1000 jest za małeOdpowiedzi:
Node.js
Pobiera dane wejściowe jako (w, l) , gdzie w jest szerokością, a l jest tablicą współrzędnych [x, y] . (Można to zmienić, jeśli format wejściowy jest tak ścisły, jak opisano.) Działa w O (w²) .
Wypróbuj online!
źródło
console.log(f( 1000, [...Array(10000)].map(_=>[Math.random()*1000+1|0,Math.random()*1000+1|0]) ));
kosztuje 114ms, choć może to być niska wydajność tego językaC (gcc)
Nie ma tutaj żadnego wymyślnego algorytmu, prawie brutalna siła ... ale hej, C jest szybki.
Wejście: pobiera dane wejściowe ze standardowego wejścia .
Wyjście: Zapisuje wyjście na standardowe wyjście .
Wypróbuj online!
źródło