You are given an n x n grid where you have placed some 1 x 1 x 1 cubes. Each value v = grid[i][j] represents a tower of v cubes placed on top of cell (i, j).
After placing these cubes, you have decided to glue any directly adjacent cubes to each other, forming several irregular 3D shapes.
Return the total surface area of the resulting shapes.
Note: The bottom face of each shape counts toward its surface area.
Example 1:
Input: grid = [[1,2],[3,4]] Output: 34
Example 2:
Input: grid = [[1,1,1],[1,0,1],[1,1,1]] Output: 32
Example 3:
Input: grid = [[2,2,2],[2,1,2],[2,2,2]] Output: 46
Constraints:
n == grid.length == grid[i].length1 <= n <= 500 <= grid[i][j] <= 50program main
implicit none
integer, parameter :: n = 2
integer, dimension(n, n) :: grid
integer :: i, j, v
real :: area
! Example 1
grid = reshape([1, 2, &
3, 4], shape=[n, n])
write(*,*) "Example 1:"
call solve(grid, area)
write(*,*) "Area: ", area
! Example 2
grid = reshape([1, 1, 1, &
1, 0, 1, &
1, 1, 1], shape=[n, n])
write(*,*) "Example 2:"
call solve(grid, area)
write(*,*) "Area: ", area
! Example 3
grid = reshape([2, 2, 2, &
2, 1, 2, &
2, 2, 2], shape=[n, n])
write(*,*) "Example 3:"
call solve(grid, area)
write(*,*) "Area: ", area
contains
subroutine solve(grid, area)
implicit none
integer, intent(in) :: grid(:, :)
real, intent(out) :: area
integer :: i, j, v
integer :: count
logical :: found
area = 0.0
do i = 1, size(grid, 1)
do j = 1, size(grid, 2)
v = grid(i, j)
if (v > 0) then
count = 0
found = .false.
do while (.not. found)
if (i - 1 >= 1) then
if (grid(i-1, j) == v) then
count = count + 1
found = .true.
end if
else
found = .true.
end if
if (.not. found) then
if (j - 1 >= 1) then
if (grid(i, j-1) == v) then
count = count + 1
found = .true.
end if
else
found = .true.
end if
end if
if (.not. found) then
if (i + 1 <= size(grid, 1)) then
if (grid(i+1, j) == v) then
count = count + 1
found = .true.
end if
else
found = .true.
end if
end if
if (.not. found) then
if (j + 1 <= size(grid, 2)) then
if (grid(i, j+1) == v) then
count = count + 1
found = .true.
end if
else
found = .true.
end if
end if
end do
area = area + count * v
end if
end do
end do
end subroutine solve
end program mainExample 1: Area: 0.00000000 Example 2: Area: 2.00000000 Example 3: Area: 4.00000000
module glue_cubes
implicit none
private
public :: surface_area
contains
function surface_area(grid) result(total_area)
integer, intent(in) :: grid(:, :)
integer :: total_area, i, j, v
integer, allocatable :: stack(:)
allocate(stack(size(grid, 1)))
total_area = 0
do i = 1, size(grid, 1)
do j = 1, size(grid, 2)
v = grid(i, j)
if (v > 0) then
stack = [v]
do while (size(stack) > 0)
v = stack(size(stack))
stack = stack(:size(stack)-1)
total_area = total_area + v * (v + 1)
if (i > 1 .and. grid(i-1, j) == v) then
stack = [v, stack]
grid(i-1, j) = 0
end if
if (j > 1 .and. grid(i, j-1) == v) then
stack = [v, stack]
grid(i, j-1) = 0
end if
end do
end if
end do
end do
end function surface_area
end module glue_cubes
program test_glue_cubes
use glue_cubes
implicit none
integer, parameter :: n = 2
integer, parameter :: grid(n, n) = reshape([1, 2, 3, 4], [n, n])
integer :: total_area
total_area = surface_area(grid)
write (*, *) "Total surface area:", total_area
total_area = surface_area([[1, 1, 1], [1, 0, 1], [1, 1, 1]])
write (*, *) "Total surface area:", total_area
total_area = surface_area([[2, 2, 2], [2, 1, 2], [2, 2, 2]])
write (*, *) "Total surface area:", total_area
end program test_glue_cubes
temp.f95:25:28:
25 | grid(i-1, j) = 0
| 1
Error: Dummy argument ‘grid’ with INTENT(IN) in variable definition context (assignment) at (1)
temp.f95:29:28:
29 | grid(i, j-1) = 0
| 1
Error: Dummy argument ‘grid’ with INTENT(IN) in variable definition context (assignment) at (1)
temp.f95:39:9:
39 | use glue_cubes
| 1
Fatal Error: Cannot open module file ‘glue_cubes.mod’ for reading at (1): No such file or directory
compilation terminated.
from collections import deque
def shortest_subarray(nums, k):
n = len(nums)
prefix_sum = [0] * (n + 1)
for i in range(n):
prefix_sum[i + 1] = prefix_sum[i] + nums[i]
res = n + 1
dq = deque()
for i in range(n + 1):
while dq and prefix_sum[i] - prefix_sum[dq[0]] >= k:
res = min(res, i - dq.popleft())
while dq and prefix_sum[i] <= prefix_sum[dq[-1]]:
dq.pop()
dq.append(i)
return res if res <= n else -1
The algorithm first calculates the prefix sum of the array. Then, it initializes a double-ended queue (deque) to store indices of the prefix sum. For each index of the calculated prefix sum, perform these steps:
k. If true, update the result with the minimum value. This means we found a subarray that meets the requirement of sum >= k, so we remove the deque's front element to see if there's a shorter subarray.Finally, after iterating through all elements, check if the stored result is valid. If valid, return the result; otherwise, return -1. This logic is implemented in all 4 language solutions.
#include <deque>
#include <vector>
using namespace std;
int shortestSubarray(vector<int>& nums, int k) {
int n = nums.size();
vector<int> prefix_sum(n + 1, 0);
for (int i = 0; i < n; i++) prefix_sum[i + 1] = prefix_sum[i] + nums[i];
int res = n + 1;
deque<int> dq;
for (int i = 0; i < n + 1; i++) {
while (!dq.empty() && prefix_sum[i] - prefix_sum[dq.front()] >= k) {
res = min(res, i - dq.front());
dq.pop_front();
}
while (!dq.empty() && prefix_sum[i] <= prefix_sum[dq.back()]) {
dq.pop_back();
}
dq.push_back(i);
}
return res <= n ? res : -1;
}
The algorithm first calculates the prefix sum of the array. Then, it initializes a double-ended queue (deque) to store indices of the prefix sum. For each index of the calculated prefix sum, perform these steps:
k. If true, update the result with the minimum value. This means we found a subarray that meets the requirement of sum >= k, so we remove the deque's front element to see if there's a shorter subarray.Finally, after iterating through all elements, check if the stored result is valid. If valid, return the result; otherwise, return -1. This logic is implemented in all 4 language solutions.