Problem Statement |
| | Introduction
You are collecting coins in a maze underground. Luckily for you, you have a
complete map of the maze that shows the locations of all the coins.
Unluckily, however, there has just been an earthquake and the maze is extremely
unstable. Sections of the maze are collapsing all the time. But, do not
despair because you also have drilling equipment which will allow you to go
through the rock (including clearing out collapsed sections).
Description
The maze is on a grid H units high and W units wide. On your map each cell is
described by one character:
- '#' blocked (rock)
- '.' open (passage)
- '*' open and contains a coin
- '^' open and is your initial position
You will start at an open cell on the left side of the map. At each time step,
you may move one cell to the left, right, up or down, provided that your
destination cell is open. If you want to open an adjacent blocked cell, it
will take T time steps to drill it out, after which you may move into it (for
T+1 total time steps).
At each time step, a collapse will occur with probability p. If a collapse
occurs, an open cell will be chosen uniformly at random from all open cells. A
breadth first search will then be performed from that location to a maximum
depth d randomly chosen in [0, D]. All those cells will become
blocked and any coins in those cells will be lost in the rubble. If you happen to
be in one of those cells, then your mission is over and you have failed (with
a score of 0).
All of the open cells on the edge of the map at the beginning of the simulation (either '.', '*' or '^') are escape cells (these will all be on the left and right sides of the map). You will start at one of them. If you ever move back to any one
(even if you have to drill it out due to a collapse), the simulation will end
as you escape with the coins you have collected thus far.
Implementation
You should implement two methods. The first method, init, takes a
String[] maze, specifying the initial state of the maze.
Each element of maze represents one row of the maze. Element 0
represents row 0 (the top). There will be exactly one row with a
'^' in the
leftmost column, which will denote the start. This function also takes the
parameter T. Your return from init will be ignored.
The second method, move, takes a int[] r
and a int[] c. These parameters indicate which cells, if
any, were open in the previous time step but now are blocked due to a
collapse. That is, for each i, the cell at row r[i] column
c[i] is now
blocked. This function will also takes
curR and curC, indicating your current
location. You should return your move/drill direction as an int.
0 indicates north (negative row), 1 east (positive column),
2 south and 3
west. If the direction you want to move would take you into a blocked cell,
you will not move, but will instead drill in that direction. Note that just
because you start drilling in one direction does not necessarily mean that you
need to finish drilling in that direction. A cell becomes unblocked when the
total amount of drilling it has experienced reaches T.
Maze Generation
W and H are first chosen randomly. Next, an R will be selected
uniformly in [1,3]. We will then independently perform the
following steps R times.
Pick a random location on the left side of the map.
Starting from this location, begin a random depth first search. That is, a
depth first search where the order of the four neighbors to visit is randomly
permuted. If a move would take us to a location which is adjacent to more than
one visited cell, we skip it (it will always be adjacent to at least one visited cell -- the current position). If a move would take us to the left, top or
bottom edge, we skip it. If there are no moves, we backtrack (leaving visited cells marked thus). Eventually, we
will reach the right side of the map. We will then prune away all of the
search that is not on the unique shortest path from the left side to the right
side. The open cells will be the union of the R depth first searches. Each
open cell has a coin in it with probability q, where q is a parameter of the
test case (see constraints).
Scoring
If you are crushed in a collapse or fail to escape for some other reason
(segfault, timeout, invalid return, etc.), your score for that test case will
be 0. Otherwise your score for an individual test case will be the
number of coins collected, divided by AVG * q, where AVG is the average
time taken (in 10 simulations) before every open cell in the map has
collapsed.
Visualizer
You may download a visualization tool at
http://www.topcoder.com/contest/problem/CollapsingMaze/vis.html.
|
| |
Definition |
| | | Class: | CollapsingMaze | | Method: | init | | Parameters: | String[], int | | Returns: | int | | Method signature: | int init(String[] maze, int T) | | | | Method: | move | | Parameters: | int[], int[], int, int | | Returns: | int | | Method signature: | int move(int[] colR, int[] colC, int curR, int curC) | | (be sure your methods are public) |
|
| |
|
| |
Notes |
| - | Some or all of the possible escape cells may collapse, but you still have to get to one of them. |
| - | Cells opened by drilling become eligible to collapse |
| - | The time limit is 20 seconds. |
| - | The memory limit is 1024MB. |
| - | The first example has been made artificial small for testing purposes. |
| - | There are 100 provisional test cases. |
| |
Constraints |
| - | All parameters are chosen uniformly at random in the ranges specified. |
| - | W and H in [100,1000] |
| - | T in [10,100] |
| - | D in [0,19] |
| - | p in [0,0.1] |
| - | q in [0,0.1] |
| |
Examples |
| 0) | |
| | | Returns:
"seed = 1<br>
T = 10<br>
W = 100<br>
H = 100<br>
D = 15<br>
p = 0.0<br>
q = 0.1<br>
" | In the maze below, the blue cell on the left denotes the start. The gold cells have coins in them. Note that there are four exit points here: two on the left and two on the right.
 |
|
|
| 1) | |
| | | Returns:
"seed = 2<br>
T = 24<br>
W = 362<br>
H = 210<br>
D = 15<br>
p = 0.055303806575227585<br>
q = 0.08780019518261352<br>
" | |
|
| 2) | |
| | | Returns:
"seed = 3<br>
T = 83<br>
W = 681<br>
H = 323<br>
D = 18<br>
p = 0.0548661956362973<br>
q = 0.08317885900480129<br>
" | |
|
| 3) | |
| | | Returns:
"seed = 4<br>
T = 79<br>
W = 651<br>
H = 986<br>
D = 2<br>
p = 0.058564166989575304<br>
q = 0.02001374685797388<br>
" | |
|
| 4) | |
| | | Returns:
"seed = 5<br>
T = 36<br>
W = 203<br>
H = 677<br>
D = 17<br>
p = 0.07970853015803138<br>
q = 0.09490294259728929<br>
" | |
|
| 5) | |
| | | Returns:
"seed = 6<br>
T = 65<br>
W = 159<br>
H = 812<br>
D = 5<br>
p = 0.033369073585745014<br>
q = 0.045186942516125796<br>
" | |
|
| 6) | |
| | | Returns:
"seed = 7<br>
T = 46<br>
W = 992<br>
H = 470<br>
D = 6<br>
p = 0.055533610841261474<br>
q = 0.06802483884497222<br>
" | |
|
| 7) | |
| | | Returns:
"seed = 8<br>
T = 69<br>
W = 290<br>
H = 141<br>
D = 8<br>
p = 0.02084588187989317<br>
q = 0.017591207458467862<br>
" | |
|
| 8) | |
| | | Returns:
"seed = 9<br>
T = 83<br>
W = 352<br>
H = 366<br>
D = 12<br>
p = 0.08888917594076315<br>
q = 0.024309811436622995<br>
" | |
|
| 9) | |
| | | Returns:
"seed = 10<br>
T = 84<br>
W = 612<br>
H = 713<br>
D = 1<br>
p = 0.08528507678047445<br>
q = 0.08388886092364066<br>
" | |
|
