This page visualizes the classic "Number of Islands" problem. Given a 2D grid map of 'M' (land) and '~' (water), the goal is to count the number of distinct islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are surrounded by water.
The animation demonstrates a Depth-First Search (DFS) approach to solve this problem. When the algorithm encounters a piece of land ('M'), it increments the island count and then explores all connected land cells, marking them as visited ('.'). Water cells are marked as 'O' once visited during the traversal. Each step of the exploration is captured and rendered as a frame in the animation.
// Simplified DFS for counting islands
function numIslands(grid):
count = 0
for each cell (r, c) in grid:
if grid[r][c] is land:
count++
dfs(grid, r, c)
return count
function dfs(grid, r, c):
if (r, c) is out of bounds or is water or already visited:
return
mark grid[r][c] as visited
dfs(grid, r+1, c)
dfs(grid, r-1, c)
dfs(grid, r, c+1)
dfs(grid, r, c-1)