How to Compute the Surface Area of 3D Shapes (Cubes Placed on Gr

  • 时间：2020-09-18 17:01:02
  • 分类：网络文摘
  • 阅读：148 次

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

When we place a single cube on the grid, the surface is 6 (4×1+2), when we place a 2×1 cubes on the grid, the surface is 10 – which is 4×2+2. That is, there is only 1 top and 1 bottom, but 4 times of the number cubes that stacked together – as the connected parts (vertically) are hidden.

Then, we can iterate each verticl stacked cubes, add the top and bottom, count the side surfaces by checking the four neighbours, and add the difference.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
public:
    int surfaceArea(vector<vector<int>>& grid) {
        int dr[4] = {0, 1, 0, -1};
        int dc[4] = {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) && (0 <= nc) && 
                            (nr < N) && (nc < N)) {
                            nv = grid[nr][nc];
                        }
                        ans += max(grid[r][c] - nv, 0);
                    }
                }
            }
        }
        return ans;
    }
};
class Solution {
public:
    int surfaceArea(vector<vector<int>>& grid) {
        int dr[4] = {0, 1, 0, -1};
        int dc[4] = {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) && (0 <= nc) && 
                            (nr < N) && (nc < N)) {
                            nv = grid[nr][nc];
                        }
                        ans += max(grid[r][c] - nv, 0);
                    }
                }
            }
        }
        return ans;
    }
};

Slightly differently, we can check the neighbours of north and west only and minus those connected surfaces.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    int surfaceArea(vector<vector<int>>& grid) {
        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 += 4 * grid[r][c] + 2;
                    if (r > 0) ans -= min(grid[r][c], grid[r - 1][c]) * 2;
                    if (c > 0) ans -= min(grid[r][c], grid[r][c - 1]) * 2;
                }
            }
        }
        return ans;
    }
};
class Solution {
public:
    int surfaceArea(vector<vector<int>>& grid) {
        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 += 4 * grid[r][c] + 2;
                    if (r > 0) ans -= min(grid[r][c], grid[r - 1][c]) * 2;
                    if (c > 0) ans -= min(grid[r][c], grid[r][c - 1]) * 2;
                }
            }
        }
        return ans;
    }
};

Both algorithms/approaches are based on the counting, which result in O(N^2) time and O(1) space requirement.

Similar post: How to Compute the Projection Area of 3D Shapes?

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
诗词名句鉴赏：大风起兮云飞扬，威加海内兮归故乡。　 百家讲坛系列节目《于丹〈庄子〉心得》MP3蓝奏云下载　 诗词名句鉴赏：男儿爱后妇，女子重前夫。　 诗词名句鉴赏：居异土国兮心内伤，愿为黄鹄兮归故乡。　 子革对灵王原文及翻译　 写人作文乐趣作文900字　 关于都江堰的写景作文　 有位置随便坐作文650字　 不一样的端午节作文　 读《为了妹妹》有感　
评论列表
添加评论