Tulis program atau fungsi yang menggunakan tiga bilangan bulat, lebar w, tinggi h, dan jumlah langkah s. Anda akan menggambar langkah-langkah berjalan acak yang tidak memotong-sendiri sjauh pada gambar 5*wdengan 5*hpiksel di mana setiap sel 5 dengan 5 piksel kosong (beige murni) atau salah satu dari dua belas "pipa" sederhana ini:

Gambar di atas diperbesar untuk menampilkan detail. Berikut adalah ukuran pipa sebenarnya:

^{(Garis abu-abu hanya untuk memisahkan jenis pipa.)}

Jalan acak akan menjadi jalur pipa kontinu tunggal yang dimulai pada satu titik ujung pipa (salah satu dari empat tipe pipa terbawah) dan berakhir di titik ujung pipa lainnya.

Mulai dengan kotak kosong woleh hdan pilih satu sel secara acak untuk menjadi titik awal. Kemudian secara acak pilih salah satu dari empat arah untuk memulai dan menggambar titik akhir pipa yang sesuai. Sel awal ini menandai langkah pertama dalam berjalan Anda dan setiap kali Anda menggambar sel baru atau menimpa yang sudah ada itu dihitung sebagai langkah lain yang diambil.

Sekarang, berulang kali, pilih secara acak ke kanan, kiri, atau lurus, gambar sel pipa yang sesuai jika arah yang dipilih valid. Mundur dan pilih kembali jika arah tidak valid sampai sjalur langkah lengkap terbentuk. Jalur harus diakhiri dengan titik akhir pipa, yang mungkin ada di mana saja di grid, tergantung pada jalur yang diambil.

Sangat penting untuk dicatat bahwa hanya dua sel pipa lurus yang dapat ditimpa, dan hanya dengan sel pipa lurus dengan orientasi yang berlawanan, hasilnya adalah sel persimpangan. Kalau tidak, semua pipa harus ditempatkan di sel kosong.

Ketika persimpangan diambil, bagian jalur yang lebih jauh dari sel awal harus digambarkan di atas.

Terserah Anda apakah grid memiliki syarat batas periodik (PBC) atau tidak, yaitu apakah pipa yang keluar dari satu sisi grid akan keluar di sisi lain. Tanpa PBC, batas grid dihitung sebagai penghalang yang bisa Anda temui seperti pipa lainnya.

Kasus Khusus

• Kapan s0 tidak ada pipa yang harus ditarik dan output harus kosong 5*woleh 5*hgambar (yaitu semua krem).

• Kapan s1 stub pipa tunggal

  (Ukuran sebenarnya: )

  harus ditarik pada sel awal yang dipilih secara acak.

Detail lainnya

• Anda dapat berasumsi bahwa spaling w*hbanyak jalan akan selalu memungkinkan. (Meskipun jalur yang lebih panjang dimungkinkan karena persimpangan.)
• wdan hakan selalu positif.
• Semua pilihan acak harus seragam acak. mis. Anda tidak boleh menghindari membuat persimpangan ketika memungkinkan bahkan jika itu membuat masalah lebih mudah. Generator angka pseudo-acak diizinkan.
• Tiga warna yang berbeda secara visual dapat digunakan sebagai pengganti warna hitam, biru, dan krem.
• Gambar output Anda dapat diperbesar sehingga benar-benar 5*w*koleh 5*h*kpiksel di mana kbilangan bulat positif. (Memperbesar setiap contoh yang Anda posting disarankan meskipun Andak 1.)
• Setiap format file gambar lossless umum dapat digunakan dan gambar dapat disimpan ke file, ditampilkan, atau dimuntahkan mentah ke stdout.

Kode terpendek dalam byte menang.

Contohnya

^{(Semua diperbesar 500%.)}

Jika inputnya w=2, h=1, s=0maka output akan selalu:

Jika inputnya w=2, h=1, s=1maka output akan menjadi salah satu gambar ini dengan peluang yang sama:

Jika inputnya w=2, h=1, s=2maka output akan menjadi

atau mungkin

jika grid diasumsikan memiliki PBC.

(Perhatikan bahwa memulai jalur seperti akan membuat langkah kedua menjadi tidak mungkin.)

Berikut adalah beberapa kemungkinan keluaran w=3, h=2, s=6, dengan asumsi PBC:

Berikut ini adalah kemungkinan output untuk w=3, h=3, s=9, dengan asumsi PBC:

Perhatikan bahwa jalur tidak perlu menutupi semua sel karena penghitungan persimpangan adalah dua langkah. Juga, kita dapat menyimpulkan bahwa titik akhir sudut adalah sel awal karena jembatan penyimpangan pasti telah ditarik sesudahnya. Dengan demikian kita dapat menyimpulkan urutan pilihan acak yang dibuat:

start at top left, facing east
go straight
go right
go right
go right
go straight
go left
go right
end

Akhirnya, berikut adalah contoh w=4, h=5, s=20dan w=4, h=5, s=16:

CJam, 274

q~:K;:B;:A;{0aA*aB*:M5*5f*:I;K{[Bmr:QAmr:P]5f*:R;3Ym*{R.+:)2{1$0=I=2$W=@tI@0=@t:I;}:F~}/R2f+1FK({MQ=P=:EY4mr:D#&1{{MQMQ=PE2D#+tt:M;}:G~7,1>[W0_1_0_W]2/D=:Off*{[QP]5f*2f+.+_:H1F_OW%.+2FOW%.m2F}/H2FO~P+:P;Q+:Q;MQ=P=:E_5YD2%-*=!JK2-=+*1{D2+4%:D;G}?}?}fJ]}0?}g'P2NA5*SI,N2NI:+N*

Cobalah online

Menggunakan PBC, output dalam format PGM. Anda dapat menghapus:+ dekat akhir untuk mendapatkan output visual yang lebih bagus di browser.

Sangat lambat untuk input yang lebih besar, terutama jika jumlah langkah dekat dengan area.

Contoh hasil untuk input 4 3 10(skala 500%):

Penjelasan singkat:

Pendekatan umum adalah:

• ulangi semua langkah berikut sampai berhasil:
• inisialisasi 2 matriks: satu rekaman sisi mana yang digunakan di setiap sel, dan satu untuk gambar
• jika s = 0, kita selesai, kalau tidak:
• pilih sel acak dan gambar kotak, lalu lakukan s-1 kali berikut:
• pilih arah acak; jika sisi itu sudah digunakan, gagal dan mulai lagi dari awal
• tandai sisi yang digunakan dan gambar pipa yang sebenarnya dalam gambar (gambar 3 garis yang berdekatan dengan panjang 6, mulai tepat "setelah" piksel tengah sel saat ini, lalu tambahkan sebuah titik untuk menutup ujung pipa)
• perbarui posisi saat ini (pindah ke sel berikutnya)
• periksa apakah sel itu kosong atau itu adalah persilangan yang benar; jika tidak, gagal dan mulai lagi dari awal
• tandai sisi dalam arah yang berlawanan seperti yang digunakan dalam sel ini, kemudian lanjutkan loop

QBasic, 517 516 byte

RANDOMIZE TIMER
SCREEN 9
INPUT w,h,s
1CLS
IF s=0GOTO 9
x=5*INT(RND*w)
y=5*INT(RND*h)
GOSUB 7
FOR k=1TO s-1
r=INT(RND*4)+1
a=x+5*((r=2)-(r=4))
b=y+5*((r=1)-(r=3))
c=(POINT(a,b+2)*POINT(a+4,b+2)+POINT(a+2,b)*POINT(a+2,b+4))*(0=POINT((a+x)\2+2,(b+y)\2+2))
IF((0=POINT(a+2,b+2))+c)*(a>=0)*(b>=0)*(a<5*w)*(b<5*h)=0GOTO 1
x=a
y=b
GOSUB 7
o=1AND r
p=x-2+3*o-5*(r=2)
q=y+1-3*o-5*(r=1)
u=p+3-o
v=q+2+o
LINE(p,q)-(u,v),7,B
LINE(p+o,q+1-o)-(u-o,v-1+o),1
NEXT
9IF c GOTO 1
END
7LINE(x+1,y+1)-(x+3,y+3),7,B
PSET(x+2,y+2),1
RETURN

• Mengambil w,, hdan sdari input pengguna, dipisahkan oleh koma.
• Output ditarik di layar. Saat program mencari solusi, Anda mungkin melihat sebagian solusi berkedip-kedip.
• Tidak menggunakan kondisi batas periodik. Saya merasa lebih mudah untuk menggambar dan menguji untuk menghubungkan pipa tanpa harus khawatir setengah dari pipa berada di satu sisi grid dan setengah di sisi lainnya.

Pendekatan di sini adalah untuk mencoba arah acak pada setiap langkah dan memulai kembali dari awal jika itu menghasilkan langkah yang tidak valid. Kami menggambar pipa sesuai petunjuk yang ditentukan, dan digunakan POINTuntuk menguji poin di layar untuk kondisi validitas kami. Suatu langkah valid jika tidak melampaui batas grid dan:

1. Sel pindah ke kosong; atau
2. Kedua
   1. Sel pindah-ke berisi pipa yang lurus, baik secara horizontal atau vertikal, dan
   2. Bagian pipa baru tidak menggandakan bagian pipa yang ada

Seperti jawaban CJam dari aditsu , kode ini sangat lambat, dan bisa sangat lambat jika shanya sebagian kecil saja w*h. Pada pengaturan QB64 saya, muncul dengan jawaban untuk 5,5,19cukup cepat, tetapi membutuhkan waktu lebih lama daripada yang saya tunggu 5,5,20.

Jika Anda ingin menjalankan contoh yang lebih besar / lebih padat, inilah pendekatan asli saya menggunakan pencarian kedalaman-pertama . Ini jauh lebih efisien, dengan biaya 300 byte ekstra.

RANDOMIZE TIMER
SCREEN 9
INPUT w,h,s
DIM t(s),m(s)
0
FOR z=1TO s
t(z)=-1
NEXT
i=5*INT(RND*w)
j=5*INT(RND*h)
k=1
1CLS
IF s=0GOTO 9
x=i
y=j
GOSUB 7
FOR z=1TO k-1
r=m(z)
GOSUB 6
x=a
y=b
GOSUB 7
o=1AND r
p=x-2+3*o-5*(r=2)
q=y+1-3*o-5*(r=1)
u=p+3-o
v=q+2+o
LINE(p,q)-(u,v),7,B
LINE(p+o,q+1-o)-(u-o,v-1+o),1
NEXT
IF c*(k=s)THEN k=k-1:GOTO 1 ELSE IF k=s GOTO 9
IF k<1GOTO 0
IF t(k)>=0GOTO 4
t(k)=0
f=30
WHILE f
r=INT(RND*4)+1
IF f AND 2^r THEN t(k)=t(k)*5+r:f=f-2^r
WEND
4r=t(k)MOD 5
m(k)=r
t(k)=t(k)\5
GOSUB 6
c=(POINT(a,b+2)*POINT(a+4,b+2)+POINT(a+2,b)*POINT(a+2,b+4))*(0=POINT((a+x)\2+2,(b+y)\2+2))
IF((0=POINT(a+2,b+2))+c)*(a>=0)*(b>=0)*(a<5*w)*(b<5*h)THEN k=k+1 ELSE IF t(k)>0GOTO 4 ELSE t(k)=-1:k=k-1
GOTO 1
6a=x+5*((r=2)-(r=4))
b=y+5*((r=1)-(r=3))
RETURN
7LINE(x+1,y+1)-(x+3,y+3),7,B
PSET(x+2,y+2),1
RETURN
9

Contoh output untuk input 10, 10, 100, ukuran sebenarnya:

Versi yang lebih keren dapat ditemukan di intisari ini . Selain tidak dikomentari dan dikomentari secara menyeluruh, ini meningkatkan skala output dengan faktor konstan dan memungkinkan penundaan set di antara langkah-langkah, memungkinkan Anda untuk menonton algoritma DFS di tempat kerja. Berikut ini contoh yang dijalankan: