Surface Area of 3D Shapes

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

 

// 上下面积都是 size*size 关键是侧面积
// 遍历每个点 统计四个方向上的侧面积（如果周围没有则直接加上这个高度）

// 另一种思路 算上所有的  减去多算的 （值考虑左和上）
class Solution {
public:
    int surfaceArea(vector<vector<int>>& grid) {
        int w=grid[0].size(), h=grid.size();
        vector<pair<int, int>> walk={{1,0},{-1,0},{0,1}, {0,-1}};
        int area=0, cnt=0;
        for(int j=0;j<h;j++){
            for(int i=0;i<w;i++){
                for(int k=0;k<4;k++){
                    if(grid[j][i] != 0) cnt++;
                    int tmpj = j+walk[k].first, tmpi= i+walk[k].second;
                    if(tmpj==h || tmpj<0 || tmpi==w || tmpi<0)  area += grid[j][i];
                    else if(grid[j][i] > grid[tmpj][tmpi])  area += grid[j][i] - grid[tmpj][tmpi];
                }
            }
        }
        area += cnt*2;
        return area;
    }
};

lass Solution {
public:
    int surfaceArea(vector<vector<int>>& grid) {
        int res = 0, n = grid.size();
        for (int i = 0; i < n; ++i) 
        {
            for (int j = 0; j < n; ++j) 
            {
                // get all surface 
                if (grid[i][j]) 
                    res += grid[i][j] * 4 + 2;
                // remove above and left attaching surface
                if (i) 
                    res -= min(grid[i][j], grid[i - 1][j]) * 2;
                if (j) 
                    res -= min(grid[i][j], grid[i][j - 1]) * 2;
            }
        }
        return res;
    }
};