欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-05-04 14:23:31
题目:三维形体的表面积 在 N * N 的网格上,我们放置一些 1 * 1 * 1 的立方体。 每个值 v = grid[i][j] 表示 v 个正方体叠放在对应单元格 (i, j) 上。 请你返回最终形体的表面积。 示例 1: 输入:[[2]]输出:10示例 2: 输入:[[1,2],[3,4]] ......

题目:三维形体的表面积

 

在 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