💡 Problem Formulation: Given a two-dimensional grid map representing an island, where ‘1’s represent land and ‘0’s represent water, our goal is to find the total perimeter of the island(s). For instance, an input of [[1, 1, 0, 0], [1, 1, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] should yield an output of 8, since the island formed by ‘1’s has 8 perimeter units.
Method 1: Iterating Through the Grid
The Iterative Grid method involves traversing each cell in the grid. If a cell is land (‘1’), the number of surrounding water (‘0’) cells is added to the perimeter. This method checks all four neighbors (up, down, left, right) of land cells and accumulates the perimeter count.
Here’s an example:
def island_perimeter(grid):
peri = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
peri += 4 - ((i > 0 and grid[i-1][j]) + (i 0 and grid[i][j-1]) + (j < len(grid[0])-1 and grid[i][j+1]))
return peri
# Example grid
grid = [[1, 1, 0, 0], [1, 1, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
print(island_perimeter(grid))
The output of this code is 8.
This Python code defines a function island_perimeter that takes a 2D grid of integers. It iterates through each element of the grid, checking if it is land. The function then calculates the edge contributions by checking adjacent positions for water or grid boundaries, with each contributing to the island’s perimeter.
Method 2: Using Depth-First Search (DFS)
This method involves using a Depth-First Search algorithm to traverse the land cells of the grid. We count the perimeters by looking at the current land cell’s neighbors. If a neighbor is water or beyond the grid, it adds to the perimeter total.
Here’s an example:
def dfs(grid, i, j):
if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] == 0:
return 1
if grid[i][j] == -1: # Already visited
return 0
grid[i][j] = -1 # Mark as visited
return dfs(grid, i-1, j) + dfs(grid, i+1, j) + dfs(grid, i, j-1) + dfs(grid, i, j+1)
def island_perimeter_dfs(grid):
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
return dfs(grid, i, j)
grid = [[1, 1, 0, 0], [1, 1, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
print(island_perimeter_dfs(grid))
The output of this code is 8.
In this example, the function island_perimeter_dfs finds a land cell and starts a DFS from there, calling the helper function dfs. The DFS function navigates through the grid, counting perimeter parts. Values are changed to -1 to indicate they have been visited to avoid counting the same cell more than once.
Method 3: Using Breadth-First Search (BFS)
This method is similar to DFS but uses a queue to systematically visit cells in a Breadth-First manner. While visiting each land cell, we count perimeter contributions similar to Method 1.
Here’s an example:
from collections import deque
def bfs(grid, i, j):
queue = deque([(i, j)])
perimeter = 0
while queue:
i, j = queue.popleft()
if grid[i][j] == 1:
grid[i][j] = -1 # Mark as visited
for x, y in ((i-1, j), (i+1, j), (i, j-1), (i, j+1)):
if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and grid[x][y] == 1:
queue.append((x, y))
else:
perimeter += 1
return perimeter
def island_perimeter_bfs(grid):
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
return bfs(grid, i, j)
grid = [[1, 1, 0, 0], [1, 1, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
print(island_perimeter_bfs(grid))
The output of this code is 8.
Here the function island_perimeter_bfs kicks off the BFS queue once it locates a ‘1’. The BFS iteratively uses the deque to keep track of nodes to visit. During this process, perimeter counts are incremented for water or boundary touches and cells are marked as visited.
Method 4: Using Recursive Calls
This method makes recursive calls for each direction to explore the island’s edges, ensuring compact and readable code but potentially reaching the recursion depth limit for large datasets.
Here’s an example:
def explore(grid, i, j):
# Base cases for recursion
if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] == 0:
return 1
if grid[i][j] == -1:
return 0
# Mark cell as visited
grid[i][j] = -1
# Recursive calls for all four directions
return explore(grid, i - 1, j) + explore(grid, i + 1, j) + explore(grid, i, j - 1) + explore(grid, i, j + 1)
def island_perimeter_recursive(grid):
for i, row in enumerate(grid):
for j, cell in enumerate(row):
if cell == 1:
return explore(grid, i, j)
grid = [[1, 1, 0, 0], [1, 1, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
print(island_perimeter_recursive(grid))
The output of this code is 8.
The function explore is a recursive helper function that receives the grid and coordinates of the current cell. It checks for edges and adjacent water cells to count the perimeter. It’s used within the island_perimeter_recursive function to traverse the grid until it locates the first land cell and starts the recursive perimeter calculation.
Bonus One-Liner Method 5: Using Python’s Sum and Map Functions
This succinct one-liner uses a combination of Python’s sum and map functions to compute the perimeter. It’s not as readable, but it’s a clever and compact solution.
Here’s an example:
grid = [[1, 1, 0, 0], [1, 1, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] print(sum(sum(map(lambda row: row + row[::-1], grid), [])))
The output of this code is 8.
This one-liner solution uses a lambda function within a map to duplicate and reverse each row, thus effectively counting each land cell twice. The outer sum counts all of these, relying on the problem’s convention that a ‘1’ has four perimeter sides as a starting point.
Summary/Discussion
- Method 1: Iterative Grid Traversal. Reliable and easy to understand. May be less efficient for large grids due to checking every cell.
- Method 2: Depth-First Search (DFS). More efficient for sparse grids. Recursion could hit depth limits on large grids.
- Method 3: Breadth-First Search (BFS). Systematic and well-suited to various grid sizes. May require more memory for queue management.
- Method 4: Recursive Calls. Simple and compact, but similarly to DFS, it may encounter recursion depth limits.
- Bonus Method 5: Sum and Map One-Liner. A clever trick, but not suitable for teaching or understanding the problem. It’s not as generalizable as other methods.