Island Perimeter

🏠 ⬅️ ➡️

You are given row x col grid representing a map where grid[i][j] = 1 represents land and grid[i][j] = 0 represents water.

Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).

The island doesn't have "lakes ", meaning the water inside isn't connected to the water around the island. One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.

Example 1:

Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]] Output: 16 Explanation: The perimeter is the 16 yellow stripes in the image above.

Example 2:

Input: grid = [[1]] Output: 4

Example 3:

Input: grid = [[1,0]] Output: 4

Constraints:

  • row == grid.length
  • col == grid[i].length
  • 1 <= row, col <= 100
  • grid[i][j] is 0 or 1.
  • There is exactly one island in grid.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: row = 4, col = 4
    integer :: grid(row, col)

    ! Example 1
    grid(:, :) = reshape([0, 1, 0, 0, &
                           1, 1, 1, 0, &
                           0, 1, 0, 0, &
                           1, 1, 0, 0], shape(grid))
    print '(I0)', solve(grid)

    ! Example 2
    grid(:, :) = reshape([1], shape(grid))
    print '(I0)', solve(grid)

    ! Example 3
    grid(:, :) = reshape([1, 0], shape(grid))
    print '(I0)', solve(grid)

contains

    function solve(grid) result(perimeter)
        implicit none
        integer, intent(in) :: grid(:, :)
        integer :: perimeter
        integer :: i, j

        perimeter = 0
        do i = 1, size(grid, 1)
            do j = 1, size(grid, 2)
                if (grid(i, j) == 1) then
                    perimeter = perimeter + 4
                    if (i > 1 .and. grid(i-1, j) == 1) then
                        perimeter = perimeter - 2
                    end if
                    if (j > 1 .and. grid(i, j-1) == 1) then
                        perimeter = perimeter - 2
                    end if
                end if
            end do
        end do
    end function solve
end program main
✅ Compiled
❌ Executed
❌ Correct 
! Declare variables
integer :: row, col, i, j, perimeter
integer, dimension(:,:), allocatable :: grid

! Read input
read(*,*) row
read(*,*) col
allocate(grid(row,col))
do i = 1, row
    read(*,*) grid(i,:)
end do

! Calculate perimeter
perimeter = 0
do i = 2, row - 1
    do j = 2, col - 1
        if (grid(i,j) == 1) then
            if (grid(i-1,j) == 0 .or. grid(i+1,j) == 0 .or. grid(i,j-1) == 0 .or. grid(i,j+1) == 0) then
                perimeter = perimeter + 4
            end if
        end if
    end do
end do

! Print output
write(*,*) perimeter

end program
🌐 Data from online sources 
def islandPerimeter(grid):
    perimeter = 0
    for row in range(len(grid)):
        for col in range(len(grid[row])):
            if grid[row][col] == 1:
                perimeter += 4
                if row > 0 and grid[row - 1][col] == 1:
                    perimeter -= 2
                if col > 0 and grid[row][col - 1] == 1:
                    perimeter -= 2
    return perimeter

The algorithm iterates through each cell in the grid. If a cell contains land, increment the perimeter count by 4 (each side of the square). If there is land in the adjacent cell to the left or above, decrement the perimeter count by 2 for each adjacent land cell as they share a common side. This way, we can calculate the total perimeter of the island without any extra data structures or recursion.

🌐 Data from online sources 
int islandPerimeter(vector<vector<int>>& grid) {
    int perimeter = 0;
    for (int row = 0; row < grid.size(); row++) {
        for (int col = 0; col < grid[row].size(); col++) {
            if (grid[row][col] == 1) {
                perimeter += 4;
                if (row > 0 && grid[row - 1][col] == 1) perimeter -= 2;
                if (col > 0 && grid[row][col - 1] == 1) perimeter -= 2;
            }
        }
    }
    return perimeter;
}

The algorithm iterates through each cell in the grid. If a cell contains land, increment the perimeter count by 4 (each side of the square). If there is land in the adjacent cell to the left or above, decrement the perimeter count by 2 for each adjacent land cell as they share a common side. This way, we can calculate the total perimeter of the island without any extra data structures or recursion.