Space Station Shielding
Time limit1sMemory limit128 MB
Given occupied unit cells of a connected 3D station, count faces on the external surface, where enclosed hollow pockets do not count.
- Level
Medium6 of 10
- Topics
- BFS, Implementation, Matrix, Brute force
- Solved
- No attempts yet
Problem
You are designing a low-orbit space station assembled from identical Airtight Cubical Modules (ACMs) — unit cubes joined together in space. Because the station occasionally passes through the upper atmosphere, where potentially lethal bacteria live, every face of an ACM that lies on the external surface of the station must be given extra shielding.
Wherever two ACMs meet face-to-face, the joint is sealed, so a shared face needs no shielding. A face that cannot be reached from the outside — for example, a face bordering a fully enclosed hollow pocket inside the station — also needs no shielding. Every other face is on the external surface and must be shielded.
Given the arrangement of ACMs, determine the exact number of faces that need extra shielding.
Input
The input contains several station descriptions.
Each description begins with a line of four positive integers . The station fits inside an grid of unit cells (), and is the number of ACMs.
The grid cells are numbered . The cell at coordinates , with , and , has the number ( varies fastest, then , then ).
After the four integers come the cell numbers of the occupied cells, separated by whitespace. Every station is fully connected: an astronaut can travel from any ACM to any other without leaving the station.
A line of four zeros, 0 0 0 0, terminates the input and is not processed.
Output
For each station, print one line:
The number of faces needing shielding is s.
where is the number of faces on the external surface — that is, the faces reachable from outside the station.