Ksatria mengisi kotak

15

Ksatria mengisi adalah mengisi banjir menggunakan konektivitas bagian catur ksatria. Secara khusus:

 1 1
1   1
  0
1   1
 1 1

(0 adalah titik awal, 1s menunjukkan sel yang terhubung)

Tantangan

Diberi kisi 2D ruang dan dinding, dan lokasi awal, melakukan knight-fill pada kisi. Kode terpendek menang.

Aturan

  • Anda dapat mengambil input dan menghasilkan output dalam format apa pun yang Anda suka (gambar, string, array, apa pun). Anda dapat mengambil lokasi awal sebagai bagian dari kisi masukan atau sebagai koordinat terpisah. Untuk tujuan penjelasan ini, format berikut akan digunakan:

    ########    # = wall
    ########    x = initial location
    ## x  ##
    ##    ##
    ########
    ##    ##
    ########
    ########
    
  • Output adalah salinan dari grid input dengan hasil knight-fill ditambahkan

  • Isi Anda tidak boleh dalam "warna" yang sama dengan ruang atau dinding, tetapi bisa sama dengan penanda lokasi awal. Misalnya diberikan gambar di atas, output yang valid adalah:

    ########    # = wall
    ########    @ = fill (could also have been x)
    ## @ @##
    ## @ @##
    ########
    ##@ @ ##
    ########
    ########
    
  • Anda dapat mengasumsikan bahwa kisi input akan selalu berisi dinding 2 sel di semua sisi

  • Anda mungkin berasumsi bahwa lokasi awal tidak akan pernah ada di dalam tembok
  • Anda dapat berasumsi bahwa kisi tidak akan pernah lebih besar dari 1000x1000
  • Builtin baik-baik saja
  • Kode terpendek (dalam byte) menang

Uji Kasus

Dalam semua kasus uji, #menunjukkan dinding, menunjukkan ruang kosong, dan xmenunjukkan lokasi awal pengisian. @menunjukkan isi keluaran.

Input 1:

########
########
## x  ##
##    ##
########
##    ##
########
########

Output 1:

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

Input 2:

############
############
## ##    x##
## ##     ##
#####     ##
##        ##
############
############

Output 2:

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

Input 3:

####################
####################
##  ##            ##
##  ##            ##
##  ##  ########  ##
##  ##  ########  ##
##  ##  ##    ##  ##
##  ##  ##    ##  ##
##  ##  ##    ##  ##
##  ##  ##    ##  ##
##  ##  ########  ##
##  ##  ########  ##
##  ##        ##  ##
##  ##       x##  ##
##  ############  ##
##  ############  ##
##                ##
##                ##
####################
####################

Output 3:

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

Input 4:

################
################
##           ###
##     x     ###
##  #######  ###
##  #######  ###
##  ##   ##  ###
##  ##   ##  ###
##  ##   ##  ###
##  ########  ##
##  ########  ##
##        ##  ##
##        ##  ##
################
################

Output 4:

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

Input 5:

##############
##############
##         ###
##         ###
##         ###
##   ###   ###
##   #x#   ###
##   ###   ###
##         ###
##         ###
##         ###
##############
##############

Output 5:

##############
##############
##@@@@@@@@@###
##@@@@@@@@@###
##@@@@@@@@@###
##@@@###@@@###
##@@@#@#@@@###
##@@@###@@@###
##@@@@@@@@@###
##@@@@@@@@@###
##@@@@@@@@@###
##############
##############
Dave
sumber
Agak terkait.
Martin Ender

Jawaban:

4

Oktaf, 73 byte

function a=F(s,a)do;b=a;until(a=~s&imdilate(a,de2bi(")0#0)"-31)))==b;a+=s

Demo online!

* Beberapa perubahan diterapkan untuk dijalankan di rextester.

Fungsi yang mengambil larik 2d 0 & 2 sebagai dinding dan larik 0 & 1 sebagai lokasi awal dan menghasilkan larik 0 & 1 & 2.

rahnema1
sumber
Terlihat bagus, tetapi bukankah ini perlu pkg load ...saat dijalankan di luar kerangka uji? Jika imdilate& de2bitersedia tanpa impor eksplisit maka itu tidak masalah.
Dave
@Dave Dalam versi oktaf sebelumnya, termasuk versi yang dipasang di tio, adalah mungkin untuk menginstal paket sehingga dapat memuat secara otomatis tetapi sekarang saya perhatikan bahwa fitur ini dihapus dari oktaf! tolong lihat ini .
rahnema1
Cukup adil. Selama Anda menargetkan versi sebelum -autodihapus, itu tidak masalah, dan saya menduga jawaban ini tidak menggunakan fitur baru.
Dave
3

JavaScript (ES6), 116 byte

f=(s,l=s.search`
`,t=s.replace(eval(`/(x| )([^]{${l-2}}(....)?|[^]{${l+l}}(..)?)(?!\\1)[x ]/`),'x$2x'))=>s==t?s:f(t)

v=(s,l=s.search`
`)=>!/^(#+)\n\1\n[^]*x[^]*\n\1\n\1$/.test(s)|s.split`
`.some(s=>s.length-l|!/^##.+##$/.test(s))&&`Invalid Input`
textarea{font-family:monospace}
<textarea rows=11 cols=33 oninput=o.value=v(this.value)||f(this.value)></textarea><textarea rows=11 cols=33 id=o reaodnly></textarea>

Berdasarkan jawaban saya untuk Mendeteksi Kastil Gagal . Mengisi menggunakan xs.

Neil
sumber
Bisakah Anda menambahkan cuplikan / tautan uji?
officialaimm
2

Python 3 , 394 387 381 356 352 347 319 313 154 139 byte

  • 154 byte setelah hanya menghitung fungsi inti dan bukan fungsi tentang pemformatan I / O
  • disimpan 7 byte: terima kasih kepada @Jacoblaw dan @ Mr.Xcoder: except:0
  • disimpan 28 byte !!!: Terima kasih kepada @ovs: singkirkan try: exceptblok dan beberapa golf lainnya
  • Terima kasih kepada @Dave untuk modul tes yang indah.
  • disimpan 6 byte: g[(a,b)] hanyag[a,b]
  • @nore menyimpan 15 byte !!! :
def x(g,a,b,m):
 if(a,b)in g and"!">g[a,b]or m:
  g[a,b]="@"
  for i in 1,2,-1,-2:
   for j in 3-abs(i),abs(i)-3:g=x(g,a+i,b+j,0)
 return g

Cobalah online!

officialaimm
sumber
1
bisakah kamu melakukannya except:pass?
jacoblaw
1
Saya cukup yakin bahwa ini bisa sangat
golf
2
@ jacoblaw lebih baik lagi:except:0
Mr. Xcoder
1
319 byte
ovs
1
Inilah versi TiO yang sedikit lebih mudah untuk diuji: Cobalah secara online!
Dave
1

Mathematica, 117 byte

Kisah yang biasa: built-in yang kuat tetapi nama panjang ...

HighlightGraph[g,ConnectedComponents[h=Subgraph[g=KnightTourGraph@@Dimensions@#,Flatten@#~Position~1],#2]~Prepend~h]&

Cobalah di kotak pasir Wolfram!

Dibutuhkan dua input: pertama adalah kisi input sebagai larik 0s (untuk dinding) dan 1s (untuk spasi), kemudian bilangan bulat tunggal untuk posisi awal, ditemukan dengan memberi nomor kisi di sepanjang baris dari atas ke bawah, misalnya

1  2  3  4  5
6  7  8  9  10
11 12 13 14 ...

Anda dapat memanggil fungsi seperti HighlightGraph[...~Prepend~h]&[{{0,0,...,0}, {0,0,...,0}, ..., {0,0,...,0}}, 20] .

The KnightTourGraphFungsi membangun grafik dengan simpul sesuai dengan posisi di grid dan tepi sesuai dengan bergerak ksatria valid, maka kita mengambil Subgraphdari simpul yang tidak dinding, dan menemukan ConnectedComponentssatu titik awal. Outputnya adalah grafik (ditunjukkan diputar 90º berlawanan arah jarum jam) dengan simpul non-dinding disorot merah, dan simpul yang diisi disorot kuning. Misalnya, untuk kasus uji pertama, hasilnya terlihat seperti:

Output untuk test case 1: grafik dengan beberapa area disorot

Bukan pohon
sumber
Yah ini sepertinya yang paling sulit untuk diuji! Bisakah Anda menambahkan contoh cara memintanya di kotak pasir, bagi kita yang belum menyentuh Mathematica sejak masa kuliah kita? Upaya saya f=... f[{0,...,0;0,...,0}, 19]dan sejenisnya telah gagal total.
Dave
@Dave, Anda dapat memanggil fungsi dengan HighlightGraph[g,ConnectedComponents[h=Subgraph[g=KnightTourGraph@@Dimensions@#,Flatten@#~Position~1],#2]~Prepend~h]&[{{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,1,1,1,1,0,0},{0,0,1,1,1,1,0,0},{0,0,0,0,0,0,0,0},{0,0,1,1,1,1,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0}},20](untuk kasus uji pertama). Saya telah mengeditnya dalam pertanyaan - maaf tidak ada di sana untuk memulai!
Bukan pohon