Teka-teki
- Cetak 0 jika labirin n * m tidak dapat dipecahkan
- Cetak 1 jika labirin n * m dapat diselesaikan (dengan 1 atau lebih cara)
(jadi saya tidak meminta jalan tetapi jika mungkin untuk menyelesaikan !!!)
Array input (2d):
[[0,0,0,0,0,0,1],[0,0,0,0,0,1,0],[0,0,0,0,1,0,0],[1,0,0,0,0,0,0]]
XXXXXXXXX
XS XX
X X X
X X X
XX FX
XXXXXXXXX
0 = can pass through
1 = can not pass trough
[0][n] is the last block of the first line
[m][0] is the first block of the last line
Aturan Posisi awal adalah 0,0 dan posisi akhir adalah n, m Anda hanya dapat bergerak secara horizontal dan vertikal. Kode terpendek menang
Jawaban:
CJam,
4241393635 byteBerdasarkan ide-ide dalam jawaban ini .
4 byte berkat Pengoptimal.
Masukkan format:
sumber
q2Wts~_s,{{[{_2$+0<{e<_}*}*]}%z}*sW=
- 36. Meskipun diasumsikan bahwa tiga karakter pertama dari input adalah[[0
Dyalog APL, 27 karakter
⊃⌽∨.∧⍨⍣≡1≥+/¨|∘.-⍨,(~×⍳∘⍴)⎕
⎕
input yang dievaluasi. APL membedakan antara matriks dan vektor vektor. Program ini mengasumsikan bahwa input adalah sebuah matriks.(~×⍳∘⍴)A
adalah garpu yang setara dengan(~A) × ⍳⍴A
. Ini diperlukan untuk menghindari menyebutkan⎕
dua kali atau memperkenalkan variabel.⍴A
adalah bentukA
. Untuk matriks 4-oleh-7 bentuknya adalah4 7
.⍳
adalah generator indeks.⍳4
adalah1 2 3 4
.⍳4 7
adalah vektor(1 1)(1 2)...(4 7)
disusun dalam matriks 4-oleh-7.~A
membalik bitA
.×
dengan mengalikan⍳⍴A
dengan bit yang dibalik, kami menjaga koordinat semua sel bebas dan mengubah semua dinding menjadi0 0
.,
putar matriks pasangan koordinat, yaitu linearkan menjadi vektor. Dalam hal ini vektor akan terdiri dari pasangan.∘.-⍨A
atauA∘.-A
kurangi elemenA
berpasangan. Perhatikan bahwa di sini elemen dariA
pasangan itu sendiri berpasangan.|
nilai mutlak+/¨
jumlah setiap pasangan nilai absolut. Ini memberi kita jarak grid antara setiap pasangan sel di labirin, kecuali untuk dinding.1≥
kami hanya tertahan di tetangga pada jarak tidak lebih dari 1, ini juga tidak termasuk dinding. Sekarang kita memiliki matriks adjacency grafik.∨.∧⍨⍣≡
Floyd - Algoritma penutupan transitif Warshall(f⍣n)A
(tidak digunakan di sini) di manan
bilangan bulat adalah operator daya. Ini berlakuf
untukA
n
kali:f f ... f A
.(f⍣g)A
di manag
fungsi, adalah operator titik tetap, alias "batas daya". Itu terus komputasi seriA
,f A
,f f A
, ... sampai((f⍣i)A) g ((f⍣(i+1))A)
kembali benar untuk beberapai
. Dalam hal ini kami menggunakan kecocokan (≡
) sebagaig
.∨.∧⍨A
atauA∨.∧A
merupakan langkah dalam algoritma Floyd.f.g
adalah generalisasi dari perkalian matriks (+.×
), di sini kami menggunakan kata hubung (∧
) dan disjungsi (∨
) sebagai ganti dari+
dan×
.⊃⌽
Setelah⍣≡
menerapkan langkah cukup lama dan mencapai kondisi stabil, kita harus mencari sudut kanan atas matriks untuk mendapatkan hasilnya, jadi kita balikkan (⌽
) dan ambil item pertama, kiri atas (⊃
).Visualisasi
⍣≡
langkah-langkahnyasumber
Python, 164 byte
Saya enggan memposting ini karena praktis bagaimana saya biasanya mengisi banjir, hanya bermain golf ringan. Tapi ini dia.
sumber
Perl, 73 byte
69 byte kode + 4 byte untuk
-n0E
(tidak yakin bagaimana tag mana dihitung pada tahun 2014, jadi saya menghitungnya untuk 4 bukannya 2, tetapi tidak masalah banyak).Cobalah online! (dan jika Anda mengganti
1111011
baris dengan1111111
, labirin tidak dapat dipecahkan lagi, dan hasilnya akan menjadi0
bukannya1
: Coba online! )Penjelasan:
Kode ini akan menemukan setiap sel yang dapat dijangkau dari labirin (dan menandainya dengan a
A
): jika sel menyentuh sel yang ditandai denganA
, maka itu dapat dijangkau dan kami menandainya denganA
juga; dan kami melakukannya lagi (redo
). Itu dilakukan berkat dua regex:s/(^0|A)(.{@{+}})?0/A$2A/s
memeriksa apakah ada ruang di kanan atau bawahA
, sementaras/0(.{@{+}})?A/A$1A/s
memeriksa apakah ada ruang di kiri atau di atas aA
. Pada akhirnya, jika sel terakhir berisiA
itu dapat dijangkau, jika tidak maka (itu yangsay/A$/+0
memeriksa;+0
ada di sini untuk memastikan hasilnya akan0
atau1
bukan string kosong dan1
).Perhatikan bahwa
/.*/
akan cocok dengan seluruh baris, dengan demikian pengaturan@+
ke indeks akhir baris pertama, yang merupakan ukuran garis, yang memungkinkan penggunaan.{@{+}}
untuk mencocokkan dengan karakter yang persis sama dengan yang ada pada garis. (@{+}
setara dengan@+
, tetapi hanya yang pertama yang dapat digunakan dalam regex)sumber
1
.Ruby,
133130129 karakterInput pada STDIN, output
1
atau0
pada STDOUT.Sangat panjang. Ini hanya mengisi banjir
1
dari(0, 0)
, dan kemudian memeriksa untuk melihat apakah "ujung" kotak adalah1
.sumber
Java, 418 byte
Golf kode pertama saya. Saya tidak tahu mengapa saya memilih Java - sangat buruk untuk bermain golf xD
Contoh maze akan dimasukkan melalui stdin seperti ini:
sumber
String[]
dana
, dan ambil input dari argumen baris perintah daripada StdIn, yang diizinkan.Python 184
188Ini jadi lebih lama daripada yang saya kira :( Bagaimanapun, saya akan menambahkan penjelasan begitu saya tidak bisa bermain golf lagi.
sumber
J, 75 karakter
Powering dari matriks adjacency (sangat tidak efisien waktu dan memori). (Apakah ini disebut powering dalam bahasa Inggris?)
Beberapa test case:
sumber
Python 3 , 147 byte
Cobalah online!
Port jawaban saya untuk Menemukan rute terpendek di jalan ASCII .
sumber
Python 3 , 184 byte
Cobalah online!
sumber