forked from keshavnandan/Topcoder
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathDungeonEscape.html
160 lines (159 loc) · 13.6 KB
/
DungeonEscape.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
<html><body bgcolor="#000000" text="#ffffff"><table><tr><td colspan="2"><h3>Problem Statement</h3></td></tr><tr><td>    </td><td><p>You are the famous explorer Indiana Jones, or Lara Croft, take your pick. You are exploring the ruins of the dungeons beneath King Lockumup IV the Good's castle in Flatlandia. Of course, the dungeon layout is two-dimensional (like your character), East-West and Up-Down in this case, in a regular grid.
</p>
<pre>
Surface
| | | | | | | | |
level 0 -R-R-R-R-R-R-R-R-R-
| | | | | | | | |
level 1 <- West -R-R-R-R-R-R-R-R-R- East ->
| | | | | | | | |
level 2 -R-R-R-R-R-R-R-R-R-
| | | | | | | | |
Depths of Despair
</pre>
<p> "R" indicates a room. "-" indicates an east-west passageway. "|" indicates an up-down passageway.
</p>
<p>
Because it is rough going in the passageways between the rooms (there has been no dungeon maintenance for centuries), it is frequently easier to travel through a passageway in a particular direction than in the opposite direction. Each room has four passageways leaving in the directions East (right), West (left), Up, and Down which lead to adjacent rooms (except the Down in the bottom-most rooms, the East in the east-most rooms, and the West in the west-most rooms, which have dead-end passageways due to ancient budget cuts, and Up in the topmost rooms which lead to the surface). The time it takes to travel through a passageway from a given room to the adjacent rooms is given in four vector <string>s depending on your direction of travel. A digit between 0 and 9 indicates how many time units (in the local system of decimillifortnights, dmfs) are taken to leave the room in that direction and travel through the passageway to the adjacent room. An 'x' character indicates that the travel in that direction is too difficult and can not be done. The dead end passageways (at the edges of the dungeon) have time values, or 'x', specified (because they were in the original plans for the dungeon and we have an old map), but we can not actually travel through these passageways in this problem. The dungeon does *not* wrap in any direction (you are probably thinking of the castle of Queen Mobius the One Sided, the former stripper).
</p>
<p> In other words, if you are in room (i,j), where i is the up-down level and j is your easting (ie. how far east you are) coordinate,
then </p>
<ul>
<li><b>up</b>[i][j] tells how many dmfs it takes to get to (i-1,j).</li>
<li><b>down</b>[i][j] tells how many dmfs it takes to get to (i+1,j).</li>
<li><b>east</b>[i][j] tells how many dmfs it takes to get to (i,j+1).</li>
<li><b>west</b>[i][j] tells how many dmfs it takes to get to (i,j-1).</li>
</ul>
<p>If it is obvious to you how these four directional time value arrays map to
a directed graph of the dungeon, then skip this next section of the problem
description, which goes into detail, and continue reading below for more
of the important problem description information.</p>
<ul><li>
<p> For example if given the inputs <b>up</b> and <b>west</b> (shown below)</p>
<pre>
up = {"123", west = {"222",
"111", "131",
"121"} "444"}
</pre>
You would have the following time values for each passageway while going up or west.
<pre>
Surface
1 2 3
level 0 2R2R2R- Up and West going
1 1 1 Passageway times
level 1 West 1R3R1R- East
1 2 1
level 2 4R4R4R-
| | |
Depths of Despair
</pre>
<p>The dead-end passageways on the far west with times {2, 1, 4} are useless and can be ignored.</p>
<br></br>
<p>Similarly if you have the inputs <b>down</b> and <b>east</b> (shown below)</p>
<pre>
down = {"987", east = {"222",
"111", "3x3",
"121"} "111"}
</pre>
You would have the following time values for each passageway while going down or east.
<pre>
Surface
| | |
level 0 -R2R2R2 Down and East going
9 8 7 Passageway times
level 1 West -R3RxR3 East
1 1 1
level 2 -R1R1R1
1 2 1
Depths of Despair
</pre>
<p>The dead-end passageways on the far east with times {2, 3, 1} and the very bottom with times {1, 2, 1} are also
useless to you and can be ignored.</p>
</li></ul>
<p>We are back from the boring details, here is some more important information.</p>
<p>
Unfortunately for you, Dr. Jones or Dr. Croft, you have just triggered an ancient trap, and the dungeon is beginning to to fill with water. First the lowest level fills with water. If the East-West width of the dungeon is n rooms, then each level of the dungeon takes n decimillifortnights to fill. Once full of water, the rooms on that level are no longer accessible. While partly full of water, they are still fully accessible. Time starts at time = 0, at time = n the lowest level becomes inaccessible, at time = 2n the second lowest level becomes inaccessible, etc. So if you are in, or pass through, a room on the lowest level at time >= n, you are dead.
</p>
<p>For simplicity, we will only consider if the room is completely filled with water when you enter. So if you leave a nearly filled room, going up through a slow
passageway, and arrive somewhat later in a now nearly filled room one level up, this is ok. We will ignore the physics which would lead us to think the passageway would fill with water before the room above it. Only check for drowning when you enter the room. Also the surface (above level 0) never fills with water (we run out of water before then), so you can not drown on the surface.
</p>
<p>
Your goal is to get to the surface as fast as possible. You start at the location (<b>startLevel</b>, <b>startEasting</b>). "Easting" is how far east you are in the local coordinate system. Rooms have Easting coordinates between 0 and n-1 inclusive, where
n is the number of rooms on each level. Return the number of time units (decimillifortnights) it takes to escape, or -1 if escape is impossible.
</p>
<p>For example:</p>
<pre>
<b>up</b> = {"0x4", <b>down</b> = {"0x9", <b>east</b> = {"1x9", <b>west</b> = {"0x9",
"0x3", "009", "0x9", "0x0",
"0x3"} "0x9"} "009"} "009"}
<b>startLevel</b> = 2, <b>startEasting</b> = 2
</pre>
<p>
We start in the lower right corner. If water were not an issue, we could reach each of the various rooms
with various paths, and the earliest possible times in which we could reach each room are shown below. If we go straight up,
the passageways take 3, 3 and 4 dmfs reaching the surface in 10 dmfs. We could also follow the path: up (3 dmfs), west (0 dmfs),
down (0 dmfs), west (0 dmfs), up (0 dmfs), up (0 dmfs), and up (0 dmfs) reaching the surface in 3 dmfs. The diagram
below shows the minimum time in which we could first get to each room (if water were not an issue), and the
passageways used are shown with '|' for up-down, and '-' for east-west.
</p>
<pre>
3 10 - surface
| | -------------
3-4 6 - level 0
| |
3 3-3 - level 1
| | |
3-3 0 - level 2
</pre>
<p> But since level 2 fills with water at time 3, we can not move from (1,1) down to (2,1) at time = 3 dmfs. The
actual rooms we can reach, considering flooding, are shown below, where 'w' represents a room which is full of water
when we first could move into it, and 'x' represents a room we can never reach:</p>
<pre>
10 - surface
| ------------
x w-6 - level 0
|
x 3-3 - level 1
| |
x w 0 - level 2
</pre>
<p>
In this example we can reach the surface in 10 dmfs by going straight up, and this is the minimum,
so return 10.
</p></td></tr><tr><td colspan="2"><h3>Definition</h3></td></tr><tr><td>    </td><td><table><tr><td>Class:</td><td>DungeonEscape</td></tr><tr><td>Method:</td><td>exitTime</td></tr><tr><td>Parameters:</td><td>vector <string>, vector <string>, vector <string>, vector <string>, int, int</td></tr><tr><td>Returns:</td><td>int</td></tr><tr><td>Method signature:</td><td>int exitTime(vector <string> up, vector <string> down, vector <string> east, vector <string> west, int startLevel, int startEasting)</td></tr><tr><td colspan="2">(be sure your method is public)</td></tr></table></td></tr><tr><td colspan="2"><h3>Limits</h3></td></tr><tr><td>    </td><td><table><tr><td>Time limit (s):</td><td>2.000</td></tr><tr><td>Memory limit (MB):</td><td>64</td></tr></table></td></tr><tr><td colspan="2"><h3>Constraints</h3></td></tr><tr><td align="center" valign="top">-</td><td><b>up</b>, <b>down</b>, <b>east</b> and <b>west</b> have the same constraints, only <b>up</b> is described.</td></tr><tr><td align="center" valign="top">-</td><td><b>up</b> will contain between 1 and 50 elements inclusive.</td></tr><tr><td align="center" valign="top">-</td><td>each element of <b>up</b> will contain between 1 and 50 characters inclusive.</td></tr><tr><td align="center" valign="top">-</td><td>each character in each element of <b>up</b> will be a digit between '0' and '9' inclusive or 'x'.</td></tr><tr><td align="center" valign="top">-</td><td><b>up</b>, <b>down</b>, <b>east</b> and <b>west</b> will all have exactly the same number of elements in each.</td></tr><tr><td align="center" valign="top">-</td><td>All elements of <b>up</b>, <b>down</b>, <b>east</b> and <b>west</b> will contain the same number of characters.</td></tr><tr><td align="center" valign="top">-</td><td><b>startLevel</b> will be between 0 and (the number of elements in <b>up</b>) - 1 inclusive.</td></tr><tr><td align="center" valign="top">-</td><td><b>startEasting</b> will be between 0 and (the number of characters in <b>up</b>[0]) - 1 inclusive.</td></tr><tr><td colspan="2"><h3>Examples</h3></td></tr><tr><td align="center" nowrap="true">0)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{"0x4",
"0x3",
"0x3"}</pre></td></tr><tr><td><pre>{"0x9",
"009",
"0x9"}</pre></td></tr><tr><td><pre>{"0x9",
"1x9",
"009"}</pre></td></tr><tr><td><pre>{"0x9",
"0x0",
"009"}</pre></td></tr><tr><td><pre>2</pre></td></tr><tr><td><pre>2</pre></td></tr></table></td></tr><tr><td><pre>Returns: 10</pre></td></tr><tr><td><table><tr><td colspan="2">The example from above. </td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">1)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{"xxxxxxxxx1",
"1xxxxxxxxx",
"xxxxxxxxx1"}</pre></td></tr><tr><td><pre>{"xxxxxxxxxx",
"xxxxxxxxxx",
"xxxxxxxxxx"}</pre></td></tr><tr><td><pre>{"1111111111",
"xxxxxxxxxx",
"1111111111"}</pre></td></tr><tr><td><pre>{"xxxxxxxxxx",
"1111111111",
"xxxxxxxxxx"}</pre></td></tr><tr><td><pre>2</pre></td></tr><tr><td><pre>0</pre></td></tr></table></td></tr><tr><td><pre>Returns: 30</pre></td></tr><tr><td><table><tr><td colspan="2">Only one serpentine path out, just avoiding the water.</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">2)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{"xxxxxxxxx1",
"xxxx999991",
"x999999991"}</pre></td></tr><tr><td><pre>{"1111111111",
"1111111111",
"1111111111"}</pre></td></tr><tr><td><pre>{"1111122242",
"2222222241",
"2111111111"}</pre></td></tr><tr><td><pre>{"xxxxxxxxx1",
"1111111111",
"xxxxxxxxx1"}</pre></td></tr><tr><td><pre>2</pre></td></tr><tr><td><pre>0</pre></td></tr></table></td></tr><tr><td><pre>Returns: -1</pre></td></tr><tr><td><table><tr><td colspan="2">No way out that is fast enough, glub, glub...</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">3)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{"1x2x3x4x5x6x7x8x9",
"00000000000000000",
"98765432223456789",
"12345678987654321"}</pre></td></tr><tr><td><pre>{"00000000000000000",
"00000000000000000",
"00000000000000000",
"00000000000000000"}</pre></td></tr><tr><td><pre>{"xxxxxxxxxxxxxxxxx",
"xxxxxxxxxxxxxxxxx",
"22222222222222222",
"33333333333333333"}</pre></td></tr><tr><td><pre>{"xxxxxxxxxxxxxxxxx",
"xxxxxxxxxxxxxxxxx",
"22222222222222222",
"33333333333333333"}</pre></td></tr><tr><td><pre>3</pre></td></tr><tr><td><pre>12</pre></td></tr></table></td></tr><tr><td><pre>Returns: 17</pre></td></tr><tr><td></td></tr></table></td></tr></table><p>This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved. </p></body></html>