Tantangan
Diberi kotak seperti ini,
1 2 3 4 5 6 7 8
1 . . . . . . . .
2 . # . . . # . .
3 . . . . . . . .
4 . . . . . . . .
5 . . . . . . . .
6 . . # . . . . .
7 . . . . . . . .
8 . . . . . . . .
tulis sepotong kode yang dapat menentukan ukuran persegi terbesar yang tidak termasuk '#'. (Jawaban untuk input ini adalah 5x5 karena kisi kanan bawah 5x5 adalah kuadrat terbesar yang mungkin).
Kuadrat harus memiliki sisi yang sejajar dengan sumbu x dan y.
Sebagai beberapa detail kecil: kisi asli selalu berbentuk bujur sangkar dan panjang sisinya diberikan kepada Anda. Koordinat simbol '#' juga diberikan kepada Anda.
Detail Input
Baris pertama: N (1 <= N <= 1000), panjang sisi kotak persegi, dan T (1 <= T <= 10.000) jumlah tanda '#'.
Next T Lines: Koordinat masing-masing T #
Uji Kasus
Input # 1:
8 3
2 2
2 6
6 3
Hasil # 1: 5
================
Input # 2:
8 4
1 1
1 8
8 1
8 8
Hasil # 2: 6
================
Input # 3:
5 1
3 3
Hasil # 3: 2
Ini adalah masalah kode tercepat , sehingga kode tercepat yang diuji pada kompiler rextester menang.
Selamat bersenang-senang!
sumber
fastest-code
1000x1000 terlalu kecil,Jawaban:
Node.js
Mengambil input sebagai (w, l) , di mana w adalah lebarnya dan l adalah array dari koordinat [x, y] . (Ini dapat diubah jika format input benar-benar seketat yang dijelaskan.) Bekerja dalam O (w²) .
Cobalah online!
sumber
console.log(f( 1000, [...Array(10000)].map(_=>[Math.random()*1000+1|0,Math.random()*1000+1|0]) ));
biaya 114ms, meskipun mungkin itu adalah efisiensi bahasa yang rendahC (gcc)
Tidak ada algoritma mewah di sini, hanya hampir-bruteforce ... tapi hei, C cepat.
Input: Mengambil input dari stdin .
Output: Menulis output ke stdout .
Cobalah online!
sumber