Pemecah labirin tekstual

14

Diberi labirin pada stdin dan titik masuk, tulis sebuah program yang mencetak jalur ke jalan keluar di stdout. Jalur apa pun dapat diterima, selama program Anda tidak menghasilkan jalur sepele (melewati setiap titik di labirin) untuk setiap labirin.

Pada input, dinding ditandai oleh a #dan titik masuk oleh a @. Anda dapat menggunakan karakter apa pun untuk menggambar labirin dan jalur di output, asalkan semuanya berbeda.

Anda dapat berasumsi bahwa:

  • Titik masuk dan keluar ada di tepi input
  • Setiap baris input memiliki panjang yang sama
  • Labirin dapat dipecahkan dan tidak memiliki siklus
  • Hanya ada satu titik keluar

Solusi terpendek oleh (Unicode) jumlah karakter menang.

Contohnya

(perhatikan bahwa input diisi dengan spasi)

####   
#  #   
@ #####
#     #
#      
#######

####
#  #
@*#####
#*    #
#******
#######

### ###################
###         #         #
##  #########      #  #
 #             #####  #
 ###############   #@##

###*###################
###*********#*********#
## *#########*     # *#
 # *********** #####**#
 ###############   #@##
Lowjacker
sumber
Bisakah saya menambahkan karakter untuk titik akhir? Itu akan membuat program saya lebih mudah untuk mengetahui kapan harus berakhir.
Peter Olson
@ Peter Of The Corn: Tentu. Anda tidak harus menggunakan karakter yang sama untuk menggambar seluruh jalur, itu hanya harus dibedakan dari sisa output.
Lowjacker

Jawaban:

5

Ruby 1.9, 244 karakter

l=*$<
i=l*""
e=[]
d=[1,-1,x=l[0].size,-x]
r=[f=9e9]*s=x*b=l.size;r[i=~/@/]=0
r.map{i.gsub(/ /){r[p=$`.size]=d.map{|u|p>-u&&r[u+p]||f}.min+1;e<<p if p%x%~-~-x*(p/-~x%~-b)<1}}
r[g=e.find{|i|r[i]<f}].times{i[g]=?*;g+=d.find{|l|r[g]>r[g+l]}}
puts i

Keluaran untuk dua contoh:

####   
#  #   
@*#####
#*    #
#******
#######

###*###################
###*        #     *** #
## *######### *****#* #
 # ************#####* #
 ###############   #@##

Suntingan:

  • (247 -> 245) Sertakan e dan ubah namanya menjadi g
  • (245 -> 249) Perbaiki bug saat pintu keluar tepat di atas pintu masuk
  • (249 -> 246) sebaris + penyederhanaan
  • (246 -> 244) Cara lebih pendek untuk beralih ke setiap bidang
Ventero
sumber
8

ANSI C ( 384 373 368 karakter)

Inilah upaya C saya. Dikompilasi dan dijalankan di Mac OS X.

m[9999],*r=m,*s=m,c,R=0,*a,L;
P(){while(*s++)putchar(*(s-1));}
C(int*l){if((l-s+2)%R==0||(l-s)%R==0||l-s<R||l>r-R)*l=42,P(),exit(0);}
e(int*l){if(*l==32)C(l),*l=42,e(l-1),*l=32,*l=42,e(l-R),*l=32,*l=42,e(l+1),*l=32,*l=42,e(l+R),*l=32;}
main(){while(~(c=getchar()))*r++=c,R=!R&&c==10?r-s:R,L=c==64?r-s-1:L;L%R==0&&e(s+L+1);(L+2)%R==0&&e(s+L-1);L<R&&e(s+L+R);e(s+L-R);}

Contoh output untuk beberapa tes:

####   
#  #   
@*#####
#*****#
#    *#
#####*#

###*###################
###*        #******** #
##**#########**    #* #
 #*************#####* #
 ###############   #@##

Keterbatasan: Hanya berfungsi untuk labirin hingga 1000 karakter, tetapi ini dapat dengan mudah ditingkatkan. Saya hanya memilih nomor arbitrer daripada repot-repot ke malloc / remalloc.

Juga, ini adalah kode yang paling sarat peringatan yang pernah saya tulis. 19 peringatan, meskipun sepertinya lebih dengan menyoroti kode XCode. : D

EDIT: Diedit dan diuji untuk menjatuhkan int dari utama, untuk menggunakan ~ bukannya! = EOF dan putchar bukan printf. Terima kasih atas komentarnya!

Jonathan Watmough
sumber
Anda dapat menggunakan 9999 - jumlah karakter yang sama
Lowjacker
Kerja bagus! Hilangkan " int " sebelum maindan simpan 4 karakter. Juga gunakan putchar(*(s-1))alih-alih printf("%c",*(s-1))menyimpan 4 lagi.
Casey
Anda juga dapat mengganti 0xAdengan 10dan !=oleh ^.
Lowjacker
Bahkan lebih baik: Anda dapat menggunakan ~operator untuk memeriksa EOF:while(~(c=getchar())
Lowjacker
Saya juga dapat menjatuhkan! L&& penjaga pada pengaturan L, lokasi di labirin '@'.
Jonathan Watmough
4

Python, 339 karakter

import sys
M=list(sys.stdin.read())
L=len(M)
R=range(L)
N=M.index('\n')+1
D=2*L*[9e9]
D[M.index('@')+N]=0
J=(1,-1,N,-N)
for x in R:
 for i in[N+i for i in R if' '==M[i]]:D[i]=min(1+D[i+j]for j in J)
e=[i+N for i in R[:N]+R[::N]+R[N-2::N]+R[-N:]if 0<D[i+N]<9e9][0]
while D[e]:M[e-N]='*';e=[e+j for j in J if D[e+j]<D[e]][0]
print''.join(M)

Menghasilkan jalur terpendek melalui labirin.

Output untuk labirin misalnya:

####   
#  #   
@*#####
#*    #
#******
#######

###*###################
###*        #     *** #
## *######### *****#* #
 # ************#####* #
 ###############   #@##
Keith Randall
sumber
Mengapa semua penambahan dan pengurangan oleh N?
Lowjacker
Ini mencegah pengindeksan D [i + j] pada baris 10 dari menjadi negatif. Dan D [e + j] di baris 12.
Keith Randall
1

Python - 510 421 karakter

m=[]
i=raw_input
l=i()
x=y=-1
while l:
 if y<0:x+=1;y=l.find('@')
 m.append(list(l));l=i()
s=(x,y)
t={}
q=[s]
v={s:1}
while 1:
 try:(i,j),q=q[0],q[1:];c=m[i][j]
 except:continue
 if c==' 'and(i*j==0)|(i+1==len(m))|(j+1==len(m[0])):break
 for d,D in(-1,0),(0,-1),(1,0),(0,1):
  p=(i+d,j+D)
  if not p in v and'#'!=c:v[p]=0;q.append(p);t[p]=(i,j)
while(i,j)!=s:m[i][j]='*';i,j=t[(i,j)]
print'\n'.join(''.join(l)for l in m)
Juan
sumber
Saya mendapatkan *di sudut kanan bawah, pada test case pertama (python 2.6.1). Adakah pikiran?
Lowjacker
@ Lowjacker Terima kasih, sepertinya saat bermain golf saya menambahkan bug yang membuatnya tampak bekerja, tetapi hanya untuk kasus uji, dan bahkan hampir tidak: P
Juan
Bagus, itu berfungsi sekarang. Tapi Anda lupa untuk mengambil print b,rdan print (i,j), yang saya
duga
0

Python 3 , 275 byte

import sys
def q(g,s=[]):w=len(g[0])+1;k='@'.join(g)+w*'@';*p,x=s or[k.find('#')];return'@'>k[x]and{x}-{*p}and[p,min((q(g,s+[x+a])or k for a in(-1,1,-w,w)),key=len)]['*'>k[x]]
g=''.join(sys.stdin.read());s=q(g.split('\n'))
for i in range(len(g)):print(end=[g[i],'+'][i in s])

Cobalah online!

Port jawaban saya untuk Menemukan rute terpendek di jalan ASCII .

Penggunaan '#'untuk memulai, '*'untuk akhir, '@'untuk dinding dan ' 'untuk ruang kosong. Dalam hal ini, fungsi tersebut qadalah fungsi pembantu yang mengembalikan array satu dimensi dengan jalur terpendek dalam labirin. Fungsi fdapat dipersingkat 4 byte dengan tidak menugaskan variabel s. Ini sangat tidak efisien dan kemungkinan akan habis, karena ini memanggil fungsi pencarian jalan untuk setiap karakter di maze.

Jitse
sumber