题目

难度：★★☆☆☆
类型：几何、数学、二维数组

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

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

返回最终形体的表面积。

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

示例

示例 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

解答

这道题与【题目463. 岛屿的周长】属于同一类，相当于将二维扩展到了三维。

循环。由于题目已经告知我们，搜索范围是50*50的方格（grid），因此我们可以遍历每一个方格，查看这些方格上是否存在四棱柱。

表面积的处理。这是这个问题的重点和难点，当某一个正方形（grid[i][j]）上存在四棱柱时，四棱柱的上下底面是无法被遮挡的，因此最终结果一定包含上下底面，可能被遮挡的部分只有四个方向的侧面，如果侧面相邻位置存在棱柱，那么当前棱柱肯定会有一部分表面被遮挡起来，且遮挡的面积取决于两者的高度。

我们计算当前棱柱grid[i][j]贡献的表面积：

底面：首先将两个底面的面积加入结果中：ans=ans+2；
侧面：四个相邻位置(i+1, j), (i-1, j), (i, j+1), (i, j-1)分别考虑，如果其中一个位置存在高度为h的棱柱，那么当前高为grid[i][j]的棱柱被遮挡的部分高度为min(h, grid[i][j])，贡献了grid[i][j]-min(h, grid[i][j])=max(0, grid[i][j]-h)的表面积，其中h既是相邻棱柱的高度，也可以认为是两者接触面的面积，我们定义为concat。

例如[[1,5]]，表示[0, 0]方格上放一个高度为1的棱柱A，[0, 1]方格上放一个高度为5的棱柱B，棱柱B贡献的表面积的计算方式为：2（两个底面）+3*5（三个没有棱柱相邻的侧面）+（5-1）（与棱柱A接壤的侧面）=21。

边界。如果某一个棱柱已经在边界上，我们考察其周围四个相邻方向时，可能发现一个方向上已经超出棋盘范围，我们认为这个超出棋盘的位置上没有棱柱，也就是该相邻位置与当前接触面的面积concat为零，这个面贡献的表面积实际上就是当前棱柱的高度。

例如上述案例中，棱柱A贡献的表面积是：2（两个底面）+1（在边缘的侧面）+1（在边缘的侧面）+1（没有棱柱接壤的侧面）+0（与棱柱B接壤的侧面）=5，两个棱柱一共贡献表面积21+5=26。

编码过程如下：

class Solution:
    def surfaceArea(self, grid):
        """
        :param grid: List[List[int]]
        :return: int
        """
        N = len(grid)
        ans = 0                                                                         # 总面积
        for r in range(N):
            for c in range(N):
                if grid[r][c]:                                                          # 如果当前位置有柱体
                    ans += 2                                                            # 上下底面
                    for nr, nc in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)):             # 考察四方
                        contact = grid[nr][nc] if 0 <= nr < N and 0 <= nc < N else 0    # 接触面
                        ans += max(grid[r][c] - contact, 0)                             # 减去接触面
        return ans

如有疑问或建议，欢迎评论区留言~