LeetCode link: 463. 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.
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.
Input: grid = [[1]]
Output: 4
Input: grid = [[1,0]]
Output: 4
row == grid.lengthcol == grid[i].length1 <= row, col <= 100grid[i][j]is0or1.- There is exactly one island in
grid.
- To calculate the perimeter of an island, we simply add up the number of water-adjacent edges of all water-adjacent lands.
- When traversing the grid, once land is found, the number of its adjacent water edges is calculated.
The island problem can be abstracted into a graph theory problem. This is an undirected graph:
And this graph has only one connected components (island).
- Find the first land.
- Starting at the first land, find all the lands of the island.
- There are two major ways to explore a
connected component(island): Depth-First Search (DFS) and Breadth-First Search (BFS). - For Depth-First Search, there are two ways to make it:
RecursiveandIterative. Here I will provide theRecursivesolution.- If you want to know Depth-First Search
Iterativesolution, please see 200. Number of Islands (Depth-First Search by Iteration). - If you want to know Breadth-First Search solution, please see 200. Number of Islands (Breadth-First Search).
- If you want to know Depth-First Search
- Mark each found land as
8which representsvisited. Visited lands don't need to be visited again.
- There are two major ways to explore a
- To calculate the perimeter of an island, we simply add up the number of water-adjacent edges of all water-adjacent lands.
- To solve this problem, you don't really need to use
DFSorBFS, but masteringDFSandBFSis absolutely necessary.
- Time:
O(n * m). - Space:
O(1).
class Solution:
def __init__(self):
self.grid = None
def islandPerimeter(self, grid: List[List[int]]) -> int:
self.grid = grid
perimeter = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
perimeter += self.water_side_count(i, j)
return perimeter
def water_side_count(self, i, j):
side_count = 0
for a, b in [
(-1, 0),
(0, -1), (0, 1),
(1, 0),
]:
m = i + a
n = j + b
if m < 0 or n < 0 or m >= len(self.grid) or n >= len(self.grid[0]) \
or self.grid[m][n] == 0:
side_count += 1
return side_countclass Solution:
def __init__(self):
self.perimeter = 0
self.grid = None
def islandPerimeter(self, grid: List[List[int]]) -> int:
self.grid = grid
for i, row in enumerate(self.grid):
for j, value in enumerate(row):
if value == 1:
self.depth_first_search(i, j)
return self.perimeter
def depth_first_search(self, i, j):
if i < 0 or i >= len(self.grid):
return
if j < 0 or j >= len(self.grid[0]):
return
if self.grid[i][j] != 1:
return
self.grid[i][j] = 8
self.perimeter += self.water_edges(i, j)
self.depth_first_search(i - 1, j)
self.depth_first_search(i, j + 1)
self.depth_first_search(i + 1, j)
self.depth_first_search(i, j - 1)
def water_edges(self, i, j):
result = 0
result += self.water_edge(i - 1, j)
result += self.water_edge(i, j + 1)
result += self.water_edge(i + 1, j)
result += self.water_edge(i, j - 1)
return result
def water_edge(self, i, j):
if i < 0 or i >= len(self.grid):
return 1
if j < 0 or j >= len(self.grid[0]):
return 1
if self.grid[i][j] == 0:
return 1
return 0// Welcome to create a PR to complete the code of this language, thanks!// Welcome to create a PR to complete the code of this language, thanks!// Welcome to create a PR to complete the code of this language, thanks!// Welcome to create a PR to complete the code of this language, thanks!// Welcome to create a PR to complete the code of this language, thanks!# Welcome to create a PR to complete the code of this language, thanks!// Welcome to create a PR to complete the code of this language, thanks!// Welcome to create a PR to complete the code of this language, thanks!// Welcome to create a PR to complete the code of this language, thanks!// Welcome to create a PR to complete the code of this language, thanks!// Welcome to create a PR to complete the code of this language, thanks!