2020-03-25 三维形体的表面积

在 N * N 的网格上，我们放置一些 1 * 1 * 1 的立方体。

每个值 v = grid[i][j] 表示 v 个正方体叠放在对应单元格 (i, j) 上。

请你返回最终形体的表面积。

示例 1：

输入：[[2]]
输出：10
示例 2：

输入：[[1,2],[3,4]]
输出：34
示例 3：

输入：[[1,0],[0,2]]
输出：16
示例 4：

输入：[[1,1,1],[1,0,1],[1,1,1]]
输出：32
示例 5：

输入：[[2,2,2],[2,1,2],[2,2,2]]
输出：46

提示：

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

来源：力扣（LeetCode）

C++1

解题思路：
此题题意不容易理解，但是观察示例可以辅助理解题意：
首先立方体的任意一个面的面积为1。给定一个二维数组grid，每个元素代表该位置上的正方体数量，每两个相邻的正方体之间会有面的重叠，是不计入表面积的，但是最底层的正方体的下表面是表面积的一部分，求最后摆出的整体形体的表面积。

主要的难点就是如何计算某个正方体和上下左右的正方体的重叠面积，将其减掉，注意不要重复计算。

解决办法：从左上角遍历二维数组，每个位置堆叠的正方体的个数乘以4代表4个侧面的表面积总数，再加上最上面和最底层的面的面积2即可算出当前位置的总表面积res，在分别和左边和上边的位置堆叠的立方体做高度的比较，分别取最小高度h1，h2，则它们分别乘以2就是每个方向需要减去的表面积的数量，最后累计求出表面积的和即可。

class Solution {
public:
    int surfaceArea(vector<vector<int>>& grid) {
        int s = grid.size(),res=0;
        for(int i=0;i<s;i++){
            for(int j=0;j<s;j++){
                int value = grid[i][j];
                if(value>0){
                    res+=value*4+2;
                    if(i>0)
                        res-=min(value, grid[i-1][j])*2;
                    if(j>0)
                        res-=min(value, grid[i][j-1])*2;
                }
            }
        }
        return res;
    }
};

C++2

思路:
单独计算每一个 v = grid[i][j] 所贡献的表面积，再将所有的 v 值相加就能得到最终形体的表面积：

对于顶面和底面的表面积，如果 v > 0，那么顶面和底面各贡献了 1 的表面积，总计 2 的表面积；

对于四个侧面的表面积，只有在相邻位置的高度小于 v 时，对应的那个侧面才会贡献表面积，且贡献的数量为 v - nv，其中 nv 是相邻位置的高度。我们可以将其写成 max(v - nv, 0)。

举一个例子，对于网格

1 5
6 7

而言，位置 grid[0][1] 的高度为 5：

因为 5 > 0，所以贡献了 2 的顶面和底面表面积；

该位置的上方和右侧没有单元格，可以看成高度为 0，所以分别贡献了 max(5 - 0, 0) = 5 的表面积；

该位置的左侧高度为 1，所以贡献了 max(5 - 1, 0) = 4 的表面积；

该位置的下方高度为 7，所以贡献了 max(5 - 7, 0) = 0 的表面积。

因此 grid[0][1] 贡献的表面积总和为 2 + 5 + 5 + 4 + 0 = 16。

算法

对于每个 v = grid[r][c] > 0，计算 ans += 2，对于 grid[r][c] 四个方向的每个相邻值 nv 还要加上 max(v - nv, 0)。

来源：LeetCode-Solution

class Solution {
public:
    int surfaceArea(vector<vector<int>>& grid) {
        int dr[]{0, 1, 0, -1};
        int dc[]{1, 0, -1, 0};

        int N = grid.size();
        int ans = 0;

        for (int r = 0; r < N; ++r)
            for (int c = 0; c < N; ++c)
                if (grid[r][c] > 0) {
                    ans += 2;
                    for (int k = 0; k < 4; ++k) {
                        int nr = r + dr[k];
                        int nc = c + dc[k];
                        int nv = 0;
                        if (0 <= nr && nr < N && 0 <= nc && nc < N)
                            nv = grid[nr][nc];

                        ans += max(grid[r][c] - nv, 0);
                    }
                }

        return ans;
    }
};