IPSC 2018 Problem J – Jumping over walls

IPSC 2018

Problem J – Jumping over walls

This problem has no input files.

You have always been an avid fan of mazes, and a bit of a cheater. No wonder you came up with a peculiar device that can be used to cheat in a maze. You will simply select a direction and the device will help you jump over all walls in your way, all the way to the nearest empty space in the chosen direction.

You have built two prototypes of the device. Prototype J1 only allows you to choose the 4 cardinal directions for jumping. Prototype J2 also lets you jump diagonally, so you have 8 available directions for each jump.

You would like to start manufacturing more of these devices – many maze fans would love to have one! But before you sell them, you need to test each of them to make sure you don’t damage your brand by selling defective pieces. You decided that you’ll build a test maze for those tests.

Problem specification

You will be constructing two separate test mazes: one for the J1 device and one for the J2 device. The purpose of the test maze is to make sure that the device jumps correctly in all supported directions, so it must be impossible to solve the maze without using every direction at least once. Constructing mazes costs money, so you must make them as small as possible.

While in the maze, you will only move using the device, never by walking. But note that the device is also able to jump over zero walls – if the very next cell in that direction is empty, you will just jump to that cell.

Each test maze must have the following properties:

The maze is on a rectangular grid. The area of the rectangle must be as small as possible.
Some cells are walls (denoted #), others are empty (denoted .).
There is exactly one start cell (denoted A) and exactly one target cell (denoted B). Both are considered empty. They may be located anywhere in the maze.
We assume that the maze is surrounded by an infinite grid of walls and jumping outside is impossible.
It must be possible to travel from A to B.
It must be impossible to travel from A to B without using each of the available directions at least once.

The easy subproblem J1 is to construct a testing maze for the J1 prototype (4 directions), the hard subproblem J2 is to do the same for the J2 prototype (8 directions).

Input specification

There is no input.

Output specification

The first line of your output should contain two integers: the number of rows r and the number of columns c in your maze. The value r × c must be as small as possible.

The rest of your output should contain the map of the maze: r lines, each with c characters as specified above.

Example

Output:

5 6
......
.#.#.B
###...
#A#...
#.#...

This is a syntactically correct output but it doesn’t describe a good test maze. This is because you could solve this maze without ever making a jump down. (For example, you can make three jumps right followed by two jumps up.)

Note that if you had the J2 prototype and started this maze at A, you would have exactly four possibilities for your first jump:

Select the direction “down” and jump by 1.
Select the direction “up” and jump by 3.
Select the direction “right” and jump by 2.
Select the direction “diagonally up and right” and jump by 3.