LeetCode.892.Surface Area of 3D Shapes 网格内三维柱体的表面积

题目描述

994 Rotting Oranges
https://leetcode-cn.com/problems/rotting-oranges/

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

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

---

解题过程

想复杂了，用了深度优先搜索，当然也没有错，不过没必要。
其实只需要按行列扫描即可，因为对每个坐标内的柱体，只需要看其上下左右即可，连通性对问题的解是无关的。

每个柱体单独考虑，上下面的表面积和肯定是2，前后左右的话，如果某个侧面有比当前柱体矮的或空着的，则加上这个面暴露出来的表面积。

时间复杂度 O(n^2)，空间复杂度 O(1)

private static class SolutionV2020 {
    private int area;
    public int surfaceArea(int[][] grid) {
        if (null == grid || 0 == grid.length) {
            return 0;
        }

        this.area = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] > 0) {
                    dfs(grid, i, j);
                }
            }
        }
        return area;
    }

    // 从(x,y)开始一次dfs，过程中更新访问过点的表面积
    private void dfs(int[][] grid, int x, int y) {
        int rows = grid.length, columns = grid[0].length;
        if (x < 0 || y < 0 || x >= rows || y >= rows || grid[x][y] <= 0) {
            return;
        }
        // 访问 x,y
        area += 2; // 上下表面积

        // x,y 上右下左 的侧面积
        area += x - 1 >= 0 ? Math.max(0, grid[x][y] - Math.abs(grid[x - 1][y])) : grid[x][y];
        area += y + 1 < columns ? Math.max(0, grid[x][y] - Math.abs(grid[x][y + 1])) : grid[x][y];
        area += x + 1 < rows ? Math.max(0, grid[x][y] - Math.abs(grid[x+1][y])) : grid[x][y];
        area += y - 1 >= 0 ? Math.max(0, grid[x][y] - Math.abs(grid[x][y-1])) : grid[x][y];
        // 访问过的标为负值
        grid[x][y] = - grid[x][y];

        // 递归上右下左
        dfs(grid, x - 1, y);
        dfs(grid, x, y + 1);
        dfs(grid, x + 1, y);
        dfs(grid, x, y - 1);
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_892_SurfaceAreaOf3DShapes.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_892_SurfaceAreaOf3DShapes.java

---