Here is a diagram of a prison using ASCII characters:
+------------------------------+
| |
| X X |
| |
| D
D |
| |
| |
| X X X |
| |
+------------------------------+
Walls are made out of pipe characters |
, dashes -
, and pillars +
for corners and intersections. There are also two doors marked with D
(which will always be on the left and right walls). The prison is filled with scary people marked with X
.
The goal is to build walls to satisfy the following:
- Each person is in solitary confinement;
- There is a corridor running between the two doors;
- Each cell contains exactly one door, which is directly connected to the main corridor;
- All space in the prison is used by the cells and the corridor;
- Each cell contains a person (that is, there are no empty cells).
The corridor is a single path, doesn't branch off, and is always one character wide. Here's a solution for the prison above:
+---------+--------------------+
| | |
| X | X |
| | +--------+
+------D--+-----D-----+ D
D +---D--+
+----D--------+---D-----+ |
| | | |
| X | X |X |
| | | |
+-------------+---------+------+
You can assume that any input prison will always have a valid output. Here are some more input prisons, along with possible outputs:
+------------------------------+
|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--+ |
| |
+----------------+