Memasukkan:
Array 2D berisi dua nilai berbeda (opsional). Saya akan menggunakan 0 dan 1 saat menjelaskan aturan. Format input tentu saja fleksibel.
Tantangan:
Nol adalah air, dan itu adalah pulau. Untuk memastikan kesepian, tugas Anda adalah mengelilingi semua pulau dengan air dengan memasukkan baris dan kolom nol. Anda tidak ingin membuang-buang air, jadi Anda harus meminimalkan jumlah air yang ditambahkan. Jika ada lebih dari satu solusi yang membutuhkan jumlah air yang sama ditambahkan, maka Anda harus menambahkan kolom air, bukan baris. Saya akan menunjukkan ini dalam kasus uji.
Keluaran:
Array 2D baru yang dimodifikasi. Format output tentu saja fleksibel.
Kasus uji:
Input dan output dipisahkan oleh tanda hubung. Angka nol yang ditambahkan ditampilkan dalam huruf tebal. Gunakan salah satu jawaban di sini jika Anda ingin mengonversi kasus uji ke format yang lebih nyaman.
1
---
1
1 1
---
1 0 1
1 1
1 1
---
1 0 1
0 0 0
1 0 1
1 0
0 1
---
1 0 0
0 0 1
Perhatikan bahwa kami menambahkan kolom nol, bukan deretan nol. Ini karena jumlah nol yang diperlukan sama, dan kolom harus lebih disukai.
1 0 0 0 1
0 1 0 1 0
0 0 1 0 0
0 1 0 1 0
---
1 0 0 0 1
0 0 0 0 0
0 1 0 1 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 1 0 1 0
Perhatikan bahwa kami menambahkan baris, bukan kolom, karena itu membutuhkan jumlah nol ekstra paling sedikit.
0 0 1 0 0
0 1 1 1 0
---
0 0 0 1 0 0 0
0 0 0 0 0 0 0
0 1 0 1 0 1 0
Ini membutuhkan kolom dan baris.
0 0 1 0 0
0 1 0 1 0
---
0 0 0 1 0 0 0
0 1 0 0 0 1 0
Lebih baik menambahkan dua kolom daripada satu baris, karena membutuhkan lebih sedikit air.
0 0
1 0
0 1
1 0
0 0
---
0 0
1 0
0 0
0 1
0 0
1 0
0 0
Lebih baik menambahkan dua baris dari satu kolom, karena itu membutuhkan lebih sedikit air.
sumber
Jawaban:
Jelly , 37 byte
Cobalah online!
Fungsi mengembalikan array bilangan bulat 2D. Perhatikan bahwa secara alami dalam daftar singleton Jelly ditampilkan sebagai nilainya sehingga
G
digunakan untuk memformat output.Program ini berjalan dalam waktu eksponensial, tetapi sejauh ini saya tidak bisa memikirkan algoritma waktu polinomial. Menggunakan
Ƥ
fungsi dyadic, fitur itu mengatasi tantangan.sumber
Python 2 ,
374346340339323317 byteCobalah online!
sumber
[:]
dapat dihapus tanpa mempengaruhi output.