Problem
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 <= 500 <= grid[i][j] <= 50
Solution: Geometry
3D version of 花花酱 LeetCode 463. Island Perimeter
Ans = total faces – hidden faces.
each pile with height h has the surface area of 2 (top/bottom) + 4*h (sides)
\(ans = ans + 2 + 4 * h\)if a cube has a neighbour, reduce the total surface area by 1
For each pile, we check 4 neighbours, the number of total hidden faces of this pile is sum(min(h, neighbour’s h)).
\(ans = ans – \Sigma min(h, n.h)\)Time complexity: O(mn)
Space complexity: O(1)
C++
|
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 |
// Author: Huahua // Running time: 4 ms class Solution { public: int surfaceArea(vector<vector<int>>& grid) { static const vector<int> dirs{0, -1, 0, 1, 0}; int m = grid.size(); int n = grid[0].size(); int ans = 0; for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) { int h = grid[i][j]; if (h == 0) continue; ans += 2 + 4 * h; for (int k = 0; k < 4; k++) { int tx = j + dirs[k]; int ty = i + dirs[k + 1]; if (tx < 0 || tx >= n || ty < 0 || ty >= m) continue; int th = grid[ty][tx]; ans -= (th <= 0 ? 0 : min(h, th)); } } return ans; } }; |
C++ (opt)
Since the neighbor relationship is symmetric, we can only consider the top and left neighbors and double the hidden faces.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua // Running time: 4 ms class Solution { public: int surfaceArea(vector<vector<int>>& grid) { int m = grid.size(); int n = grid[0].size(); int ans = 0; for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) { int h = grid[i][j]; if (h == 0) continue; ans += 2 + 4 * h; if (i) ans -= 2 * min(h, grid[i - 1][j]); if (j) ans -= 2 * min(h, grid[i][j - 1]); } return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment