Leetcode 892.三维形体的表面积【C++】

地址：https://leetcode-cn.com/problems/surface-area-of-3d-shapes/

题目

在 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

解题思路

一开始这个题还真是一头雾水，虽然之前做过类似的题，比如前不久才做过的“腐烂橘子”那个题，就很类似。

只要做过类似的题，应该还是很容易想到要遍历二维数组，然后对每一个元素要判断其周围的元素，如果有需要的话可能还需要动态规划、递归之类的方法来解题。

仔细思考一下，其实这个题想通了思路还挺简单的，因为并没有用到动态规划或是递归，只需要遍历一次二维数组就可以了。

首先不考虑周围格子的情况下，每一个格子上所堆叠的正方体都有一个表面积，如果没有立方体那么它的表面积为 0 ，显然也不会有与别的立方体重叠的部分；否则该单元格上堆叠的立方体的表面积应为 4 * grid[i][j] + 2 。

然后考虑周围格子的情况，不管周围单元格是否有立方体，与当前单元格重叠的部分始终是较少立方体的个数，也就是 grid[i][j] <= grid[ii][jj] ? grid[i][j] : grid[ii][jj] ，按照我们人的思维很容易想到应该减去2倍的重叠部分的面积，但是不能这么做，程序它不聪明，当它遍历的这个相邻单元格的时候，再一次减掉2倍的重叠部分的面积，实际上就减去了4倍的重叠部分的面积，所以我们应该只考虑当前单元格应该做的事，也就是只减掉当前单元格与相邻单元格重叠部分的面积（1倍）。

重复上述步骤遍历完整个二维数组，即可以得到最终的三维形体表面积。

代码

class Solution {
public:
    int surfaceArea(vector<vector<int>>& grid) {
        int area = 0;//表面积
        vector<pair<int, int>> dir = { {-1,0},{1,0},{0,-1},{0,1} };//上、下、左、右
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 0)//没有立方体不做处理，面积不改变
                    continue;
                area += 4 * grid[i][j] + 2;//不考虑四周重叠部分的表面积
                for (auto d : dir) {
                    int ii = i + d.first;
                    int jj = j + d.second;
                    //减掉相邻立方体个数较少的一侧的面积
                    //例如4和2相邻，应减掉当前4个立方体与2相邻一侧的表面积2
                    if (ii >= 0 && ii < grid.size() && jj >= 0 && jj < grid[0].size()) {
                        area -= grid[i][j] <= grid[ii][jj] ? grid[i][j] : grid[ii][jj];
                    }
                }
            }
        }
        return area;
    }
};