Ninja’s 3D structures

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
0 upvote
Asked in company
eBay

Problem statement

Ninja is quite free these days, so he started making some random 3D structures. He put some 1 x 1 x 1 cube in an ‘N’ x ‘N’ grid for making these structures. After placing the cubes, he glued all the adjacent cubes together.

Each value ‘V’ = ‘GRID[i][j]’ represents a tower of ‘V’ cubes placed on top of the cell (i, j).

Now, Ninja wants to find the total surface area of the structure that he formed. Your task is to help Ninja in finding the total surface area of the structure.

Note:

The bottom face of each shape counts toward its surface area.

Example

Let say ‘N’ = 2 and ‘GRID’ = [ [1,2] , [ 4, 3] ]. The the grid will look like this


Here, Ninja has kept 1 cube at ‘GRID[0][0]’, 2 cubes at ‘GRID[0][1]’, 4 cubes at ‘GRID[1][0]’ and three cubes at ‘GRID[1][1]’.

If we have to find the total surface area of this structure then, we will have to subtract the total surface area that has glued up. 

After subtracting, the total surface area of the structure made by Ninja would be 34.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain a single integer ‘N’ which denotes the grid’s size.

The next ‘N’ lines contain the ‘N’ space-separated integers which denote the value of ‘GIRD[i][j]’.
Output Format: 
For each test case, return the total surface area of the structure.
Note: 
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 50
1 <= N <= 100
1 <= GRID[ i ][ j ] <= 50

Time limit: 1 sec
Sample Input 1:
2
2
1 3
3 3
1
2
Sample Output 1:
32
10
Explanation of sample input 1:
In the first test case, there is 1 cube at “grid[0][0]” , 3 cubes at “grid[0][1]” ,“grid[1][0]” , and   “grid[1][1]”. So if we consider surface area of all cube towers independently then it would be  
(6 * (1^2) ) + (3 * 6 * (1^2) ) + (3 * 6 * (1^2) ) +  (3 * 6 * (1^2) ) = 60. 

But here, the cube at “grid[0,0]” is sharing the surface with cubes at “grid[0][1]” and at “grid[1][0]”. Similarly, other cubes also have surfaces glued together. After subtracting the glued area, the total surface area of the structure will be 32 units. 


In the second test case, there are only 2 cubes towers placed together. Their surface area individually will be 2 * (6 * (1^2) ) = 12, but the topmost surface of the first cube and the bottom-most surface of the second cube is glued together and not will be considered in the total surface area, so the total surface area will be 2 * (6 * (1^2) ) - (2 * (1^2) ) = 10.
Sample Input 2:
2
4
1 4 3 5
7 8 9 0
1 0 3 0
1 1 1 1
1
0
Sample Output 2:
128
0
Explanation of sample input 2:
In the second test case, there is no cube in the grid, so the surface area is 0.
Hint

Can you analyze the area contributed by each grid?

Approaches (1)
Brute Force, Mathematics

The basic idea is to calculate the total surface area by each cell in the grid. For each tower, its surface area is 4*v + 2.

 

However, 2 adjacent towers will hide the area of the connected part. The hidden part is min(v1, v2), and we need to just subtract twice of this hidden area (as the hidden area will contain faces of both the adjacent cubes).

 

The steps are as follows:

 

  • Initialize a variable 'RES' to store the result; this will be of type int. Initially, its value will be 0.
  • Iterate  0 to ‘N’(say iterator = ‘i’ ).
    • Iterate  from 0 to ‘N’.(say iterator = ‘j’)
      • If ‘GRID[i][j]’ is equals to 1 then increase ‘RES’ by 'GRID[i][j]’*4 + 2 .
      • If ‘i’ is 1 then decrease two times the minimum of “GRID[i][j]” and “GRID[i-1][j]” from ‘RES’.
      • If ‘j’ is 1 then decrease two times the minimum of “GRID[i][j]” and “GRID[i][j-1]” from ‘RES’.
  • Return ‘RES’
Time Complexity

O(N^2), where ‘N’ is the square matrix ‘GRID’ size.

 

Since we are iterating on every index of “grid”. So, the complexity will be O(N^2).

Space Complexity

O(1).

 

No extra space is used.

Code Solution
(100% EXP penalty)
Ninja’s 3D structures
Full screen
Console