463 Island Perimeter

1. Description

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 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.

 

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.

2. Algorithms

When we consider all blocks exists in grid, we can add 4 perimeters when we meet land("1") in each row. However, if there any land in right or bottom, we should minus 2 from total perimeters.

 

To escape removing perimeters twice, we need to consider counting adjacent land in one way (left + upper or right + bottom).

 

1. Start
2. Declare variable perimeter and initialize it to 0.
3. For each row i and for each col j repeat under steps.
   1. If current block is land (grid[i][j] == 1), increment perimeter by 4.
      1. If current row is greater than and eqaul to 1 (j >= 1) and left block of current block is land (grid[i][j-1] == 1), increment perimeter by -2.
      2. If current col is greater than and equal to 1 (i >= 1) and upper blcok of current block is land (grid[i-1][j] == 1), increment perimeter by -2.
4. Return perimeter after loop ends.
5. End

3. Codes

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        perimeter = 0
        for i in range(len(grid)) : 
            for j in range(len(grid[0])) : 
                if grid[i][j] == 1 : 
                    perimeter += 4
                    if i >= 1 and grid[i-1][j] == 1 : 
                        perimeter -= 2
                    if j >= 1 and grid[i][j-1] == 1 : 
                        perimeter -= 2
        return perimeter

4. Conclusion