Description
Details
Planet X is the only known location of Illudium Phosdex, the shaving cream atom. The planet’s
surface can be modeled as a 20 x 20 hexagonal map, shown below.
The surface of Planet X is rather plain, except for areas of molten lava, over which neither Duck
Dodgers nor Marvin the Martian can pass. The Illudium Phosdex resides in one non-lava cell on the
map.
The basic goal of this project is simple: assuming that Dodgers and Marvin move at the same rate,
which one can reach the Illudium Phosdex first?
The program must begin by reading seven integers: the row and column of Duck Dodgers’ starting
position, the row and column of Marvin the Martian’s starting position, the row and column of the
location of the Illudium Phosdex, and the number of map cells covered in lava.
Next, for each lava cell, the program must read the row and column of the lava’s location.
Once the data is read, find a shortest path from both Marvin and Dodgers to the Illudium Phosdex.
Output a shortest path from both characters to the goal, and determine who will claim the Illudium
Phosdex. Break any ties in favor of Marvin the Martian (he has a disintegration gun that doesn’t
disintegrate, and he’s not afraid to use it).
.A Twist. . .
Duck Dodgers’ sidekick is more resourceful than Dodgers, and will try to block Marvin. He can
use his Acme Teleporter to summon Gandalf the Grey (hey, if the new Duck Dodgers can have
a crossover episode with Samurai Jack, why not Lord of the Rings?), who will stand in one cell,
blocking Marvin while reciting his famous “You shall not pass!” quote. See if there is a location for
Gandalf that would force Marvin to take a detour and let Duck Dodgers win.
If there is a position for Gandalf that lets Duck Dodgers reach the Illudium Phosdex first, output the
position and the new route for Marvin the Martian. Otherwise, output a message that indicates
that Gandalf cannot help.
Data Structures and Objects Project 3
.Pseudorandom Thoughts
• You don’t have to look at every cell to find a spot for Gandalf. But you do have to redo your
calculations.
• You’ll want a queue to find the shortest path, and you might want a linear list to help find
Gandalf’s position.
• We’ll discuss the algorithms in class and/or lab.
What to turn in
Turn in your source code and Makefile. If you use Code::Blocks, turn in a tarball of your project
directory.
2 of 3
Data Structures and Objects Project 3
0,0
0,1
0,2
0,3
0,4
0,5
0,6
0,7
0,8
0,9
0,10
0,11
0,12
0,13
0,14
0,15
0,16
0,17
0,18
0,19
1,0
1,1
1,2
1,3
1,4
1,5
1,6
1,7
1,8
1,9
1,10
1,11
1,12
1,13
1,14
1,15
1,16
1,17
1,18
1,19
2,0
2,1
2,2
2,3
2,4
2,5
2,6
2,7
2,8
2,9
2,10
2,11
2,12
2,13
2,14
2,15
2,16
2,17
2,18
2,19
3,0
3,1
3,2
3,3
3,4
3,5
3,6
3,7
3,8
3,9
3,10
3,11
3,12
3,13
3,14
3,15
3,16
3,17
3,18
3,19
4,0
4,1
4,2
4,3
4,4
4,5
4,6
4,7
4,8
4,9
4,10
4,11
4,12
4,13
4,14
4,15
4,16
4,17
4,18
4,19
5,0
5,1
5,2
5,3
5,4
5,5
5,6
5,7
5,8
5,9
5,10
5,11
5,12
5,13
5,14
5,15
5,16
5,17
5,18
5,19
6,0
6,1
6,2
6,3
6,4
6,5
6,6
6,7
6,8
6,9
6,10
6,11
6,12
6,13
6,14
6,15
6,16
6,17
6,18
6,19
7,0
7,1
7,2
7,3
7,4
7,5
7,6
7,7
7,8
7,9
7,10
7,11
7,12
7,13
7,14
7,15
7,16
7,17
7,18
7,19
8,0
8,1
8,2
8,3
8,4
8,5
8,6
8,7
8,8
8,9
8,10
8,11
8,12
8,13
8,14
8,15
8,16
8,17
8,18
8,19
9,0
9,1
9,2
9,3
9,4
9,5
9,6
9,7
9,8
9,9
9,10
9,11
9,12
9,13
9,14
9,15
9,16
9,17
9,18
9,19
10,0
10,1
10,2
10,3
10,4
10,5
10,6
10,7
10,8
10,9
10,10
10,11
10,12
10,13
10,14
10,15
10,16
10,17
10,18
10,19
11,0
11,1
11,2
11,3
11,4
11,5
11,6
11,7
11,8
11,9
11,10
11,11
11,12
11,13
11,14
11,15
11,16
11,17
11,18
11,19
12,0
12,1
12,2
12,3
12,4
12,5
12,6
12,7
12,8
12,9
12,10
12,11
12,12
12,13
12,14
12,15
12,16
12,17
12,18
12,19
13,0
13,1
13,2
13,3
13,4
13,5
13,6
13,7
13,8
13,9
13,10
13,11
13,12
13,13
13,14
13,15
13,16
13,17
13,18
13,19
14,0
14,1
14,2
14,3
14,4
14,5
14,6
14,7
14,8
14,9
14,10
14,11
14,12
14,13
14,14
14,15
14,16
14,17
14,18
14,19
15,0
15,1
15,2
15,3
15,4
15,5
15,6
15,7
15,8
15,9
15,10
15,11
15,12
15,13
15,14
15,15
15,16
15,17
15,18
15,19
16,0
16,1
16,2
16,3
16,4
16,5
16,6
16,7
16,8
16,9
16,10
16,11
16,12
16,13
16,14
16,15
16,16
16,17
16,18
16,19
17,0
17,1
17,2
17,3
17,4
17,5
17,6
17,7
17,8
17,9
17,10
17,11
17,12
17,13
17,14
17,15
17,16
17,17
17,18
17,19
18,0
18,1
18,2
18,3
18,4
18,5
18,6
18,7
18,8
18,9
18,10
18,11
18,12
18,13
18,14
18,15
18,16
18,17
18,18
18,19
19,0
19,1
19,2
19,3
19,4
19,5
19,6
19,7
19,8
19,9
19,10
19,11
19,12
19,13
19,14
19,15
19,16
19,17
19,18
19,19
Figure 1: An empty map of Planet X
3 of 3
