Tantangan
Tulis program / fungsi yang menerima "gambar" dan mengeluarkan labirin gambar dari gambar itu.
Memasukkan
Program Anda harus menerima dua argumen:
- Saya, gambar untuk membentuk labirin dari
- S, sebuah boolean yang menentukan apakah akan menampilkan solusi ke labirin
Saya diberikan dalam bentuk berikut:
.......
.#####.
.#####.
#######
.#####.
.#####.
.......
di mana #
sel adalah untuk dimasukkan dalam jalur solusi dan .
sel adalah untuk dikecualikan. Anda dapat menukar baris .
's, #
dan baris baru dengan karakter apa pun yang Anda pilih asalkan berbeda satu sama lain. Atau, Anda dapat menerima bitmap aktual dari gambar input.
Keluaran
Labirin Anda yang dihasilkan harus dalam bentuk berikut:
###############
# #
# ### ####### #
# #.........# #
# #.#######.# #
# #.#.......# #
###.#.#########
....#.#........
#####.#.#######
# ...#..... #
# #.#######.# #
# #.........# #
# ####### ### #
# # # #
###############
di mana #
dinding menunjukkan, .
menunjukkan bagian dari jalan yang merupakan bagian dari solusi, dan ruang adalah jalan yang dikeluarkan dari solusi. Itu .
dapat diganti dengan spasi jika S salah. Sekali lagi, karakter dapat ditukar dengan karakter lain yang Anda pilih atau Anda dapat menampilkan bitmap sebenarnya dari labirin dengan solusi yang disorot.
detil tambahan
- Jalan harus selebar satu sel (tidak dapat memiliki kolam kosong ruang kosong menjadi jalan)
- Labirin tidak boleh mengandung loop apa pun
- Labirin harus terhubung sepenuhnya (semua sel harus dapat dijangkau dari pintu masuk / keluar)
- Labirin harus dikelilingi oleh dinding (kecuali pintu masuk / keluar)
- Jalur solusi tidak boleh menyertakan jalan buntu
- Harus ada tepat 1 pintu masuk dan 1 pintu keluar untuk labirin
- Pintu masuk dan keluar harus sejajar dengan tepi kisi dan berdekatan dengan sel yang termasuk dalam jalur solusi
- Anda dapat memilih tempat pintu masuk dan keluar ditempatkan
- Anda dapat mengasumsikan bahwa jalur yang valid dapat dibentuk dari gambar input yang diberikan
(Ditambahkan untuk klarifikasi) Diagram di bawah ini menunjukkan bagaimana jalur solusi berkorelasi dengan gambar input:
Input (I): | Output: | Corresponding Cells:
| | (@'s denote #'s from I)
| |
....... | ############### | ###############
.#####. | # # | # #
.#####. | # ### ####### # | # ### ####### #
####### | # #.........# # | # #@.@.@.@.@# #
.#####. | # #.#######.# # | # #.#######.# #
.#####. | # #.#.......# # | # #@#@.@.@.@# #
....... | ###.#.######### | ###.#.#########
| ....#.#........ | .@.@#@#@.@.@.@.
| #####.#.####### | #####.#.#######
| # ...#..... # | # @.@#@.@.@ #
| # #.#######.# # | # #.#######.# #
| # #.........# # | # #@.@.@.@.@# #
| # ####### ### # | # ####### ### #
| # # # # | # # # #
| ############### | ###############
| |
Uji Kasus
Penyiraman dapat contoh dari Wikipedia :
Memasukkan:
..................
..................
.......####.......
......##..##......
.....##....##....#
.....#......#...##
.#############.##.
##..############..
#...###########...
#...##########....
#...##########....
#...##########....
#...##########....
....##########....
....##########....
....##########....
..................
..................
Output (S = false):
#####################################
# # # # # # #
# ### ### ### # # ##### ### ### ### #
# # # # # # # # # # #
# ### # ##### # ########### # ### # #
# # # # # # # # #
# # # ### ##### # ### ### # ### ### #
# # # # # # # # # # # # #
# ### # ##### ##### ### ##### # # ###
# # # # # # # # #
### ####### ### ### # ### ##### ### #
# # # # # # # # # # #
# ### ##### # ### ####### # # # # # #
# # # # # # # #
# # ##### ############# ### ### ### #
# # # # # # # # # #
# ### # ####### # ### ### # # ### # #
# # # # # # # # # #
# # # ### ######### # # ##### # #####
# # # # # # # # # # # #
# ##### # # ##### # ##### # # ### # #
# # # # # # # # # # #
# ### ### ### # ### # ##### ####### #
# # # # # # # # # #
# # # # ####### # ### # ##### # ### #
# # # # # # # # # # #
### # # # # # ############# # ### # #
# # # # # # # # # # #
##### # # ##### ####### # ### ##### #
# # # # # # # # #
##### # # # # ####### # ### #########
# # # # # #
# ### ######### ############# # #####
# # # # # # # # #
# # ######### # ####### ####### ### #
# # # #
#####################################
Output (S = true):
#####################################
# # # # # # #
# ### ### ### # # ##### ### ### ### #
# # # # # # # # # # #
# ### # ##### # ########### # ### # #
# # # #....... # # # # #
# # # ### #####.# ###.### # ### ### #
# # # # #...# # #...# # # # #
# ### # #####.##### ###.##### # # ###
# # # ...# # #... # # #..
### #######.### ### # ###.##### ###.#
# # #.# # # #.# # #...#
# ### #####.# ### #######.# # # #.# #
# #.......#.............#...# #...# #
# #.#####.#############.###.###.### #
#...# #.......#.....#...#.#...# # #
#.### # #######.#.###.###.#.#.### # #
#.# # # .......#...#.#...#...# #
#.# # ###.#########.#.#.##### # #####
#.# # #.#.......#.#...#...# # # #
#.##### #.#.#####.#.#####.#.# ### # #
#. #.#...#...#.#.....#.# # # #
#.### ###.###.#.###.#.#####.####### #
#. # # #.....#.#...#.#..... # #
#.# # # #######.#.###.#.##### # ### #
..# # # #...#...#.....#.....# # # #
### # # #.#.#.#############.# ### # #
# # # #.#...#.........#...# # # #
##### # #.#####.#######.#.### ##### #
# # #.#...#.......#.#...# #
##### # #.#.#.#######.#.###.#########
# # ...#.........#..... # #
# ### ######### ############# # #####
# # # # # # # # #
# # ######### # ####### ####### ### #
# # # #
#####################################
Contoh Bitmap (labirin yang sama seperti di atas):
sumber
Jawaban:
Python 3, 1599 Bytes
Saya menemukan ini sebagai proyek yang menyenangkan dan sangat menarik (dan agak panjang). Ketika saya melihat ini, saya teringat akan musim panas yang saya habiskan secara eksklusif untuk menulis dan meningkatkan algoritme pembuatan labirin dan langsung mengerjakannya.
Setelah beberapa saat, saya memiliki draft awal sekitar 6000 byte panjang dan saya menghabiskan beberapa jam berikutnya kondensasi ke dalam program berikut:
Yang kira-kira tidak masuk akal untuk dipandang sebagai labirin ascii-art adalah ...
Perlu dicatat bahwa, karena fungsi acak tidak digunakan sampai setelah jalan yang benar telah ditemukan, tidak peduli berapa kali input yang sama diberikan, rute dari awal hingga akhir akan sama dan, sementara program ini tidak bekerja untuk contoh-contoh di atas, kadang-kadang itu tidak akan dapat menemukan solusi jika 'mendorong dirinya sendiri ke dinding' untuk berbicara.
Saat menjalankan contoh di atas, ini memberikan ini:
ini:
dan ini:
Bagi siapa saja yang ingin mencoba menjalankan program ini sendiri, gunakan perintah
M(Image, Show solution)
. Saya akan merekomendasikan menggunakan tanda kutip tiga untuk memasukkan gambar karena jika tidak akan ada banyak garis miring atau karakter baris baru yang terlibat.sumber
0
alih-alihpass
,l.append(a);l.append(b)
->l+=a,b
,l.append(a)
->l+=[a]
, mungkin ada baiknya menugaskan'#'
ke variabel, dandef E(G,y,z):\n c=[]
->def E(G,y,z,c=[]):
if G[r][c]==1 or G[r][c]==2:
->if 0<G[r][c]<3:
,s=[0]\n for x in R(L(I[0])*2):s+=[0]
->s=[0]*(1+L(I[0])*2)
dan (saya pikir, belum mengujinya)G=[s]
->*G=s
.except:0
,l+=a,b
dans=[0]*(1+L(I[0])*2)
sangat membantu. Sayangnya, untuk alasan apa pun, menugaskan c dalam panggilan fungsi tidak meresetnya melalui beberapa panggilan yang berarti berhenti bekerja, G [r] [c] dapat berupa string sehingga saya tidak dapat menggunakan <atau> pada itu dan * G = s memberi saya kesalahan sintaksis. Tetap saja, saran yang bagus.G[r][c]
bisa berupa string,G[r][c]in[1,2]
harusnya berfungsi.