For each land cell, start with 4 edges. Then subtract 1 for each adjacent land cell (up, down, left, right). Sum up the contributions of all land cells to get the total perimeter.
Start DFS from any land cell. At each cell, explore all four directions. If a neighbor is out of bounds or water, that edge contributes 1 to the perimeter. Use a visited set to avoid revisiting cells.
""" 0463.1 - Island Perimeter - Solution 1 - Iterative Counting """
#####################################################################################
# Imports
#####################################################################################
from typing import List
#####################################################################################
# Classes
#####################################################################################
class Solution:
"""Solution Class"""
def islandPerimeter(self, grid: List[List[int]]) -> int:
"""Island Perimeter Function"""
rows, cols = len(grid), len(grid[0])
perimeter = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1:
perimeter += 4
if r > 0 and grid[r - 1][c] == 1:
perimeter -= 2
if c > 0 and grid[r][c - 1] == 1:
perimeter -= 2
return perimeter
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
print(Solution().islandPerimeter([[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]])) # 16
print(Solution().islandPerimeter([[1]])) # 4
print(Solution().islandPerimeter([[1,0]])) # 4
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
""" 0463.2 - Island Perimeter - Solution 2 - DFS Traversal """
#####################################################################################
# Imports
#####################################################################################
from typing import List
#####################################################################################
# Classes
#####################################################################################
class Solution:
"""Solution Class"""
def islandPerimeter(self, grid: List[List[int]]) -> int:
"""Island Perimeter Function"""
rows, cols = len(grid), len(grid[0])
visited = set()
def dfs(r: int, c: int) -> int:
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 0:
return 1
if (r, c) in visited:
return 0
visited.add((r, c))
perimeter = 0
perimeter += dfs(r + 1, c)
perimeter += dfs(r - 1, c)
perimeter += dfs(r, c + 1)
perimeter += dfs(r, c - 1)
return perimeter
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1:
return dfs(r, c)
return 0
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
print(Solution().islandPerimeter([[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]])) # 16
print(Solution().islandPerimeter([[1]])) # 4
print(Solution().islandPerimeter([[1,0]])) # 4
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()