Dengan diberikan dua bentuk yang berdekatan dari area yang sama, tentukan cara optimal untuk membagi bentuk pertama menjadi jumlah minimum segmen yang berdekatan sehingga dapat disusun ulang untuk membentuk bentuk kedua. Dengan kata lain, temukan jumlah minimum segmen yang diperlukan yang dapat membentuk kedua bentuk tersebut.
"Berdampingan" berarti bahwa setiap kotak dalam bentuk dapat dicapai dari kotak lain dengan berjalan melintasi tepi. Bentuk dan segmen diizinkan memiliki lubang.
"Tata Ulang" berarti Anda memindahkan segmen; Anda dapat menerjemahkan, memutar, dan memantulkannya.
Bentuknya terkandung pada kotak; dengan kata lain, setiap bentuk terdiri dari kumpulan kuadrat satuan yang disatukan dengan sudut / tepinya.
Spesifikasi Input
Input akan diberikan dalam beberapa format yang masuk akal - daftar poin, array string yang mewakili setiap kisi, dll. Anda juga dapat mengambil ukuran kisi jika diminta. Grid akan memiliki dimensi yang sama dan dua bentuk dijamin memiliki area yang sama, dan area tersebut akan positif.
Spesifikasi Output
Keluaran seharusnya hanya bilangan bulat positif tunggal. Perhatikan bahwa akan selalu ada jawaban positif karena dalam skenario kasus terburuk, Anda hanya membagi bentuk menjadi N
kotak satuan.
Contohnya
Contoh-contoh disajikan sebagai kotak dengan .
mewakili bagian kosong dan #
mewakili bentuk.
Kasus 1
Memasukkan
.....
.###.
.#.#.
.###.
.....
###..
..#..
..#..
..###
.....
Keluaran
2
Penjelasan
Anda dapat membaginya menjadi dua blok berbentuk L dari 4:
#
###
Kasus 2
Memasukkan
#...
##..
.#..
.##.
.##.
####
....
....
Keluaran
2
Penjelasan
Anda dapat membagi bentuk seperti:
A...
AA..
.A.
.BB.
.AA.
BBAA
....
....
Anda juga bisa:
A...
AA..
.B..
.BB.
.AB.
AABB
....
....
Kasus 3
Memasukkan
#....#
######
.####.
.####.
Keluaran
2
Penjelasan
A....B
AAABBB
.ABBB.
.AAAB.
(Kasing uji ini menunjukkan perlunya memutar / memantulkan bentuk untuk hasil optimal)
Kasus 4
Memasukkan
.###.
..#..
.##..
.##..
Keluaran
2
Penjelasan
Tidak masalah bagaimana Anda memilih blok, memilih 2x1 dari bentuk pertama tentu mencegah dua lainnya dari dikelompokkan bersama; dengan demikian, Anda dapat menggunakan satu 2x1 dan dua 1x1s. Namun, (terima kasih @Jonah), Anda dapat membaginya menjadi bentuk 3-blok L dan satu kotak seperti ini:
.AAB.
..A..
.AA..
.BA..
Jawaban:
Python 3.6 ,
799791 byte7 byte disimpan oleh Jonathan Frech dan motavica
Cobalah online!
Pemakaian
A(s, t)
mengambil dua bentuk di mana setiap bentuk diberikan oleh daftarx, y
posisi kisi.Fungsi pembantu untuk mengonversi representasi grafis ke daftar posisi adalah di bawah ini:
Contoh:
Penjelasan
Algoritma yang digunakan di sini sedikit lebih baik daripada brute force dengan caching sub-bentuk. Untuk bentuk yang diberikan, cache semua cara untuk membagi bentuk itu menjadi dua bentuk yang bersebelahan, saya kemudian menormalkan bentuk-bentuk ini (menggeser koordinat sehingga dimulai pada asal, kemudian menemukan rotasi / refleksi dari itu yang digunakan dalam cache) dan simpan di cache untuk mencari dengan cepat nanti. Semua sub-bentuk kemudian memiliki sub-bentuk di-cache juga sampai sampai ke bentuk blok tunggal.
Sub-bentuk ini dihasilkan dengan mengonversinya menjadi daftar adjacency grafik dan menggunakan BFS untuk menghasilkan semua sub-grafik. Kami kemudian dapat memfilter subgraph ini ke yang simpul yang tidak termasuk adalah komponen yang terhubung. Menentukan apakah grafik terhubung dilakukan dengan BFS lain.
Setelah cache selesai, solusinya ditemukan dengan membandingkan dua bentuk untuk menemukan sub-bentuk yang sama. Setelah memiliki daftar sub-bentuk ini, diperlukan sepasang sub-bentuk yang tersisa setelah menghapus bentuk bersama dan secara rekursif menerapkan algoritma yang sama lagi untuk menemukan jumlah minimum blok yang diperlukan untuk merekonstruksi bentuk. Ini kemudian mengembalikan sub-bentuk dengan minimum semua nilai-nilai itu dan kami memiliki solusi kami.
Saya telah meletakkan versi beranotasi di bawah ini untuk menjelaskan apa yang dilakukan setiap baris.
sumber
if s==t else
mungkin bisa dibalik, memungkinkan penggantian!=
ke^
.if i<len(s)-1else
~>if-~i<len(s)else
.def A(s,t):U(s);U(t);return V(P(s),P(t))
bisa jadilambda s,t:U(s)or U(t)or V(P(s),P(t))
, menghemat tiga byte.s.union(*[g[n]for n in s])
~>s.union(*map(g.get,s))