CSE 4051: Project #5, Space Station Shielding
Due: Friday, 8 February 2008
The Task
Roger Wilco is in charge of the design of a low orbiting space station
for the planet Mars. To simplify construction, the station is made up
of a series of Airtight Cubical Modules (ACM's), which are connected
together once in space. One problem that concerns Roger is that of
(potentially) lethal bacteria that may reside in the upper atmosphere
of Mars. Since the station will occasionally fly through the upper
atmosphere, it is imperative that extra shielding be used on all faces
of the ACM's touch, either edge to edge or face to face, that joint is
sealed so no bacteria can sneak through. Any face of an ACM shared by
another ACM will not need shielding, of course, nor will a face which
cannot be reached from the outside. Roger could just put extra
shielding on all of the faces of every ACM, but the cost would be
prohibitive. Therefore, he wants to know the exact number of ACM faces
which need the extra shielding.
Space Station
Each space station is fully connected
(i.e., an astronaut can move from one ACM to any other ACM in the
station without leaving the station).
We assume that each space station can fit into an n × m × k grid
(1 ≤ n, m, k ≤ 60), where each grid cube may or may not contain an ACM.
We number the grid cubes 0, 1, 2, ..., kmn-1 as shown in the diagram below.
A space station specification then consists of the
following: the first line contains four positive integers n, m, k, l,
where n, m and k are as described above and l ≥ 1 is the number of ACM's
in the station.
This is followed by at least one and at most l lines which specify the l
grid locations of the ACM's.
Each of these lines contain 1 or more integers.
(For example, if l were equal to 12, then there could be three lines
with four numbers on each line, or four lines with three numbers each,
or 1, 2, 3, and 6 numbers in four lines, etc.)
Input/Output
Read from the standard input stream.
The input consists of multiple problem instances.
each instance consists of a specification of a space station.
For each problem instance, you should output one line of the form
Space station #D: The number of faces needing shielding is S.
For example, the following input
2 2 1 3 #1. 2x2x1, 3 modules
0 1 3
3 3 3 26 #2. 3x3x3, 26 modules
0 1 2 3 4 5 6 7 8 9
10 11 12 14 15 16 17 18 19 20
21 22 23 24 25 26
0 0 0 0 # The end
should yield the output.
Space station #1: The number of faces needing shielding is 14.
Space station #2: The number of faces needing shielding is 54.
Acknowledgment
ICPC East Central North America 2001; TJU #1198
Helpful Stuff
Turning it in
Turn in the Java source code for the program using the submission server.
The file name should be SpaceStation.java and the project is proj05.
Be sure your name is in comments at the beginning of your program
as required in the standard header for this class.
For your convenience, here is a submission form for this assignment.
Ryan Stansifer <ryan@cs.fit.edu>
Last modified: Tue Feb 5 10:07:21 EST 2008