Największy kwadrat na siatce [zamknięty]

10

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 problemem, więc najszybszy kod testowany na rextester wygrywa kompilatora.

Baw się dobrze!

NL628
źródło
1
Związane .
user202729
3
Jednak fastest-code1000x1000 jest za małe
l4m2
1
Ale rextester nie obsługuje Jelly ani Hexagony.
user202729
6
Jak rextester jest w stanie, czy mogę polecić wypróbowanie go online ? Zawiera wiele innych języków i jest prowadzony przez społeczność.
ATaco
1
„wygrywa najszybszy kod przetestowany na kompilatorze rextestera” - najszybszy na jakim wejściu?
Nathaniel

Odpowiedzi:

1

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²) .

f = (w, l) => {
  var x, y,
      W = w * w,
      a = new Uint16Array(W),
      best = 0;

  l.forEach(([x, y]) => a[(y - 1) * w + x - 1] = 1);

  for(y = w; y < W; y += w) {
    for(x = y + 1; x < y + w; x++) {
      if(a[x]) {
        a[x] = 0;
      }
      else {
        best = Math.max(
          best,
          a[x] = Math.min(a[x - 1], a[x - w], a[x - w - 1]) + 1
        );
      }
    }
  }

  return best;
}

Wypróbuj online!

Arnauld
ź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ęzyka
l4m2
To bardziej jak 8ms wewnątrz f () po kompilacji JIT. (Ale tak ... odpowiedzi nie będą oceniane w ten sposób.)
Arnauld
Wątpię, żeby OP dodał bardziej obiektywne kryteria wygranej ...
user202729
1

C (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 .

#include <stdio.h>
#include <stdint.h>

int main(void) {
    uint_fast16_t n, t, i, j, h, x, y, flag, biggest = 0;
    scanf("%hi %hi", &n, &t);
    uint_fast8_t m[n][n];
    for (uint_fast16_t c = 0; c < t; ++c) {
        scanf("%hi %hi", &i, &j);
        m[i-1][j-1] = '#';
    }
    for (i = 0; i < n - 1; ++i) {
        for (j = 0; j < n - 1; ++j) {
            flag = 1;
            for (h = 1; flag && i + h < n + 1 && j + h < n + 1; ++h) {
                for (y = i; flag && y < i + h; ++y) {
                    for (x = j; flag && x < j + h; ++x) {
                        if (m[y][x] == '#') flag = 0;
                    }
                }
                if (flag && h > biggest) biggest = h;
            }
        }
    }
    printf("%d", biggest);
}

Wypróbuj online!

Marco
źródło