Berikut adalah diagram penjara yang menggunakan karakter ASCII:

+------------------------------+
|                              |
|   X               X          |
|                              |
|                              D
D                              |
|                              |
|                              |
|        X           X   X     |
|                              |
+------------------------------+

Dinding terbuat dari karakter pipa |, tanda hubung -, dan pilar +untuk sudut dan persimpangan. Ada juga dua pintu yang ditandai D(yang akan selalu ada di dinding kiri dan kanan). Penjara dipenuhi dengan orang-orang menakutkan yang ditandai X.

Tujuannya adalah untuk membangun tembok untuk memenuhi hal-hal berikut:

1. Setiap orang berada di sel isolasi;
2. Ada koridor yang membentang di antara dua pintu;
3. Setiap sel berisi tepat satu pintu, yang terhubung langsung ke koridor utama;
4. Semua ruang di penjara digunakan oleh sel dan koridor;
5. Setiap sel berisi seseorang (yaitu, tidak ada sel kosong).

Koridor adalah jalur tunggal, tidak bercabang, dan selalu lebar satu karakter. Inilah solusi untuk penjara di atas:

+---------+--------------------+
|         |                    |
|   X     |         X          |
|         |           +--------+
+------D--+-----D-----+        D
D                       +---D--+
+----D--------+---D-----+      |
|             |         |      |
|        X    |      X  |X     |
|             |         |      |
+-------------+---------+------+

Anda dapat mengasumsikan bahwa setiap penjara input akan selalu memiliki output yang valid. Berikut adalah beberapa penjara input, bersama dengan kemungkinan keluaran:

+------------------------------+
|X X X X X X X X X X X X X X X |
|                              |
D                              D
|                              |
|              X               |
+------------------------------+

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+
|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X |
+D+D+D+D+D+D+D+D+D+D+D+D+D+D+D-+
D                              D
+----------------------D-------+
|              X               |
+------------------------------+

+-----------+
|X          |
|           |
|           |
|X         X|
|           |
|          X|
|           |
D           D
+-----------+

+-+-------+-+
|X|       D |
| D +---+ | |
+-+ |     | |
|X| | +---+X|
| | | |   +-+
| D | |    X|
+-+ | +-D---+
D   |       D
+---+-------+

+----------------+
|X    X    X    X|
|                |
D                |
|                |
|X    X    X     |
|                |
|                |
|                |
|     X    X     D
|                |
|                |
+----------------+

+---+---+----+---+
|X  | X |  X |  X|
+--D+--D+---D+--D+
D                |
+---+---+------+ |
|X  | X |  X   | |
+--D+--D+---D--+ |
|                |
| +-----+------+-+
| |   X |  X   | D
| +----D+---D--+ |
|                |
+----------------+

Python 2 , 2986 2881 2949 2135 2075 2071 1996 byte

• Disimpan 105 byte, mengimplementasikan program sebagai fungsi untuk mematuhi aturan standar. Tab dan saran ruang Wheat Wizard yang diterapkan.
• Ditambahkan 68 byte karena memperbaiki bug.
• Disimpan 814 + 51 byte berkat Halvard Hummel.
• Disimpan 9 + 4 byte.
• Disimpan 4 byte berkat Erik the Outgolfer.
• Disimpan 71 byte berkat saran ppperry.

exec r"""def Z(P):
 H,n,I,o,O,i,d,D,W=[type,range]+list(" dD#xX*");R=(1,0),(-1,0),(0,1),(0,-1)
 def F(j,k,l):P[j][k]=l
 def E(j,k,v,w):
	if G(j,k,v):F(k,j,w)
 def q(b,c,d):[[E(j+J,k+K,b,c)for J,K in M]&L if G(j,k,d)]
 def A(e,r,l,o,q):
	S,E,P[q][o],Q,X=P[q][o],e,0,[(o,q)],0
	for a,b in Q:
	 &R:
		x,y=a+j,b+k
		if(0<=x<w!=0<=y<h)<1:continue
		if e in((x,y),P[y][x]):X=1;e=x,y;break
		if I!=P[y][x]:continue
		F(y,x,P[b][a]+1);Q+=[(x,y)]
	 if X:break
	p,i=e,0
	while(o,q)!=p:
	 a,b=p;P[b][a],m=[r,l][l and i==1],0
	 &R:
		x,y=a+j,b+k
		if(0<=x<w!=0<=y<h)-1:continue
		if(H(P[y][x])==H(0))*(m==0 or P[y][x]<P[m[1]][m[0]]):m=x,y
	 p=m;i+=1
	P[q][o],P[e[1]][e[0]]=S,E;[F(k,j,I)&L if H(P[k][j])==H(0)]
 def B(N):
	[[E(j,k,"x*",I),0<j<w-1 and E(j,k,O,I)]&L]
	&L:
	 if G(j,k,D):[E(j+J,k+K,I,d)for J,K in M]
	 if G(j,k,O)and j==0:T=0,k
	if N:A(O,o,0,*T)
	U,V=M[-1];[[[F(k+K,j+J,I)for J,K in M if(P[k+K][j+J]!=i)*((0<=j+J+U<w!=0<=k+K+V<h and G(j+J+U,k+K+V,D))<1)],F(k,j,W),A(o,W,O,j,k),q(I,d,W),F(k,j,D)]&L if G(j,k,D)];q("xX*# @+-|",i,o)
 for j in"|+-":P=P.replace(j,i)
 P=list(map(list,P.split("\n")));h=len(P);w=len(P[0]);b,L,M,G="#+-|D",[(k,j)for k in n(w)for j in n(h)],[(k-1,j-1)for k in n(3)for j in n(3)if(j,k)!=(1,1)],lambda j,k,v:P[k][j]in v
 B(1);Y=lambda:0<j<w-1!=0<k<h-1and G(j,k,i);[[[F(k,j,o),F(k+g,j+N,i)]for N,g in((-1,-1),(-1,1),(1,-1),(1,1))if P[k][j+g]+P[k][j-g]==P[k+N][j+g]+P[k-N][j]==P[k+N][j]+i==o+i]&L if(j in(1,w-2)or k in(1,h-2))*Y()for N in n(w*h)];[F(k,j,I)&L if Y()];B(0)
 def c(x,y,b,l,d,f,Q):
	F(y,x,b)
	for J,K in M:Q+=[[],[(x+J,y+K)]][G(x+J,y+K,l)];E(x+J,y+K,d,f)
 &L:
	if G(j,k,D):Q=[(j,k)];[c(x,y,"@",W,d,I,Q)for x,y in Q if G(x,y,"X*")];[G(u,v,"X*")and[E(u+U,v+V,I,d)for U,V in M]or E(u,v,"@",I)for u,v in L];Q=Q[:1];[c(x,y,"$",I,"x*",i,Q)for x,y in Q];F(k,j,D)
 &L:E(j,k,"@$d",I);X=(k>0and G(j,k-1,b))+(k<h-1and G(j,k+1,b))-(j>0and G(j-1,k,b))-(j<w-1and G(j+1,k,b));E(j,k,i,{2:"+",X:"|",-X:"-"}[2])
 print"\n".join("".join(p)for p in P)""".replace("&","for j,k in ")

Cobalah online!

Itu golf turun secara signifikan; namun mungkin masih ada ruang untuk perbaikan. Namun, sepotong kode ini menyelesaikan semua kasus uji. Tidak berjalan sangat efisien; untuk penjara besar, arsitek dapat meluangkan waktu untuk mencari tahu.
Menggunakan algoritma penelusuran jalan sederhana untuk menghubungkan kedua pintu dan tahanan ke koridor. Kemudian itu merangkum semua tahanan dan dinding mereka dan mendorong dinding tersebut di ruang kosong sampai semuanya terisi. Sebagai langkah terakhir, penampilan seni ASCII diimplementasikan.

Butuh beberapa jam untuk menulis. Saya harap ini juga bekerja di penjara lain selain kasus uji. (Anda tidak dapat menguji semuanya, bukan?)

C, 3732 3642 byte

Saya pasti bisa bermain golf ini sedikit lebih jauh, tetapi ini adalah awal yang cukup bagus. Awalnya saya tidak tahu bahwa pendekatan saya memiliki nama, jadi berteriaklah ke @TehPers karena memberi saya nama untuk diteliti. Saya benar-benar menikmati tantangan yang ditawarkan pertanyaan ini. :)

-63 byte dari saran @ Jonathan. Saya juga diganti chardengan typedef char Rdan diganti semua karakter literal yang lebih kecil dari 100 dengan nilai ASCII mereka untuk total 90 bytes

Penjelasan cepat tentang kode saya.

1. Konversi array char ke array integer yang ideal (0 adalah spasi, 1 adalah dinding, dll.)
2. Hasilkan diagram Voronoi menggunakan orang-orang sebagai titik
3. Gunakan persimpangan (a 5 dikelilingi oleh setidaknya tiga 5s lainnya) sebagai titik pivot untuk jalur
4. Buat koridor menggunakan algoritma pencarian arah yang bias arah (jika arahnya satu arah, pilih jalur yang tidak mengubah arah). Itu juga memodifikasi grid sehingga lebih suka bepergian di sebelah koridor yang sudah dibuat.
5. Regenerasi diagram untuk menempatkan dinding akhir. Memastikan bahwa semua ruang digunakan.
6. Konversi peta kembali ke representasi ASCII yang diformat dengan benar dan cetak.

Untuk menggunakan program ini, berikan peta sebagai string dengan karakter baris baru atau dengan setiap level yang dipisahkan oleh spasi seperti pada contoh berikut.

program-name.exe "+-----------+ |X          | |           | |           | |X         X| |           | |          X| |           | D           D +-----------+ "

+------+----+
|X     |    |
|    +D+-+  |
+----+   |  |
|X   | + D X|
|    | | +--+
|    | | | X|
+D---+ | +-D+
D      |    D
+------+----+

kode

typedef int Q;typedef char R;typedef struct{Q x,y,v;}P;w,h,A,Y,Z,x,y,i,j,e,f,m,n,v;P*t,*u,*s;I(R*a,Q x,Q y,R c){a[x+y*w]=c;}G(Q*a,Q x,Q y){if(x>-1&&x<w&&y>-1&&y<h)return a[x+y*w];return-1;}J(Q*a,Q x,Q y,Q c){a[x+y*w]=c;}P*E(Q n,Q*a,Q*c){P*r=0;for(i=v=0;i<A;i++)if(a[i]==n)r=(P*)realloc(r,sizeof(P)*(v+1)),r[v].x=i%w,r[v].y=i/w,r[v].v=v,*c=++v;return r;}C(Q*a,Q x,Q y,Q b){return(G(a,x-1,y)==b)+(G(a,x+1,y)==b)+(G(a,x,y-1)==b)+(G(a,x,y+1)==b);}H(Q*a,Q b){P q[A],r[A];m=Y,n=0;for(i=0;i<Y;i++)q[i]=t[i];while(m){while(m){x=q[m-1].x,y=q[m-1].y,v=q[m-1].v;i=G(a,x,y);if(i!=b&&i!=1){for(f=-1;f<2;f++){for(e=-1;e<2;e++){i=G(a,x+e,y+f);if(i==0){J(a,x+e,y+f,v+8);r[n].x=x+e;r[n].y=y+f;r[n].v=v;n++;}else if(i>=8&&i!=v+8)J(a,x+e,y+f,b);}}}m--;}for(i=0;i<n;i++)q[i]=r[i];m=n;n=0;}}B(P p,Q*a,Q*b){for(i=m=n=0;i<A;i++)if(b[i]>-2)b[i]=-1;P q[A],r[A];q[0]=p,q[0].v=0,b[p.x+p.y*w]=0;while(m+1){while(m+1){x=q[m].x,y=q[m].y,v=q[m].v;for(f=-1;f<2;f++){for(e=-1;e<2;e++){if(e!=0&&f!=0||(x+e<0||x+e>=w||y+f<0||y+f>=h))continue;i=G(a,x+e,y+f);if(i!=7&&i!=1&&i!=0){j=3;if(i==4||i==5)j=1;if(x+e!=p.x&&y+f!=p.y)j++;Q*p=&b[x+e+(y+f)*w];if(*p!=-2&&(*p==-1||*p>v+j)){*p=v+j;if(i!=2)r[n].x=x+e,r[n].y=y+f,r[n].v=v+j,n++;}}}}m--;}for(i=0;i<n;i++){q[i]=r[i];}m=n-1,n=0;}}D(P S,P*T,Q n,P U,Q*a){Q m[A];Q x,y,v=0,c=0,d=1,d1=1;for(i=0;i<n;i++)T[i].v=0;for(i=0;i<A;i++)m[i]=-1;x=S.x,y=S.y;if(n==0){B(U,a,m);goto fin;}while(v<n){j=-1;for(i=0;i<n;i++)if(T[i].v==0)if(j==-1||abs(T[i].x-x)+abs(T[i].y-y)-(T[i].x==x)*!d*2-(T[i].y==y)*d*2<abs(T[j].x-x)+abs(T[j].y-y)-(T[j].x==x)*!d*2-(T[j].y==y)*d*2)j=i;T[j].v=1;B(T[j],a,m);fin:v++;c=m[x+y*w];while(c>0||c==-1){Q tx,ty;j=-1;for(f=-1;f<2;f++){for(e=-1;e<2;e++){if(e!=0&&f!=0)continue;if(x+e<0||x+e>=w||y+f<0||y+f>=h)continue;i=G(m,x+e,y+f);if(i>-1&&(i<c||c==-1)){if(j==-1||j>i||((e*d||f*!d)&&j==i)){j=i;tx=x+e,ty=y+f;d1=e!=0;}}}}J(m,x-1*!d1,y-1*d1,-2);J(m,x+1*!d1,y+1*d1,-2);d=d1;x=tx,y=ty,c=j;if(G(a,x,y)!=2)J(a,x,y,0);}for(f=0;f<h;f++)for(e=0;e<w;e++)if((i=G(a,e,f))>3&&i!=7)if(C(m,e,f,-2))J(a,e,f,5);if(v==n){B(U,a,m);goto fin;}}}main(Q c,R**v){R*a=v[1];w=strchr(a,'|')-a;h=(strchr(a+w,43)-a)/w+1;A=w*h;Q p[A];for(y=0;y<h;y++)for(x=0;x<w;x++){c=a[x+y*w];J(p,x,y,0);if(c==45||c=='|'||c==43)J(p,x,y,1);if(c==68)J(p,x,y,2);if(c==88)J(p,x,y,3);}t=E(3,p,&Y);u=E(2,p,&Z);H(p,5);for(c=0;c<Y;c++)for(y=-1;y<2;y++)for(x=-1;x<2;x++)if(G(p,t[c].x+x,t[c].y+y)>=4)J(p,x+t[c].x,y+t[c].y,7);for(y=1;y<h-1;y++)for(x=1;x<w-2;x++)if(G(p,x,y)==5)if(C(p,x,y,5)>2)J(p,x,y,4);s=E(4,p,&c);for(i=0;i<c;i++)s[i].v=0;for(y=1;y<h-1;y++)for(x=1;x<w-2;x++)if(G(p,x,y)>=8)if(C(p,x,y,5))J(p,x,y,4);i=u[0].x!=0;D(u[i],s,c,u[!i],p);for(y=0;y<h;y++){for(x=0;x<w;x++){i=0;if(G(p,x,y)>2){for(f=-1;f<2;f++)for(e=-1;e<2;e++)i+=G(p,x+e,y+f)==0;if(i>0)J(p,x,y,6);}}}free(s);for(i=0;i<A;i++)if(p[i]>=7||p[i]==4||p[i]==5)p[i]=0;for(y=0;y<h;y++){for(x=0;x<w-1;x++){if((x==0||x==w-2||y==0||y==h-1)&&G(p,x,y)!=2)J(p,x,y,1);}}H(p,1);P q[A],r[A];for(i=0;i<Y;i++){m=1,n=0;q[0]=t[i];while(m){while(m){x=q[m-1].x,y=q[m-1].y;for(f=-1;f<2;f++){for(e=-1;e<2;e++){if(e!=0&&f!=0)continue;c=G(p,x+e,y+f);if(c==6){if(G(p,x+e*2,y+f*2)==0){J(p,x+e,y+f,2);m=1,n=0;e=f=2;}}else if(c!=1&&c!=3&&c!=7){J(p,x+e,y+f,7);r[n].x=x+e;r[n].y=y+f;n++;}}}m--;}for(c=0;c<n;c++)q[c]=r[c];m=n;n=0;}}for(i=0;i<A;i++)if(p[i]==6)p[i]=1;R b[A];for(y=0;y<h;y++){for(x=0;x<w;x++){c=G(p,x,y);I(b,x,y,32);if(c==1){i=0;if(G(p,x,y-1)==1||G(p,x,y-1)==2)i|=1;if(G(p,x,y+1)==1||G(p,x,y+1)==2)i|=2;if(G(p,x-1,y)==1||G(p,x-1,y)==2)i|=4;if(G(p,x+1,y)==1||G(p,x+1,y)==2)i|=8;if(i==3)I(b,x,y,'|');else if(i==12)I(b,x,y,45);else I(b,x,y,43);}if(c==2)I(b,x,y,68);if(c==3)I(b,x,y,88);if(x==w-1)I(b,x,y,10);}}b[A-1]=0;puts(b);}