The 3BV dari Minesweeper papan mewakili jumlah minimum klik kiri diperlukan untuk memecahkan papan jika Anda sudah tahu solusinya. Itu adalah singkatan dari "Nilai Benchmark Dewan Bechtel". Inilah situsnya yang menjelaskannya.
Di bawah ini adalah papan Minesweeper yang terpecahkan. Bendera menunjukkan ranjau; ubin tanpa tambang menunjukkan jumlah tambang yang berdekatan, termasuk diagonal, kecuali bahwa ubin yang seharusnya memiliki "0" dibiarkan kosong. Gambar menunjukkan ubin mana yang perlu diklik untuk menyelesaikan papan.
Klik yang dihitung ke 3BV adalah:
- Satu untuk setiap area genteng kosong yang diisi banjir (berdekatan dengan nol tambang) dan tetangganya yang tidak kosong.
- Satu untuk setiap ubin non-tambang lainnya.
Contoh Lain (3BV = 39)
Diberikan array nilai 2D, 0
untuk yang jelas dan 1
untuk tambang (atau boolean), kembalikan 3BV .
Dimensi dewan setidaknya 8x8, dan paling banyak 24x30, inklusif. Program Anda harus menangani semua papan yang mungkin, bukan hanya contoh.
Catatan: Papan tidak akan pernah hanya berisi ranjau.
Contoh I / O:
[[0,0,0,0,0,0,0,0],
[0,0,0,1,0,0,0,0],
[0,0,0,1,0,0,1,0],
[0,1,0,0,1,0,0,0],
[0,0,1,0,0,0,0,1],
[0,0,0,1,0,0,0,0],
[0,0,0,0,0,0,1,0],
[0,0,0,0,0,0,0,1]]
23
[[0,0,1,0,0,0,1,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0],
[0,0,0,0,0,1,1,1,0,0,1,0,0,0,0,0,0,1,0,0,1,0,1,1,0,0,0,0,0,0],
[0,1,0,0,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,1,1,0,0,0,1,0,1,0,1,0],
[0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,0,0,0],
[0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,1,1,0,1],
[0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,1,1],
[0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0],
[0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0],
[0,0,1,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0],
[1,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0,1,1],
[0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,1,1,0,1,1,0,0,0,0,1,1,0,0],
[0,0,0,0,0,1,0,1,1,0,0,0,0,0,0,1,0,1,1,0,0,0,1,0,0,0,1,1,0,0],
[0,1,1,1,0,0,0,0,0,1,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0],
[0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,1,0,0,0],
[0,0,1,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,1,0,0,0,0,0,0,0]]
187
sumber
Jawaban:
MATLAB,
92908683797472 byteSolusi ini menerima input dalam bentuk matriks 2D 0 dan 1 dan akan menampilkan nilai 3BV untuk input yang disediakan.
Ini demo yang sedikit dimodifikasi dalam Oktaf bagi Anda tanpa MATLAB.
Penjelasan
Matriks input dilebarkan menggunakan matriks 3 x 3
1
dan kemudian terbalik (menggunakan~
) yang mengidentifikasi semua titik yang tidak memiliki tambang sebagai tetangga (1
) atau melakukan (0
). Untuk menentukan jumlah wilayah yang terhubung, kami menggunakanbwlabel
label masing-masing wilayah yang terhubung1
. Output pertama adalah matriks label (di0
mana input adalah nol dan nilai apa pun dalam rentang di1...N
mana ada1
di input di manaN
adalah indeks dari grup yang terhubung yang dimilikinya). Output kedua adalah jumlah wilayah (jumlah klik yang diperlukan untuk membukanya). Hasil daribwlabel
ditunjukkan pada gambar di sebelah kiri.Kami memperluas output pertama
bwlabel
menggunakanimdilate
(semua non-nol diperluas) menggunakan matriks 3 x 31
. Hasilnya ditunjukkan pada gambar di tengah.Untuk menentukan klik yang tersisa, kami kemudian menghitung kotak yang tidak ada di wilayah yang diperluas ini (
~imdilate()
) dan bukan tambang (-x
) (kotak putih di gambar di sebelah kanan) dan menambahkan ini ke jumlah total wilayah terbuka (jumlah warna berbeda pada gambar di sebelah kiri) untuk mendapatkan 3BV.sumber
Oktaf,
86,847966 byteSolusi ini menciptakan fungsi anonim bernama
ans
yang kemudian dapat melewati matriks 2D dari0
dan1
' s. Logikanya sama dengan jawaban MATLAB saya tetapi menggunakan beberapa trik yang ditawarkan Octave untuk menghemat ruang.Solusi ini mensyaratkan bahwa
image
paket diinstal.Demo di sini
sumber
MATL,
242221 byte (tidak bersaing)1 byte disimpan berkat @Luis
Cobalah MATL Online
Penjelasan
Sekali lagi, ini mirip dengan jawaban MATLAB dan Oktaf saya untuk pertanyaan ini.
sumber
bwlabeln
fungsi ini diperkenalkan ke MATL setelah tantangan diposting.