Woburn Challenge 2016-17 Round 3 - Senior Division

Problem 3: Puzzle Rooms

Among other things, the Pokémon series of video games is known for having interesting 2D puzzles for the player to solve. The latest installment, Pokémon Navy Green, is no exception!

As one of the game's level designers, you've been given the responsibility of turning N (1 ≤ N ≤ 50) different rooms into a series of puzzling challenges. However, rather than designing thought-provoking puzzles which would require careful solutions from the player, you'd much rather annoy them by crafting as tedious a gaming experience as possible.

The i-th room is a grid of cells with 4 rows and C_i (1 ≤ C_i ≤ 100) columns. You'll designate one of the cells to be the player's starting cell, and another one to be their destination. You may then choose some subset of the remaining cells to contain walls. The player's objective will then be to navigate from the starting cell to the destination cell by moving up, down, left, and right, without entering any cells that contain walls. Mazes are passable as puzzles, right?

Since your own objective is to make the players' lives miserable, you want to design each room in such a way that the shortest possible path from the starting cell to the destination cell is as long as possible. The distance covered by a path between two cells is the number of up/down/left/right moves that it involves. For each room, you'll need to determine the maximum possible length of such a shortest path, and come up with a room design (an arrangement of walls and starting/destination cells) which yields that optimal distance between its starting and destination cells. A room can be described as 4 strings of N characters each, with the j-th character of the i-th string representing the cell in the i-th row and the j-th column. The single starting cell should be indicated with an "S", the single destination cell with an "E", each wall with a "#", and each remaining empty cell with a ".". If there exist multiple optimal room designs, any of them will do.

In test cases worth 8/35 of the points, C_i ≤ 6.
In test cases worth another 8/35 of the points, C_i ≤ 12.

Input Format

The first line of input consists of a single integer N.
N lines follow, the i-th of which consists of a single integer C_i (for i = 1..N)

Output Format

For each room, output five lines. The first of these lines should consist of a single integer – the largest possible shortest distance between the starting and destination cells.
The last four of these lines shall describe any valid room design which yields that optimal distance.

Sample Input

2
2
3

Sample Output

5
S.
#.
..
E#
8
...
.#E
..#
..S

Sample Explanation

Note that, for both rooms, there exist other valid room designs (besides the ones shown here) which would also yield the same optimal distances of 5 and 8, and which would also be accepted.

All Submissions
Best Solutions

Point Value: 15 (partial)
Time Limit: 5.00s
Memory Limit: 16M
Added: Feb 19, 2017
Author: LordKlotski

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)