Diberi gambar hitam dan putih dengan latar belakang putih dan satu set titik-titik hitam, cat satu set piksel putih merah, sedemikian rupa sehingga ada jalur antara setiap pasangan piksel hitam.
Detail
Path adalah sekumpulan piksel yang terhubung (konektivitas 8-lingkungan). Piksel hitam dapat digunakan sebagai bagian dari jalur. Tujuannya adalah mencoba meminimalkan set piksel merah dalam kondisi di atas, dan menghasilkan gambar yang sesuai.
Anda tidak perlu menemukan solusi optimal.
Solusi terburuk yang sepele dan sekaligus hanya mengecat semua piksel putih merah.
Contoh (Piksel diperbesar untuk visibilitas):
Detail
- Diberikan gambar piksel (dalam format apa pun yang sesuai) mengembalikan gambar lain dengan titik-titik yang terhubung seperti ditentukan di atas, serta bilangan bulat yang menunjukkan berapa banyak piksel merah yang digunakan.
- Skor adalah produk dari (1 + jumlah piksel merah) untuk masing-masing dari 14 testcases.
- Tujuannya adalah memiliki skor terendah.
Testcases
14 testcas ditunjukkan di bawah ini. Program python untuk memverifikasi keterhubungan output dapat ditemukan di sini.
Meta
Terima kasih kepada @Veskah, @Fatalize, @ wizzwizz4, dan @trichoplax untuk berbagai saran.
Jawaban:
C, skor 2.397x10 ^ 38
Manusia ini terlalu lama untuk dilakukan, kemungkinan besar karena pilihan bahasa saya. Saya mendapatkan algoritma yang bekerja cukup awal, tetapi mengalami banyak masalah dengan alokasi memori (tidak bisa hal-hal gratis secara rekursif karena stack overflow, ukuran kebocoran sangat besar).
Masih! Ini mengalahkan entri lain pada setiap test case, dan
bahkan mungkin menjadi optimalmendapatkan solusi yang cukup dekat atau tepat banyak waktu.Bagaimanapun, ini kodenya:
Diuji pada: Arch Linux, GCC 9.1.0,
-O3
Kode ini mengambil input / output dalam file kustom yang saya sebut "cppm" (karena itu seperti versi singkat dari format PPM klasik). Skrip python untuk mengkonversi ke / dari itu di bawah ini:
Penjelasan algoritma
Cara kerja algoritma ini adalah memulai dengan menemukan semua bentuk yang terhubung dalam gambar, termasuk piksel merah. Kemudian mengambil yang pertama dan memperluas pixel satu perbatasan pada suatu waktu sampai bertemu bentuk lain. Kemudian warna semua piksel dari menyentuh ke bentuk asli (menggunakan daftar tertaut itu dibuat sepanjang jalan untuk melacak). Akhirnya, ia mengulangi prosesnya, menemukan semua bentuk baru yang dibuat, sampai hanya ada satu bentuk yang tersisa.
Galeri gambar
Testcase 1, 183 pikselTestcase 2, 140 piksel
Testcase 3, 244 piksel
Testcase 4, 42 piksel
Testcase 5, 622 piksel
Testcase 6, 1 piksel
Testcase 7, 104 piksel
Testcase 8, 2286 piksel
Testcase 9, 22 piksel
Testcase 10, 31581 piksel
Testcase 11, 21421 piksel
Testcase 12, 5465 piksel
Testcase 13, 4679 piksel
Testcase 14, 7362 piksel
sumber
Python, 2.62 * 10 ^ 40
Algoritma ini hanya membanjiri (BFS) pesawat mulai dari bagian hitam gambar, di mana untuk setiap piksel baru kami merekam bagian hitam dari mana ia dibanjiri. Segera setelah kami memiliki dua piksel tetangga dengan bagian hitam berbeda sebagai leluhur, kami pada dasarnya menggabungkan kedua bagian hitam ini dengan menggabungkannya melalui leluhur dua tetangga yang baru saja kami temukan. Secara teori ini bisa diterapkan
O(#pixels)
, tetapi untuk menjaga jumlah kode pada tingkat yang dapat diterima implementasi ini sedikit lebih buruk.Keluaran
Skor
sumber
Python 3:
1.7x10 ^ 421.5x10 ^ 41Menggunakan
Pillow
,numpy
danscipy
.Gambar diasumsikan berada di
images
folder yang berada di direktori yang sama dengan skrip.Penafian : Butuh waktu lama untuk memproses semua gambar.
Kode
Penjelasan
Solusi sepele. Kita mulai dengan mengubah warna semua piksel putih dalam gambar menjadi merah. Dengan melakukan ini, dijamin bahwa semua elemen (semua pulau piksel hitam) terhubung.
Kemudian, kami mengulangi semua piksel dalam gambar mulai dari sudut kiri atas dan bergerak ke kanan dan ke bawah. Untuk setiap piksel merah kami temukan kami mengubah warnanya menjadi putih. Jika setelah perubahan warna ini masih ada hanya satu elemen (sebuah elemen yang sekarang merupakan pulau piksel hitam dan merah), kita membiarkan piksel putih dan beralih ke piksel berikutnya. Namun, jika setelah perubahan warna dari merah ke putih jumlah elemen lebih besar dari satu, kita meninggalkan piksel merah dan beralih ke piksel berikutnya.
Memperbarui
Seperti dapat dilihat (dan diharapkan) koneksi yang diperoleh dengan hanya menggunakan metode ini menunjukkan pola reguler dan dalam beberapa kasus, seperti pada gambar 6 dan 11, ada piksel merah yang tidak perlu.
Pixel merah ekstra ini dapat dengan mudah dihapus dengan mengulangi lagi gambar dan melakukan operasi yang sama seperti yang dijelaskan di atas tetapi dari sudut kanan bawah ke sudut kiri atas. Lulus kedua ini jauh lebih cepat karena jumlah piksel merah yang harus diperiksa.
Hasil
Gambar yang dimodifikasi setelah pass kedua terdaftar dua kali untuk menunjukkan perbedaan.
Jumlah piksel merah: 18825
Jumlah piksel merah: 334
Jumlah piksel merah: 1352
Jumlah piksel merah: 20214
Jumlah piksel merah: 47268
Jumlah piksel merah:
6327Jumlah piksel merah: 17889
Jumlah piksel merah: 259
Jumlah piksel merah: 6746
Jumlah piksel merah: 586
Jumlah piksel merah:
91Jumlah piksel merah: 126
Jumlah piksel merah: 212
Jumlah piksel merah: 683
Perhitungan skor:
(1 + 6746) * (1 + 126) * (1 + 259) * (1 + 17889) * (1 + 334) * (1 + 586) * (1 + 18825) * (1 + 925) * (1 + 9) * (1 +683) * (1 + 1352) * (1 + 20214) * (1 + 212) * (1 + 63) * (1 + 47268) = 1778700054505858720992088713763655500800000 ~ 1.7x10 ^ 42
Perhitungan skor yang diperbarui setelah menambahkan pass kedua:
(1+ 18825) * (1+ 1352) * (1+ 20214) * (1+ 47268) * (1+ 27) * (1+ 17889) * (1+ 6746) * (1+ 5846) * (1+ 586) * (1 + 1) * (1+ 126) * (1+ 212) * (1+ 334) * (1 + 259) * (1 + 683) = 155636254769262638086807762454319856320000 ~ 1.5x10 ^ 41
sumber