Kepulauan Sepi

10

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.

Stewie Griffin
sumber
Terkait .
Stewie Griffin
Sialan, Stewie, sekarang aku punya "Jack Sparrow" terjebak di kepalaku lagi!
Shaggy
Masalah ini setara dengan masalah penutup verteks pada grafik bipartit, dan menurut Wikipedia dapat diselesaikan dalam waktu polinomial.
user202729
Saya berubah pikiran ... mungkin tertimbang. Pokoknya untuk matriks persegi cukup besar itu (semoga) setara. Jadi, jika algoritme Anda "terlalu sederhana", berhati-hatilah .
user202729
Saya pikir saya memiliki algoritma waktu polinomial.
user202729

Jawaban:

2

Jelly , 37 byte

ṫƤ-S€ZƊ⁺FỊẠ
Z_,,WƲ€ŒpẎ€Ʋ⁺€ẎLÞFL$ÞṚÇÞṪ

Cobalah online!

Fungsi mengembalikan array bilangan bulat 2D. Perhatikan bahwa secara alami dalam daftar singleton Jelly ditampilkan sebagai nilainya sehingga Gdigunakan untuk memformat output.


  • Tautan 1: Kembali (validitas).
  • Tautan 2: Program utama.

Program ini berjalan dalam waktu eksponensial, tetapi sejauh ini saya tidak bisa memikirkan algoritma waktu polinomial. Menggunakan Ƥfungsi dyadic, fitur itu mengatasi tantangan.

pengguna202729
sumber
2

Python 2 , 374 346 340 339 323 317 byte

R=range;L=len
def f(a):
 w,h=L(a[0]),L(a);W=[]
 for i in R(2**w):
	A=zip(*a)
	for c in R(w):A[-c:-c]=[[0]*h]*(i&1<<c>0)
	for j in R(2**h):
	 B=zip(*A);x=L(B[0])
	 for r in R(h):B[-r:-r]=[(0,)*x]*(j&1<<r>0)
	 y=L(B);W+=[(w*h-x*y,x,B)]*all(sum(B[i][j:j+2]+B[i+1][j:j+2])<2for i in R(y-1)for j in R(x))
 return max(W)[2]

Cobalah online!

TFeld
sumber
Saya pikir yang pertama [:]dapat dihapus tanpa mempengaruhi output.
user202729
@ user202729, Terima kasih, saya pikir itu bisa. Sementara itu saya telah mengubahnya :)
TFeld