Question
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
Difficulty:Medium
Category:Math, Geometry
Analyze
Solution
// Running time: 8 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;
}
};