892.Surface Area of 3D Shapes

Tags: Easy Math

Links: https://leetcode.com/problems/surface-area-of-3d-shapes/

---

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

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

---

class Solution {
    int direction[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
public:
    int surfaceArea(vector<vector<int>>& grid) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int cost = 0;
        int cnt = 0;
        int m = grid.size(); if (!m) return 0;
        int n = grid[0].size(); if (!n) return 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                cnt += grid[i][j];
                for (int k = 0; k < 4; ++k) {
                    int row = i + direction[k][0];
                    int col = j + direction[k][1];
                    if (0 <= row && row < m && 0 <= col && col < n) {
                        cost += min(grid[i][j], grid[row][col]);
                    }
                }
                cost += (grid[i][j] > 0 ? 2 * (grid[i][j] - 1) : 0);
            }
        }

        return cnt * 6 - cost;
    }
};

用cnt统计共用多少个立方体，每个正方体共六个面，只需要最后减去被遮挡的部分。遮挡部分来源于两个方面。一个是和周围立方体的重叠，另一方面是自身上下的重叠。和周围立方体的重叠可以利用木桶效应来分析，只需要计算高度最小的部分，上下重叠就是立方体个数-1然后乘2.