Bisakah labirin dipecahkan?

20

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

dwana
sumber
Haruskah inputnya berupa string atau array?
apsillers
3
Jika ada 1 (dinding) di (n, m) haruskah kode mengembalikan 0?
trichoplax
3
(Sama untuk tembok di (0,0)?)
Martin Ender
3
Anda mengatakan ini adalah labirin × m, tetapi pengindeksan Anda menyiratkan bahwa ini adalah labirin (n +1) × (m +1).
Nick Matteo
3
Saya menantikan solusi regex =)
flawr

Jawaban:

7

CJam, 42 41 39 36 35 byte

Wq3>~_s,{{[{_2$+0<{e<_}*}*]}%z}*sW=

Berdasarkan ide-ide dalam jawaban ini .

4 byte berkat Pengoptimal.

Masukkan format:

[[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]]
jimmy23013
sumber
@ Opsizer Terima kasih untuk itu. Tapi kemudian saya menemukan cara yang lebih singkat ...
jimmy23013
1
q2Wts~_s,{{[{_2$+0<{e<_}*}*]}%z}*sW=- 36. Meskipun diasumsikan bahwa tiga karakter pertama dari input adalah[[0
Pengoptimal
7

Dyalog APL, 27 karakter

⊃⌽∨.∧⍨⍣≡1≥+/¨|∘.-⍨,(~×⍳∘⍴)⎕

input yang dievaluasi. APL membedakan antara matriks dan vektor vektor. Program ini mengasumsikan bahwa input adalah sebuah matriks.

(~×⍳∘⍴)Aadalah garpu yang setara dengan (~A) × ⍳⍴A. Ini diperlukan untuk menghindari menyebutkan dua kali atau memperkenalkan variabel.

⍴Aadalah bentuk A. Untuk matriks 4-oleh-7 bentuknya adalah 4 7.

adalah generator indeks. ⍳4adalah 1 2 3 4. ⍳4 7adalah vektor (1 1)(1 2)...(4 7)disusun dalam matriks 4-oleh-7.

~Amembalik bit A.

×dengan mengalikan ⍳⍴Adengan bit yang dibalik, kami menjaga koordinat semua sel bebas dan mengubah semua dinding menjadi 0 0.

,putar matriks pasangan koordinat, yaitu linearkan menjadi vektor. Dalam hal ini vektor akan terdiri dari pasangan.

∘.-⍨Aatau A∘.-Akurangi elemen Aberpasangan. Perhatikan bahwa di sini elemen dari Apasangan 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 mana nbilangan bulat adalah operator daya. Ini berlaku funtuk A nkali: f f ... f A.

(f⍣g)Adi mana gfungsi, adalah operator titik tetap, alias "batas daya". Itu terus komputasi seri A, f A, f f A, ... sampai ((f⍣i)A) g ((f⍣(i+1))A)kembali benar untuk beberapa i. Dalam hal ini kami menggunakan kecocokan ( ) sebagai g.

∨.∧⍨Aatau A∨.∧Amerupakan langkah dalam algoritma Floyd. f.gadalah 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-langkahnya

ngn
sumber
5

Python, 164 byte

def s(a):
 d=[(0,0)]
 while d:i,j=d.pop();a[i][j]=2;d+=[(x,y)for x,y in[(i-1,j),(i,j-1),(i+1,j),(i,j+1)]if len(a[0])>y>-1<x<len(a)and a[x][y]<1]
 return a[-1][-1]>1

Saya enggan memposting ini karena praktis bagaimana saya biasanya mengisi banjir, hanya bermain golf ringan. Tapi ini dia.

Sp3000
sumber
4

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).

/.*/;s/(^0|A)(.{@{+}})?0/A$2A/s||s/0(.{@{+}})?A/A$1A/s?redo:say/A$/+0

Cobalah online! (dan jika Anda mengganti 1111011baris dengan 1111111, labirin tidak dapat dipecahkan lagi, dan hasilnya akan menjadi 0bukannya 1: 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 dengan A, maka itu dapat dijangkau dan kami menandainya dengan Ajuga; dan kami melakukannya lagi ( redo). Itu dilakukan berkat dua regex: s/(^0|A)(.{@{+}})?0/A$2A/smemeriksa apakah ada ruang di kanan atau bawah A, sementara s/0(.{@{+}})?A/A$1A/smemeriksa apakah ada ruang di kiri atau di atas a A. Pada akhirnya, jika sel terakhir berisi Aitu dapat dijangkau, jika tidak maka (itu yang say/A$/+0memeriksa; +0ada di sini untuk memastikan hasilnya akan 0atau 1bukan string kosong dan 1).
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)

Dada
sumber
Untuk kasus uji ini , kode Anda menganggap labirin dapat dipecahkan bahkan jika posisi akhirnya 1.
Jitse
@ Jitse Tangkapan yang bagus. Sebenarnya, itu karena tautan TIO tidak menggunakan kode yang benar (saya kira itu beberapa versi sebelumnya dan saya tidak menemukannya). Jawabannya masih valid, dan saya telah memperbarui tautan TIO. Contoh Anda berfungsi dengan baik: Coba online!
Dada
Oh benar Terima kasih atas klarifikasi, saya suka pendekatan ini.
Jitse
@Jitse terima kasih, itu salah satu golf favorit saya :)
Dada
3

Ruby, 133 130 129 karakter

a=eval gets
f=->x,y{a[x][y]=1
[[-1,0],[1,0],[0,-1],[0,1]].map{|o|d,e=x+o[0],y+o[1]
f[d,e]if a[d]&&a[d][e]==0}}
f[0,0]
p a[-1][-1]

Input pada STDIN, output 1atau0 pada STDOUT.

Sangat panjang. Ini hanya mengisi banjir 1dari (0, 0), dan kemudian memeriksa untuk melihat apakah "ujung" kotak adalah 1.

Gagang pintu
sumber
Apakah ini akan memperlakukan labirin sebagai dapat dipecahkan jika sudah berisi angka 1 at (n, m)?
trichoplax
2

Java, 418 byte

import java.util.Scanner;public class Solvable{static int w,h;public static void main(String[] a){String[]i=new Scanner(System.in).nextLine().split(";");h=i.length+2;w=i[0].length()+2;int[]m=new int[w * h];for(int x=1;x<w-1;x++)for(int y=1;y<h-1;y++)m[y*w+x]=i[y-1].charAt(x-1)<'.'?0:1;f(m,w+1);System.out.println(m[w*h-w-2]>0?0:1);}static void f(int[]m,int i){if(m[i]>0){m[i]--;f(m,i-1);f(m,i+1);f(m,i-w);f(m,i+w);}}}

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:

......#;.....#.;....#..;#......
bace1000
sumber
1
Pro tip: beri nama kelas Anda sesuatu yang panjangnya satu karakter, selisih spasi antara String[]dan a, dan ambil input dari argumen baris perintah daripada StdIn, yang diizinkan.
Pavel
1

Python 184 188

def f(a,x=0,y=0,h=[]):s=h+[[x,y]];X,Y=len(a[0]),len(a);return([x,y]in h)==(x>=X)==(y>=Y)==(x<0)==(y<0)==a[y][x]<(x==X-1and y==Y-1or f(a,x-1,y,s)|f(a,x+1,y,s)|f(a,x,y-1,s)|f(a,x,y+1,s))

Ini jadi lebih lama daripada yang saya kira :( Bagaimanapun, saya akan menambahkan penjelasan begitu saya tidak bisa bermain golf lagi.

FryAmTheEggman
sumber
1

J, 75 karakter

Powering dari matriks adjacency (sangat tidak efisien waktu dan memori). (Apakah ini disebut powering dalam bahasa Inggris?)

   ({.@{:@(+./ .*.^:_~)@(+:/~@,*2>(>@[+/@:|@:->@])"0/~@,@(i.@#<@,"0/i.@#@|:)))

Beberapa test case:

   m1=. 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
   m2=. 0 1 1 ,. 0 0 0
   m3=. 0 1 0 ,. 1 1 0
   m4=. 0 1 1 0 ,. 0 0 1 0
   ({.@{:@(+./ .*.^:_~)@(+:/~@,*2>(>@[+/@:|@:->@])"0/~@,@(i.@#<@,"0/i.@#@|:))) every m1;m2;m3;m4
1 1 0 0
randomra
sumber
0

Python 3 , 184 byte

f=lambda m,x=0,y=0,n=0:n<len(m)*len(m[0])and m[x][y]<1and((x,y)==(len(m)-1,len(m[0])-1)or any(0<=i<len(m)and 0<=j<len(m[0])and f(m,i,j,n+1)for i,j in[(x-1,y),(x,y-1),(x+1,y),(x,y+1)]))

Cobalah online!

Matthew Jensen
sumber