Aquí hay un diagrama de una prisión con caracteres ASCII:
+------------------------------+
| |
| X X |
| |
| D
D |
| |
| |
| X X X |
| |
+------------------------------+
Las paredes están hechas de caracteres de tubería |
, guiones -
y pilares +
para esquinas e intersecciones. También hay dos puertas marcadas con D
(que siempre estarán en las paredes izquierda y derecha). La prisión está llena de gente aterradora marcada con X
.
El objetivo es construir muros para satisfacer lo siguiente:
- Cada persona está en confinamiento solitario;
- Hay un corredor que corre entre las dos puertas;
- Cada celda contiene exactamente una puerta, que está conectada directamente al corredor principal;
- Todo el espacio en la prisión es utilizado por las celdas y el corredor;
- Cada celda contiene una persona (es decir, no hay celdas vacías).
El corredor es un camino único, no se ramifica y siempre tiene un carácter de ancho. Aquí hay una solución para la prisión anterior:
+---------+--------------------+
| | |
| X | X |
| | +--------+
+------D--+-----D-----+ D
D +---D--+
+----D--------+---D-----+ |
| | | |
| X | X |X |
| | | |
+-------------+---------+------+
Puede suponer que cualquier prisión de entrada siempre tendrá una salida válida. Aquí hay algunas prisiones de entrada más, junto con posibles salidas:
+------------------------------+
|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--+ |
| |
+----------------+
Respuestas:
Python 2 ,
2986288129492135207520711996 bytesPruébalo en línea!
Fue golfing down significativamente; Sin embargo, todavía puede haber margen de mejora. Este código, sin embargo, resuelve todos los casos de prueba. No funciona de manera muy eficiente; Para grandes prisiones, el arquitecto puede tomarse su tiempo para resolverlo.
Utiliza un algoritmo de búsqueda de ruta simple para conectar las puertas y los prisioneros al corredor. Luego encapsula a todos los prisioneros y sus muros y empuja dichos muros en un espacio vacío hasta que se llena todo. Como paso final, se implementa la apariencia de arte ASCII.
Me tomó varias horas para escribir. Espero que también funcione en otras cárceles además de los casos de prueba. (No puedes probarlos a todos, ¿verdad?)
fuente
P
). Este no es un formato IO permitido. Debe usarinput()
o definir una función.C,
37323642 bytesDefinitivamente podría jugar golf un poco más lejos, pero es un buen comienzo. Inicialmente no sabía que mi enfoque tenía un nombre, así que agradezca a @TehPers por darme un nombre para investigar. Definitivamente disfruté el desafío que me ofreció esta pregunta. :)
-63 bytes de las sugerencias de @ Jonathan. También he sustituido
char
contypedef char R
y sustituye todos los caracteres literales que son menores que 100 con sus valores ASCII para un total de 90 bytesUna explicación rápida de mi código.
Para usar este programa, pase el mapa como una cadena con caracteres de nueva línea o con cada nivel separado por un espacio como en el siguiente ejemplo.
código
fuente
free(t);free(u);
al final de su programa. Además,'\0'
es igual a0
guardar otros 3 bytes.typedef int Q;
y reemplaza todas las apariciones deint
conQ
, puede guardar otros 44 bytes.