On a N * N grid, we place some 1 * 1 * 1 cubes.

Each value v = grid[i][j] represents a tower of v cubes placed on top of grid cell (i, j).

Return the total surface area of the resulting shapes.

 

Example 1:

Input: [[2]]
Output: 10

Example 2:

Input: [[1,2],[3,4]]
Output: 34

Example 3:

Input: [[1,0],[0,2]]
Output: 16

Example 4:

Input: [[1,1,1],[1,0,1],[1,1,1]]
Output: 32

Example 5:

Input: [[2,2,2],[2,1,2],[2,2,2]]
Output: 46

 

Note:

• 1 <= N <= 50
• 0 <= grid[i][j] <= 50

 

Approach #1: Math. [Java]

class Solution {
    public int surfaceArea(int[][] grid) {
        int N = grid.length;
        int ret = 0;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (grid[i][j] > 0) ret += grid[i][j] * 4 + 2;
                if (i > 0) ret -= Math.min(grid[i][j], grid[i-1][j]) * 2;
                if (j > 0) ret -= Math.min(grid[i][j], grid[i][j-1]) * 2;
            }
        }
        return ret;
    }
}

　　

Analysis:

For each tower, its surface area is 4 * v + 2. However, 2 adjacent tower will hide the area of connected part. The hidden part is min(v1, v2) and we need just minus this area * 2.

 

Reference:

https://leetcode.com/problems/surface-area-of-3d-shapes/discuss/163414/C%2B%2BJava1-line-Python-Minus-Hidden-Area