Misalkan kita memiliki matriks seperti ini:
11111
12221
12321
12221
11111
Matriks ini mewakili medan, dan setiap sel mewakili sebagian medan. Jumlah di setiap sel mewakili waktu bagian medan perlu dibakar sepenuhnya (dalam hitungan menit, jika unit pengukuran diperlukan), sesuai dengan kemampuan terbakarnya . Jika api mulai pada posisi tertentu (sel), sel itu harus benar-benar terbakar sebelum api merambat ke sel-sel yang berdekatan (hanya horisontal dan vertikal, bukan diagonal). Jadi, jika api dimulai pada posisi tengah, api membutuhkan:
11111 11111 11111 11011 10001 00000
12221 3 m. 12221 2 m. 12021 1 m. 11011 1 m. 00000 1 m. 00000
12321 -----> 12021 -----> 10001 -----> 00000 -----> 00000 -----> 00000
12221 12221 12021 11011 00000 00000
11111 11111 11111 11011 10001 00000
Penjelasan:
- Api dimulai pada [2,2] (berbasis 0), yang memiliki waktu bakar 3.
- Setelah 3 menit, [1,2], [2,1], [2,3], [3,2] mulai terbakar.
- Setelah 2 menit, sel-sel itu berakhir terbakar dan merambat ke semua sel yang berdekatan, tetapi [0,2], [2,0], [2,4], [0,4] hanya perlu 1 menit lagi untuk terbakar, jadi
- Setelah 1 menit, sel-sel itu dibakar dan sel merambat ke sel-sel yang berdekatan.
- Setelah 1 menit lagi, sisa sel dari langkah 3 berakhir terbakar dan merambat ke sel-sel yang berdekatan (yang sudah terbakar, sehingga tidak terjadi apa-apa).
- Setelah 1 menit terakhir, api berakhir membakar seluruh medan.
Jadi solusi untuk kasus itu adalah 8 menit. Jika api dimulai di sel paling kiri atas [0,0]:
11111 01111 00111 00011 00001 00000
12221 1 12221 1 02221 1 01221 1 00121 1 00011 1
12321 --> 12321 --> 12321 --> 02321 --> 01321 --> 00321 -->
12221 12221 12221 12221 02221 01221
11111 11111 11111 11111 11111 01111
00000 00000 00000 00000 00000
00000 1 00000 1 00000 1 00000 1 00000
00221 --> 00110 --> 00000 --> 00000 --> 00000
00221 00121 00020 00010 00000
00111 00011 00001 00000 00000
Jadi sekarang total waktu adalah 10 menit.
Tantangan
Diberikan matriks NxM (N> 0, M> 0) dari nilai integer yang mewakili waktu setiap sel perlu dikonsumsi sepenuhnya, tulis program / fungsi terpendek yang mengambil matriks dan sepasang bilangan bulat dengan posisi api dimulai pada , dan mengembalikan / mencetak waktu yang dibutuhkan api untuk sepenuhnya menghabiskan seluruh medan.
- Setiap sel akan memiliki waktu pembakaran positif (bukan nol). Anda tidak dapat mengasumsikan nilai maksimum untuk sel.
- Matriks tidak harus persegi atau simetris.
- Matriks dapat 0-diindeks atau 1-diindeks, seperti yang Anda inginkan.
- Posisi dapat diberikan sebagai parameter tunggal dengan tupel bilangan bulat, dua parameter terpisah dari format beralasan lainnya.
- Dimensi matriks tidak dapat ditentukan sebagai parameter input.
- Anda tidak perlu menampilkan setiap langkah perantara, cukup jumlah waktu yang diminta. Tetapi saya tidak akan mengeluh jika langkah-langkah tersebut divisualisasikan dengan cara apa pun.
Contoh lain:
Fire starts at [1,1] (a '>' represents a minute):
4253 4253 4253 4153 4043 3033 2023 0001 0000
2213 > 2113 > 2013 > 1003 > 0002 > 0001 > 0000 >> 0000 > 0000
1211 1211 1211 1111 1001 0000 0000 0000 0000
Output: 9
Ini adalah kode-golf , jadi semoga program terpendek untuk setiap bahasa menang!
sumber
1
keM*N
Jawaban:
Matlab,
235257190182178 byteInput: Matriks
A
, vektor 1x2 yangp
berisi koordinat awal.Penjelasan:
Alih-alih mensimulasikan penyebaran api, kita juga bisa memahami ini sebagai masalah "temukan jalur terpendek terpanjang". Matriks tersebut dikonversi menjadi grafik terarah tertimbang. Bobot jalur ke satu simpul sesuai dengan waktu untuk membakar simpul tersebut. Misalnya untuk sebuah matriks
kami mendapatkan grafik yang terhubung:
Di mana simpul 1 adalah elemen matriks kiri atas dan simpul 12 elemen kanan bawah. Diberikan koordinat awal
p
, jalur terpendek ke semua node lainnya dihitung. Kemudian panjang jalur terpanjang dari jalur terpendek tersebut + waktu untuk membakar simpul awal sama dengan waktu untuk membakar seluruh matriks.Versi tidak dikoleksi dan dikomentari dengan nilai awal sampel:
sumber
;
setelah setiap baris. Di Matlab, ini mencegah agar hasil setiap perintah ditampilkan di konsol. Saat ini kodenya SANGAT cerewet dan spam konsol. Tapi karena itu bukan keadaan kegagalan yang ketat saya tetap seperti itu. Tapi itu tidak masalah, hanya 4 byteJavaScript (ES6),
156152146144143 byteDisimpan 1 byte berkat Kevin Cruijssen
Implementasi yang agak naif. Mengambil input dalam sintaks currying
(a)(s)
, di mana a adalah 2D-array dan s adalah array dua bilangan bulat [ x, y ] yang mewakili koordinat berbasis 0 dari posisi awal.Diformat dan dikomentari
Uji kasus
Tampilkan cuplikan kode
sumber
==0
bisa bermain golf<1
jika saya tidak salah.undefined<1
salah. Terima kasih!Oktaf, 67 byte
Cobalah online!
Untuk memvisualisasikan hasil antara, Anda dapat Coba ini!
Suatu fungsi yang mengambil sebagai matriks masukan medan
a
dan koordinat awal sebagai matriks 0 & 1 dengan ukuran yang sama dengan medan.Sebenarnya tidak perlu
endfunction
untuk menjalankan contoh di tio itu harus ditambahkan.Penjelasan:
Lakukan pelebaran gambar morfologis berulang kali pada medan dan kurangi area yang terbakar darinya.
Jawaban yang tidak digabungkan:
sumber
n=1
menjadin=0
.MATL ,
2625 byteFormat input adalah:
Input pertama adalah matriks yang digunakan
;
sebagai pemisah baris.Input kedua adalah nomor tunggal yang membahas entri matriks dalam urutan kolom-mayor 1 berbasis (diizinkan oleh tantangan). Misalnya, koordinat kolom-utama dari setiap entri dalam matriks 3 × 4 diberikan oleh
Jadi misalnya koordinat berbasis 1 (2,2) sesuai dengan
5
.Cobalah online! Atau verifikasi semua kasus uji .
Penjelasan
Kode memelihara daftar entri yang terbakar. Pada setiap iterasi, semua entri dalam daftar itu dikurangi. Ketika sebuah entri mencapai nol, entri yang berdekatan ditambahkan ke daftar. Untuk menyimpan byte, entri yang mencapai nol tidak dihapus dari daftar; alih-alih, mereka terus "membakar" dengan nilai negatif. Loop keluar ketika tidak ada entri yang memiliki nilai positif.
Lihat program yang menjalankan langkah demi langkah dengan kode yang sedikit dimodifikasi.
Kode yang dikomentari:
sumber
Python 2 , 170 byte
Cobalah online!
sumber
Python 3 ,
277266 byteCobalah online!
Menentukan fungsi
f
yang mengambil matriks 2D dan tupel poin. Hal pertama fungsi adalah menentukan satu set tupel mengandung nilai tuple awal disahkan pada:p={s}
. Fungsi kemudian melewati setiap tuple titikp
dan mengurangi satu dari matriksm
pada titik itu, kecuali nilainya sudah nol. Kemudian loopm
lagi menemukan semua poin dengan nilai nol dan menambahkan empat tetangga dari titik itu ke setp
. Inilah sebabnya saya memilih untuk menggunakan set, karena set dengan Python tidak mengizinkan nilai duplikat (yang akan mengacaukan pengurangan banyak). Sayangnya, karena pembungkus indeks daftar (misalnyalist[-1] == list[len(list)-1]
:) indeks perlu dibatasi sehingga mereka tidak pergi negatif dan menambahkan koordinat yang salahp
.Tidak ada yang istimewa, masih membiasakan diri bermain golf. Pasti ruang untuk perbaikan di sini, saya akan terus melakukannya.
sumber
APL (Dyalog) ,
936657 byteCobalah online! atau Visualisasikan secara online!
Fungsi ini mengambil matriks medan sebagai argumen kanan dan koordinat (berbasis 1) dari api pertama sebagai argumen kiri. Mengembalikan jumlah menit yang dibutuhkan untuk membakar semuanya.
Pembaruan
Akhirnya menemukan cara untuk menurunkan fungsi penyebaran.
* Menghela nafas * akan jauh lebih mudah jika dunia ini toroidal .
TIO baru saja ditingkatkan ke Dyalog 16.0 , yang berarti sekarang kami memiliki operator stensil baru yang mengkilap
sumber
Python 2 , 268 byte
Cobalah online!
Ulangi secara berulang-ulang seiring waktu langkah-langkah di mana setiap nomor ubin dikurangi jika berbatasan kardinal dengan 0. Algoritma yang sangat mudah, saya percaya, masih bisa digunakan untuk efisiensi boolean ...
* catatan: my 'Coba online!' kode termasuk bonus debug logging di footer. Saya suka melihat perkembangan algoritma.
sumber
Haskell ,
138133 byteCobalah online!
Asumsikan input adalah daftar ((x, y), sel). Tidak Terkumpul:
sumber