Latar Belakang

Anda adalah magang penyihir yang kuat, dan master Anda saat ini sedang mengembangkan mantra untuk membuat labirin antar dimensi untuk menjebak musuh-musuhnya. Ia ingin Anda memprogram komputer bertenaga uapnya untuk menganalisis kemungkinan tata letak. Memprogram mesin jahat ini sangat berbahaya, jadi Anda harus menjaga kode sesingkat mungkin.

Memasukkan

Input Anda adalah kisi periode .dan hash dua dimensi #, yang menandakan ruang dan dinding kosong, diberikan sebagai string yang dibatasi garis baru. Akan selalu ada setidaknya satu .dan satu #, dan Anda dapat memutuskan apakah ada baris baru atau tidak.

Kotak ini adalah cetak biru labirin tanpa batas, yang dibuat dengan menyelaraskan banyak salinan dari kotak di sebelah satu sama lain. Labirin dibagi menjadi rongga , yang merupakan komponen yang terhubung dari ruang kosong (ruang diagonal yang berdekatan tidak terhubung). Misalnya, kisi

##.####
...##..
#..#..#
####..#
##...##

menghasilkan labirin berikut (berlanjut tanpa batas ke segala arah):

##.######.######.####
...##.....##.....##..
#..#..##..#..##..#..#
####..#####..#####..#
##...####...####...##
##.######.######.####
...##.....##.....##..
#..#..##..#..##..#..#
####..#####..#####..#
##...####...####...##
##.######.######.####
...##.....##.....##..
#..#..##..#..##..#..#
####..#####..#####..#
##...####...####...##

Labirin khusus ini berisi rongga area tak terbatas. Di sisi lain, cetak biru ini menghasilkan labirin dengan hanya rongga terbatas:

##.####
##..###
####...
..####.
#..####

Keluaran

Output Anda akan menjadi nilai kebenaran jika labirin berisi rongga tak terbatas, dan nilai palsu jika tidak. Perhatikan bahwa labirin dapat berisi rongga yang terbatas dan tidak terbatas; dalam hal ini, hasilnya harus benar.

Aturan

Anda dapat menulis program atau fungsi lengkap. Hitungan byte terendah menang, dan celah standar tidak diizinkan.

Kasus Uji Tambahan

Rongga tak terbatas:

.#

#.#
...
#.#

#.###.#.###.#
#.#...#...#.#
#.#.#####.#.#
..#.#...#.#..
###.#.#.#.###
#...#.#.#...#
#.###.#.###.#

##.###
#..###
..##..
###..#
##..##

..#..#..#..#..#..#
.#..#..#..#..#..#.
#..#..#..#..#..#..

#.####.###.###.####
#...#..#...###..###
###.#..#.######..##
....####.#######...
###..###...########
##########.##....##
..###......##.##...
#.........##..#####
###########..###..#
#...........####..#
#.###########.##..#
#.##....##.....####
#.####.###.###.####

Rongga yang terbatas:

###
#.#
###

.#
#.

####
.#..
####

#.#.#
..#..
#####
..#..
#.#.#

#.#.#.#.#.#
..#...#.#..
###.###.###
..#.#......
#.#.#######
#.#.......#
#.#######.#
#.#.....#.#
#.#.#.#.#.#

##....#####
.#..#...##.
.##.#..#...
..###.###..
#..##.#####
#...##....#
#.#.#####.#
###..####.#
....####...
###...#####

###....##.#########
####...##....#...##
..####.#######.###.
....##..........##.
###..#####.#..##...
####..#..#....#..##
..###.####.#.#..##.
..###...#....#.#...
..####..##.###...##
#.####.##..#####.##
####...##.#####..##


###########
........#..
#########.#
..........#
.##########
.#.........
##.########
...#.......

JavaScript (ES6), 235 253

Metode yang sama digunakan oleh @mac. Untuk setiap sel bebas, saya mencoba mengisi rekursif, menandai sel yang digunakan dengan koordinat yang saya gunakan (yang bisa di luar template asli). Jika selama pengisian saya tiba di sel yang sudah ditandai memiliki koordinat berbeda, saya berada di jalur yang tak terbatas.

Cara unik menangani modulo di JS cukup mengganggu.

L=g=>(
  g=g.split('\n').map(r=>[...r]),
  w=g[0].length,h=g.length,
  F=(x,y,t=((x%w)+w)%w,u=((y%h)+h)%h,v=g[u][t],k=0+[x,y])=>
    v<'.'?0:v>'.'?v!=k
    :[0,2,-3,5].some(n=>F(x+(n&3)-1,y+(n>>2)),g[u][t]=k),
  g.some((r,y)=>r.some((c,x)=>c=='.'&&F(x,y)))
)

Uji di Firefox / konsol FireBug

Tak terbatas

['##.###\n#..###\n..##..\n###..#\n##..##'
,'#.#\n...\n#.#'
,'#.###.#.###.#\n#.#...#...#.#\n#.#.#####.#.#\n..#.#...#.#..\n###.#.#.#.###\n#...#.#.#...#\n#.###.#.###.#'
,'##.###\n#..###\n..##..\n###..#\n##..##'
,'#.####.###.###.####\n#...#..#...###..###\n###.#..#.######..##\n....####.#######...\n###..###...########\n##########.##....##\n..###......##.##...\n#.........##..#####\n###########..###..#\n#...........####..#\n#.###########.##..#\n#.##....##.....####\n#.####.###.###.####'
].forEach(g=>console.log(g,L(g)))

Keluaran

"##.###
#..###
..##..
###..#
##..##" true

"#.#
...
#.#" true

"#.###.#.###.#
#.#...#...#.#
#.#.#####.#.#
..#.#...#.#..
###.#.#.#.###
#...#.#.#...#
#.###.#.###.#" true

"##.###
#..###
..##..
###..#
##..##" true

"#.####.###.###.####
#...#..#...###..###
###.#..#.######..##
....####.#######...
###..###...########
##########.##....##
..###......##.##...
#.........##..#####
###########..###..#
#...........####..#
#.###########.##..#
#.##....##.....####
#.####.###.###.####" true

Terbatas

['###\n#.#\n###', '.#\n#.', '####\n.#..\n####'
,'#.#.#\n..#..\n#####\n..#..\n#.#.#'
,'#.#.#.#.#.#\n..#...#.#..\n###.###.###\n..#.#......\n#.#.#######\n#.#.......#\n#.#######.#\n#.#.....#.#\n#.#.#.#.#.#'
,'##....#####\n.#..#...##.\n.##.#..#...\n..###.###..\n#..##.#####\n#...##....#\n#.#.#####.#\n###..####.#\n....####...\n###...#####'
,'###....##.#########\n####...##....#...##\n..####.#######.###.\n....##..........##.\n###..#####.#..##...\n####..#..#....#..##\n..###.####.#.#..##.\n..###...#....#.#...\n..####..##.###...##\n#.####.##..#####.##\n####...##.#####..##'
].forEach(g=>console.log(g,L(g)))

Keluaran

"###
#.#
###" false

".#
#." false

"####
.#..
####" false

"#.#.#
..#..
#####
..#..
#.#.#" false

"#.#.#.#.#.#
..#...#.#..
###.###.###
..#.#......
#.#.#######
#.#.......#
#.#######.#
#.#.....#.#
#.#.#.#.#.#" false

"##....#####
.#..#...##.
.##.#..#...
..###.###..
#..##.#####
#...##....#
#.#.#####.#
###..####.#
....####...
###...#####" false

"###....##.#########
####...##....#...##
..####.#######.###.
....##..........##.
###..#####.#..##...
####..#..#....#..##
..###.####.#.#..##.
..###...#....#.#...
..####..##.###...##
#.####.##..#####.##
####...##.#####..##" false

C # - 423 375 byte

Selesaikan program C #, terima input melalui STDIN, output "Benar" atau "Salah" untuk STDOUT yang sesuai.

Saya tidak bisa meninggalkan Linq di sana ... untungnya penghapusannya terbayar! Sekarang melacak sel dilihat dan dikunjungi dalam array (mengingat hanya melihat jumlah yang terbatas pula). Saya juga menulis ulang kode directional, menghilangkan kebutuhan untuk Lambda, dan umumnya membuat kode lebih mustahil untuk dipahami (tetapi dengan penghematan byte yang substansial).

using C=System.Console;struct P{int x,y;static void Main(){int w=0,W,k=0,o,i,j;P t;string D="",L;for(;(L=C.ReadLine())!=null;D+=L)w=L.Length;for(i=W=D.Length;i-->0&k<W;){k=1;P[]F=new P[W];for(F[j=0].x=i%w+W*W,F[0].y=i/w+W*W;D[i]>35&j<k;)for(t=F[j++],o=1;o<5&k<W;t.y+=(o++&2)-1){t.x+=o&2;if(D[--t.x%w+t.y%(W/w)*w]>35&System.Array.IndexOf(F,t)<0)F[k++]=t;}}C.WriteLine(k>=W);}}

Ini adalah pencarian pertama (bukan yang penting) yang hanya berjalan sampai terjebak di gua yang terbatas, atau memutuskan gua itu cukup besar sehingga harus sangat besar (ketika memiliki sel sebanyak persegi panjang asli, ini berarti harus ada jalur dari satu sel ke dirinya sendiri di tempat lain, yang dapat kita terus ikuti selamanya).

Kode tidak terpangkas:

using C=System.Console;

struct P
{
    int x,y;

    static void Main()
    {
        int w=0, // w is the width
        W, // W is the length of the whole thing
        k=0, // k is visited count
        o, // o is offset, or something (gives -1,0 0,-1 +1,0 0,+1 t offset pattern)
        i, // i is the start cell we are checking currently
        j; // j is the F index of the cell we are looking at

        P t; // t is the cell at offset from the cell we are looking at

        string D="", // D is the map
        L;

        for(;(L=C.ReadLine())!=null; // read a line, while we can
            D+=L) // add the line to the map
            w=L.Length; // record the width

        for(i=W=D.Length;i-->0&k<W;) // for each cell
        {
            k=1;

            P[]F=new P[W]; // F is the list of visited cells,

            for(F[j=0].x=i%w+W*W,F[0].y=i/w+W*W; // there are reasons (broken modulo)
                D[i]>35&j<k;) // for each cell we've visited, until we've run out
                for(t=F[j++], // get the current cell
                    o=1; // o is just a counter which we use to kick t about
                    o<5& // 4 counts
                    k<W; // make sure we havn't filled F
                    t.y+=(o++&2)-1) // kick and nudge y, inc o
                {
                    t.x+=o&2; // kick x
                    if(D[--t.x%w+t.y%(W/w)*w]>35 // nudge x, it's a dot
                       &System.Array.IndexOf(F,t)<0) // and we've not seen it before
                        F[k++]=t; // then add it
                }
        }

        C.WriteLine(k>=W); // result is whether we visited lots of cells
    }
}

Python 2 - 258 210 244 byte

Periksa path secara rekursif, jika stack overflow mengembalikan 1 (benar) lain kembali Tidak ada (falsey).

import sys
def k(s):
 a=len(s);m=[[c=='.'for c in b]*999for b in s.split('\n')]*999;sys.setrecursionlimit(a)
 for x in range(a*a):
  try:p(m,x/a,x%a)
  except:return 1
def p(m,x,y):
 if m[x][y]:m[x][y]=0;map(p,[m]*4,[x,x,x+1,x-1],[y+1,y-1,y,y])

Python 2 - 297 286 275 byte

Pilih sel "terbuka" yang sewenang-wenang untuk memulai pengisian banjir. Labirin tidak terbatas jika selama pengisian kita mengunjungi kembali sel yang sudah kita kunjungi, tetapi memiliki koordinat yang berbeda dengan kunjungan sebelumnya. Jika isi banjir memenuhi seluruh wilayah tanpa menemukan sel seperti itu, cobalah wilayah lain. Jika wilayah seperti itu tidak dapat ditemukan, labirin terbatas.

Membawa file untuk diproses pada baris perintah, mengembalikan kode keluar 1untuk tak terbatas, dan 0untuk terbatas.

Mengembalikan hasil yang benar untuk semua kasus uji.

import sys
e=enumerate
C=dict([((i,j),1)for i,l in e(open(sys.argv[1]))for j,k in e(l)if'.'==k])
while C:
 d={}
 def f(r,c):
  n=(r%(i+1),c%j)
  if n in d:return(r,c)!=d[n]
  if C.pop(n,0):d[n]=(r,c);return any(map(f,[r-1,r,r+1,r],[c,c+1,c,c-1]))
 if f(*C.keys()[0]):exit(1)