LeetCode-892 三维形体的表面积

📝题目

在 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

📝思路

想法一：做加法。
我们可以将单元格 (i, j) 上堆叠的 v 个正方体看成一个高度为 v 的柱子，然后分别计算每个柱子的表面积。
首先，v > 0 的话，柱子顶部、底部的表面积都是 1。
然后是上、下、左、右四个侧面的表面积。以左侧的表面积为例：

• 如果柱子位于网格左边缘，左侧没有其他柱子，那么左侧表面积为 v；
• 如果柱子比左边的柱子矮，那么左侧露不出来，表面积为 0；
• 如果柱子比左边的柱子高，假设左边柱子高度为 v’，那么左边露出来的表面积为 v - v’。

其余的三个侧面以此类推。

想法二：做减法。
先计算全部的表面积，然后再减去重叠的部分。
假设一共有 n 个立方体，每个立方体都有六个面，那么总的表面积应该是 6n。但是这些正方体堆叠在了一起，需要减掉一些因为堆叠而露不出来的表面积。每一对相邻的立方体接触在一起，都会让表面积减少 2。假设一共有 e 对相接触的立方体，即有 e 个接触面，表面积就会减少 2e。那么，最终的表面积就应该是 6n - 2e。
那么如何计算立方体的接触面呢？很简单，我们还是把每个单元格上堆叠的 v 个立方体看成一个柱子。立方体的接触面可以分为柱子内部和柱子之间的接触面：

• v 个立方体的柱子内部，有 v - 1 个接触面
• 高度分别为 v、w 的两个立方体之间的接触面为 min(v, w)。

🐣：Sicily线上赛有一道几乎一样的！！但当时我竟死磕用三视图去解🤦

📝题解

//加法

int surfaceArea(vector<vector<int>>& grid){
    int n = grid.size();
    int result = 0;
    for (int i = 0; i < n; ++i){
        for (int j = 0; j < n; ++j){
            //上下
            if (grid[i][j]) result += 2;
            //左右
            if (j == 0) result += grid[i][j];
            if (j == n-1) result += grid[i][j];
            if (j > 0 && grid[i][j] > grid[i][j-1]) result += (grid[i][j] - grid[i][j-1]);
            if (j < n-1 && grid[i][j] > grid[i][j+1])   result += (grid[i][j] - grid[i][j+1]);
            //前后
            if (i == 0) result += grid[i][j];
            if (i == n-1) result += grid[i][j];
            if (i > 0 && grid[i][j] > grid[i-1][j]) result += (grid[i][j] - grid[i-1][j]);
            if (i < n-1 && grid[i][j] > grid[i+1][j])   result += (grid[i][j] - grid[i+1][j]);
        }
    }
    return result;
}

//减法

int surfaceArea(vector<vector<int>>& grid){
    int n = grid.size();
    int result = 0;
    for (int i = 0; i < n; ++i){
        for (int j = 0; j < n; ++j){
            if (grid[i][j]) result += 4*grid[i][j]+2;
            if (i < n-1)
                result -= 2*min(grid[i][j], grid[i+1][j]);
            if (j < n-1)
                result -= 2*min(grid[i][j], grid[i][j+1]);
        }
    }
    return result;
}