[题记]三维形体的表面积-leetcode

题目：三维形体的表面积

 

在 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

---

思路：

　　[暴力]

　　我们可以求每个正方体的表面积，然后加起来即可。

　　如：grid[0][1] = 3

1. 他有一个顶部面积和底部面积为 top = 2
2. 如果grid[0][1]在整个三维形体的左侧，那么它的左侧面积为 grid[0][1];
3. 如果grid[0][1]的右侧grid[0][2]的高度比grid[0][1]小，那么右侧的面积为grid[0][1] - grid[0][2];
4. 重复步骤2，3检查其他方向。
5. 重复以上步骤，最终得到每个位置上所贡献出的顶面和底面积和侧面积的和，则为三维形体的表面积。

上代码（c）:

//判断这个位置是不是在三维形体的一侧
bool chick( int x, int y, int xlen, int ylen ) {
    if( x < 0|| x >= xlen|| y < 0|| y >= ylen ) return true;
    else return false;
}

int surfacearea(int** grid, int gridsize, int* gridcolsize){
    int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
    int top = 0;
    int side = 0;

    for( int i = 0; i < gridsize; i++ ) {
        for( int j = 0; j < *gridcolsize; j++ ) {
            //底面积+顶面积
            if( grid[i][j] != 0 ) top+=2;

            for( int z = 0; z < 4; z++ ) {

                int x = i + dir[z][0];
                int y = j + dir[z][1];

                //如果在三维形体的一侧
                if( chick(x,y,gridsize,*gridcolsize ) ){
                    side += grid[i][j];
                }
                else {
                    //如果不在三维形体的一侧，检查相邻位置的高度关系
                    if( grid[x][y] >= grid[i][j] ) continue;
                    else ce += grid[i][j] - grid[x][y];
                }
            }
        }
    }
    return side+top;
}

2020-03-25-09:45:22