Hitung 3BV dari Papan Minesweeper

17

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.

Menghitung 3BV

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)

Papan Minesweeper terpecahkan Diperlukan klik


Diberikan array nilai 2D, 0untuk yang jelas dan 1untuk 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
mbomb007
sumber
Apakah array bilangan apa-apa sebagai input? Setiap kode integer satu baris.
Karl Napf
@KarlNapf No. Input harus dikenali sebagai papan seperti yang ditunjukkan.
mbomb007
Bisakah Anda memberikan lebih banyak case uji, mungkin termasuk input berdasarkan gambar yang ditampilkan, dan mungkin case test dimensi maksimum?
mil

Jawaban:

15

MATLAB, 92 90 86 83 79 74 72 byte

x=input('');I=@(x)~imdilate(x,ones(3));[C,N]=bwlabel(I(x));nnz(I(C)-x)+N

Solusi 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 1dan kemudian terbalik (menggunakan ~) yang mengidentifikasi semua titik yang tidak memiliki tambang sebagai tetangga ( 1) atau melakukan (0 ). Untuk menentukan jumlah wilayah yang terhubung, kami menggunakan bwlabellabel masing-masing wilayah yang terhubung 1. Output pertama adalah matriks label (di 0mana input adalah nol dan nilai apa pun dalam rentang di 1...Nmana ada 1di input di mana Nadalah indeks dari grup yang terhubung yang dimilikinya). Output kedua adalah jumlah wilayah (jumlah klik yang diperlukan untuk membukanya). Hasil dari bwlabelditunjukkan pada gambar di sebelah kiri.

masukkan deskripsi gambar di sini

Kami memperluas output pertama bwlabelmenggunakan imdilate(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.

Suever
sumber
9

Oktaf, 86 , 84 79 66 byte

@(x)nnz(~imdilate(c=imerode(~x,o=ones(3)),o)-x)+max(bwlabel(c)(:))

Solusi ini menciptakan fungsi anonim bernama ansyang kemudian dapat melewati matriks 2D dari 0dan1 ' 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

Suever
sumber
2

MATL, 24 22 21 byte (tidak bersaing)

1 byte disimpan berkat @Luis

4Y6Z+~l2#ZIw7MZ+G+~z+

Cobalah MATL Online

Penjelasan

Sekali lagi, ini mirip dengan jawaban MATLAB dan Oktaf saya untuk pertanyaan ini.

        % Implicitly grab input array
4Y6     % Push the literal [1 1 1; 1 1 1; 1 1 1] to the stack
Z+      % Perform 2D convolution of the input with this array
~       % Negate the result
l2#ZI   % Call bwlabeln which dilates each open region and the second output
        % returns the number of open regions
w       % Flip the top two stack elements
7M      % Push the literal [1 1 1; 1 1 1; 1 1 1] to the stack again
Z+      % Perform 2D convolution
G+      % Explicitly grab the input and add it to the result
~z      % Count the number of 0's in the result (the remaining number of clicks)
+       % Add the total number of remaining clicks to the number of open regions 
Suever
sumber
Mengapa tidak bersaing?
CalculatorFeline
1
@CalculatorFeline Sayangnya bwlabelnfungsi ini diperkenalkan ke MATL setelah tantangan diposting.
Suever