What is the worst possible maze if we are using BFS to solve it?
In this problem you’ll need to come close enough to the answer to that question.
We have an infinite grid of unit square cells. Two cells are considered adjacent if they share a common side.
In our grid, a maze of size \(n\) is a collection of exactly \(n\) distinct cells that form a tree. (That is, you get a tree if you build the graph whose vertices are the cells that form the maze and whose edges connect adjacent pairs of cells.)
One algorithm we can use when trying to get from cell A to cell B in a maze is breadth-first search (BFS).
We will consider a specific BFS implementation in which the neighbors of each cell are traversed in row major order. I.e., from cell \((r, c)\) we first try moving up to \((r-1, c)\), then left to \((r, c-1)\), then right to \((r, c+1)\), and finally down to \((r+1, c)\).
Here’s the full pseudocode of this BFS.
DIRECTIONS = [ (-1,0), (0,-1), (0,1), (1,0) ]
function BFS ( starting cell A, target cell B ):
initialize all distances to infinity
set distance[A] = 0
put A into the queue
repeat:
take a cell X from the queue
if X = B, terminate
for each direction in DIRECTIONS:
let Y be the neighboring cell to X in that direction
if Y exists and is empty (i.e., belongs to the maze):
if distance[Y] is infinity:
set distance[Y] to distance[X]+1
put Y into the queueIt should be obvious that for any maze and any pair of its cells A
and B the above algorithm will terminate (and at that moment
distance[B] will be the shortest distance from A to B).
It should also be obvious that the running time of the algorithm is proportional to the number of cells it visited. (These are the cells that were put into the queue during the algorithm’s execution. Equivalently, these are the cells that had a finite distance when the algorithm terminated.)
Given a maze \(M\) and two of its cells \(A\) and \(B\), we will denote the number of cells visited by BFS(A,B) as \(runtime(M,A,B)\).
Note that for any maze and any cell \(A\) we have \(runtime(M, A, A) = 1\).
For a maze \(M\) with \(n\) cells, we can define \(quality(M)\) as the sum of all \(n^2\) values \(runtime(M, A, B)\). That is, we are summing over all ordered pairs of cells \((A, B)\) in the maze.
Find a maze with the following properties:
Resubmissions for this problem do not generate penalty minutes.
(Note that the 20-submission limit is still in place.)
There is no input.
Output a drawing of your maze.
The first line of output should contain the dimensions \(r\) and \(c\) of a rectangle that contains your maze, with \(1\leq r,c\leq 300\).
The rest of your output should consist of \(r\) lines, each containing \(c\) characters that form a bitmap of the maze. Use ‘#’ (hash) for cells that do not belong to the maze and ‘.’ (period) for cells that do.
If \(q\) is the quality of your maze, your score is computed using the following formula:
\(s = 2\Big((q~\mathop{\rm div}~10^8) - 626\Big)\)
\(score = \max(0, \min(100, s ))\)
That is, you’ll get a positive score for any maze with \(q\geq 627\times 10^8\), you’ll get a full score for any maze with \(q\geq 676\times 10^8\), and the score of any submission is always an even integer.
It is guaranteed that the best mazes exceed the threshold needed for 100 points.
Output file: S0_example.out
The file linked above is a syntactically valid submission containing a very simple maze with 5000 cells in the shape of a spiral. The exact quality of this maze is \(62\,524\,992\,564\).
Note that submitting the above file would give you zero points, as its quality is too low to score any points.