Hide

Problem C
Containment

A $10 \times 10 \times 10$ three-dimensional grid of tightly packed cubic atomic energy cells aboard the starship Fiugtuwf is reporting failures on several of its cells. The ship’s engineer must set up enclosures that will contain all of the cells that are reported to be failing, in order to avoid a meltdown. It is imperative that the enclosures be finished in the shortest amount of time, even if that requires some healthy cells to be enclosed along with the defective ones. The enclosures are formed by square panels which fit perfectly between adjacent cells, or can be placed along the sides of the cells on the edges of the grid. Each panel is exactly the size and shape of a face of one of the cubic cells. For full containment, each enclosure must be completely closed. Given the coordinates of each defective cell, report the minimum number of panels required to contain the problem.

Input

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. Each test case will start with a line with a single integer $n$ ($0 \le n \le 1\, 000$) indicating the number of defective cells. Each of the next $n$ lines will hold an $(x,y,z)$ coordinate ($0 \le x,y,z \le 9$) indicating the location in the grid of a defective cell. All of the coordinates in a test case will be unique.

Output

Output a single line with a single integer, indicating the minimum number of panels required to contain the defective cells.

Sample Input 1 Sample Output 1
1
0 0 0
6
Sample Input 2 Sample Output 2
2
0 0 0
0 0 1
10
Sample Input 3 Sample Output 3
3
0 0 0
0 0 1
0 1 1
14

Please log in to submit a solution to this problem

Log in